簡易檢索 / 詳目顯示

回結果列表
研究生： 李宗澤
Lee, Zong-Ze
論文名稱： 基於拓撲至幾何轉換學習之強化學習模組擺置方法
Reinforcement-Learning-Based Macro Placement via Topology-to-Geometry Transformation Learning
指導教授： 林家民
Lin, Jai-Ming
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2026
畢業學年度： 114
語文別： 英文
論文頁數： 70
中文關鍵詞： 實體設計 、模塊擺置 、強化學習 、拓樸至幾何轉換
外文關鍵詞： Physical Design, Macro Placement, Reinforcement Learning, Topology-to-Geometry Transformation
相關次數： 點閱：50  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 強化學習在模塊擺置領域已展現出巨大的潛力，然而現有方法往往依賴於人工設計的空間引導機制（例如線路遮罩）。這類方法需要在每一步都重新建構引導地圖，且無法保留將電路拓撲轉化為空間偏好的推理過程。
    在本論文中，我們提出了一個基於強化學習的大大型單元佈局框架，能夠學習「拓撲至幾何」的轉換。具體而言，我們採用超圖編碼器，直接根據網表與部分佈局結果預測出密集的空間引導地圖；這不僅能將完整連線關係映射至佈局畫布上，還能透過單次前向傳播降低建構成本。此外，我們提出了空間正規化的軟Q代理人，以提升探索穩定性，並使學習目標與後續的佈局品質保持一致。
    在學術基準測試中，與主流大大型單元佈局方法相比，我們的方法分別降低了 50%、12%、9% 和 2% 的線長。當整合至工業級佈局流程時，它實現了平均 12% 的線長改善，並將運行時間縮短高達 12 倍。這些結果表明，學習拓撲至幾何的轉換能有效提升基於強化學習之大大型單元佈局方法的實用性。

    Reinforcement learning has shown great potential for macro placement, but existing methods often rely on hand-crafted spatial guidance, such as WireMask. Such methods require reconstructing the guidance map at every step and cannot retain the reasoning process that transforms circuit connectivity into spatial preferences. In this thesis, we propose a reinforcement-learning-based macro placement framework that learns a topology-togeometry transformation. Specifically, we employ a hypergraph encoder to directly predict a dense spatial guidance map from the netlist and partial placement, thereby grounding full connectivity onto the placement canvas and reducing the construction cost through a single forward pass. Furthermore, we propose a spatially-regularized Soft-Q agent to improve exploration stability and align the learning objective with downstream placement quality. On academic benchmarks, our method reduces wirelength by 50%, 12%, 9%, and 2% compared with mainstream macro placement methods. When integrated into an industrial placement flow, it achieves an average wirelength improvement of 12% and reduces runtime by up to 12×. These results demonstrate that learning a topology-to-geometry transformation effectively improves the practicality of reinforcement-learning-based macro placement.

    1 Introduction 1 1.1 Previous Works 1 1.2 Survey of RL-based Macro Placers 3 1.2.1 Architecture-Centric Branch 4 1.2.2 Guidance-based Branch 4 1.3 Remaining Challenges 6 1.4 Our Contributions 7 2 Preliminary 9 2.1 Reinforcement Learning (RL), Deep-Q learning and Soft-Q learning 9 2.2 Reward Sparsity and the WireMask Approach 11 2.3 Auxiliary Learning 13 2.4 Set-Based Function and AllSet 15 3 Our Methodology 17 3.1 Method Overview 18 4 RL-Based Prototyping 20 4.1 State Representation 21 4.2 AllSet-Based Reward Map Estimator 24 4.3 Training the Estimator as Auxiliary Learning 26 4.4 Customized SR-SQ Agent 33 4.5 Overall Training Flow 38 5 Experimental Results 40 5.1 Academic benchmarks and experimental setup 40 5.2 Comparison with SOTA Placers on the academic benchmarks 42 5.3 Comparison with Innovus on Industrial Benchmarks 43 5.4 Runtime Analysis of our Reward Estimator versus Traditional Reward Construction 46 5.5 Visualizing Placement Quality 47 6 Ablation Studies 49 6.1 Ablation: Policy Backbone and Reward-Map Guidance 50 6.2 Ablation: Reward Composition 51 6.3 Ablation: Auxiliary-Task Calibration of the Estimator 53 7 Conclusion 56 References 57

    [1] Cadence Design Systems, “Cadence Innovus Implementation System,” [Online]. Available: http://www.cadence.com. [Accessed: Apr. 16, 2025].
    [2] A. Agnesina, P. Rajvanshi, T. Yang, G. Pradipta, A. Jiao, B. Keller, R. Khailany and H. Ren, “AutoDMP: Automated DREAMPlace-based Macro Placement,“ in Proc. of ISPD, pp. 149-157, 2023.
    [3] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech., vol. 2008, no. 10, p. P10008, Oct. 2008.
    [4] I. Bustany, A. B. Kahng, I. Koutis, B. Pramanik, and Z. Wang, “SpecPart: A supervised spectral framework for hypergraph partitioning solution improvement,” in Proc. of ICCAD, pp. 1-9, 2022.
    [5] R. Caruana, “Multitask Learning,” Machine Learning, vol. 28, no. 1, pp. 41–75, 1997.
    [6] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, “MP-trees: A packingbased macro placement algorithm for modern mixed-size designs,” IEEE Trans. of TCAD, vol. 27, no. 9, pp. 1621-1634, 2008.
    [7] Y.-F. Chen. C.-C. Huang, C.-H Chiou, Y.-W. Chang, and C.-J. Wang, “Routabilitydriven blockage-aware macro placement,” in Proc. of DAC, pp. 1-6, 2014.
    [8] M. Chen and T.-C. Wang, “A Hypergraph Partitioner Utilizing a Novel Graph Generative Model,” in Proc. of ICCAD, pp. 1–9, 2024.
    [9] C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, “Circular-contour-based obstacle-aware macro placement,” in Proc. of ASP-DAC, pp. 172-177, 2016.
    [10] C.-H. Chang, Y.-W. Chang, and T.-C. Chen, “A novel damped-wave framework for macro placement,” in Proc. of ICCAD, pp. 504-511, 2017.
    [11] C.-K. Cheng, A. B. Kahng, I. Kang and L. Wang, “RePlAce: Advancing Solution Quality and Routability Validation in Global Placement“,IEEE Trans. of TCAD, vol. 38, no. 9, pp. 1717-1730, 2018.
    [12] L. Chen, K. Lu, A. Rajeswaran, K. Lee, A. Grover, M. Laskin, P. Abbeel, A. Srinivas, and I. Mordatch, “Decision transformer: reinforcement learning via sequence modeling,” in Proc. of NeurIPS, pp. 15084–15097, 2021.
    [13] R. Cheng and J. Yan, “On joint learning for solving placement and routing in chip design,” in Proc. of NeurIPS, pp. 16508–16519, 2021.
    [14] E. Chien, C. Pan, J. Peng, and O. Milenkovic, “You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks,” in Proc. of ICLR, 2022. [15] T. Cover and P. Hart, “Nearest neighbor pattern classification,” IEEE Trans. of TIT, vol. 13, no. 1, pp. 21–27, 1967.
    [16] M. Fogac¸a, A. B. Kahng, R. Reis, and L. Wang, “Finding placement-relevant clusters with fast modularity-based clustering,” in Proc. 24th Asia and South Pacific Design Automation Conference (ASPDAC), pp. 569–576, 2019.
    [17] H. Furuta, Y. Matsuo, and S. S. Gu, “Generalized Decision Transformer for offline hindsight information matching,” in Proc. of ICLR, 2022.
    [18] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proc. of KDD, pp. 855–864, 2016.
    [19] H. Gu et al., “LAMPlace: Legalization-aided reinforcement learning-based macro placement for mixed-size designs with preplaced blocks,” IEEE Trans. of TCSII, vol. 71, no. 8, pp. 3770–3774, 2024.
    [20] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Proc. of NeurIPS, pp. 1025–1035, 2017.
    [21] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine, “Reinforcement Learning with Deep Energy-Based Policies,” in Proc. of ICML, pp. 1352–1361, 2017.
    [22] H. van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double Q-learning,” in Proc. of AAAI, pp. 2094–2100, 2016.
    [23] R. A. Howard, Dynamic Programming and Markov Processes. Cambridge, MA, USA: MIT Press, 1960.
    [24] M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu, “Reinforcement learning with unsupervised auxiliary tasks,” in Proc. of ICLR, 2017.
    [25] L. P. Kaelbling, M. L. Littman and A. W. Moore, “Reinforcement learning: A survey,“ JAIR, vol. 4, no. 1, p.p. 237-285, 1996.
    [26] Y. Lai, Y. Mu, P. Luo, “MaskPlace: Fast Chip Placement via Reinforced Visual Representation Learning,” in Proc. of NeurlIPS, pp. 24019-24030, 2022. [27] Y. Lai, J. Liu, Z. Tang, B. Wang, J. Hao, and P. Luo, “ChiPFormer: Transferable chip placement via offline decision transformer,” in Proc. of ICML, Art. no. 757, 2023.
    [28] B. S. Lengeling, E. Reif, A. Pearce and A. B. Wiltschko, “A Gentle Introduction to Graph Neural Networks,“ Accessed: July 2, 2025. Available: https://distill.pub/2021/gnn-intro/
    [29] J.-M. Lin, Y.-W. Chang, and S.-P. Lin, “Corner sequence: A P-admissible floorplan representation with a worst case linear-time packing scheme,” IEEE Trans. of TVLSI, vol. 11, no. 4, pp. 679-686, 2003.
    [30] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen, and Y.-C. Chen, “Novel Macro Placement Approach based on Simulated Evolution Algorithm,” in Proc. of ICCAD, pp. 1-7, 2019.
    [31] Y. Lin, Z. Jiang, J. Gu, W. Li, S. Dhar, H. Ren, “DREAMPlace: Deep learning toolkitenabled GPU acceleration for modern VLSI placement,” IEEE Trans. of TCAD, vol. 40, no. 4, pp. 748–761, 2021.
    [32] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen and P.-C. Lu, “Dataflow-Aware Macro Placement Based on Simulated Evolution Algorithm for Mixed-Size Designs,” IEEE Trans. of TVLSI, vol. 29, no. 5, pp. 973-984, 2021.
    [33] J. Lin, Z. Lee, and N. Lin, “Effective Macro Placement for Very Large Scale Designs Using MCTS Guided by Pre-Trained RL,” in Proc. of DATE, pp. 1-7, 2025.
    [34] Y. Liu, Z. Ju, Z. Li, M. Dong, H. Zhou, J. Wang, F. Yang, X. Zeng, and L. Shang, “Floorplanning with graph attention,” in Proc. of DAC, pp. 1303–1308, 2022.
    [35] Y. Liu, Z. Ju, Z. Li, M. Dong, H. Zhou, J. Wang, F. Yang, X. Zeng, and L. Shang, “GraphPlanner: Floorplanning with graph neural network,” ACM Trans. of TODAES, vol. 28, no. 2, Art. no. 21, 2022.
    [36] A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi et al., “A graph placement methodology for fast chip design,“ Nature, vol. 594, no. 7862, pp. 207– 212, 2021.
    [37] T. M. Moerland, J. Broekens, A. Plaat, and C. M. Jonker, “Model-based Reinforcement Learning: A Survey,” arXiv preprint arXiv:2006.16712, 2020. [38] Y. Pu, T. Chem, Z. He, C. Bai, H. Zheng, Y. Lin, B. Yu, “IncreMacro: Incremental Macro Placement Refinement,” in Proc. of ISPD, pp. 169-176, 2024.
    [39] A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever, “Improving language understanding by generative pre-training,” arXiv preprint arXiv:1801.10198, 2018.
    [40] S. Ruder, “An Overview of Multi-Task Learning in Deep Neural Networks,” arXiv preprint arXiv:1706.05098, 2017.
    [41] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms,” arXiv preprint arXiv:1707.06347, 2017.
    [42] Y. Shi, K. Xue, L. Song, and C. Qian, “Macro Placement by Wire-Mask-Guided Black-Box Optimization,” in Proc. of NeurIPS, 2023.
    [43] R. S. Sutton, “Learning to predict by the methods of temporal differences,” Machine Learning, vol. 3, no. 1, pp. 9–44, 1988.
    [44] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. Cambridge, MA, USA: MIT Press, 2018.
    [45] S. Thakoor, C. Tallec, M. G. Azar, R. Munos, P. Velickovic, and M. Valko, “Bootstrapped representation learning on graphs,” arXiv preprint arXiv:2102.06514, 2021.
    [46] P. Velickovi ˇ c, W. Fedus, W. L. Hamilton, P. Li ´ o, Y. Bengio, and R. D. Hjelm, “Deep ` Graph Infomax,” in Proc. of ICLR, 2019.
    [47] M. Wiering and M. van Otterlo, Eds., Reinforcement Learning: State-of-the-Art. Berlin, Germany: Springer, 2012.
    [48] D. Yarats, R. Fergus, A. Lazaric, and L. Pinto, “Mastering Visual Continuous Control: Improved Data-Augmented Reinforcement Learning,” in Proc. of ICLR, 2022.
    [49] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu, “Do Transformers really perform bad for graph representation?” in Proc. of NeurIPS, pp. 28877–28888, 2021.
    [50] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhutdinov, and A. J. Smola, ´ “Deep Sets,” in Proc. of NeurIPS, 2017.
    [51] Y. Zhang, S. Yang, and B. Yu, “Escaping local optima in global placement,” in Proc. of DAC (WIP), pp. 1–2, 2024.
    [52] X. Zhao, T. Wang, R. Jiao, and X. Guo, “Standard cells do matter: Uncovering hidden connections for high-quality macro placement,” in Proc. of DATE, pp. 1–6, 2024.

    QR CODE