IncreMacro: Incremental Macro Placement Refinement
Authors: 
Yuan Pu, Tinghuan Chen, Zhuolun He, Chen Bai, Haisheng Zheng, Yibo Lin, Bei YuAuthors Info & Claims
Pages 169 - 176
Abstract
This paper proposes IncreMacro, a novel approach for macro placement refinement in the context of integrated circuit (IC) design. The suggested approach iteratively and incrementally optimizes the placement of macros in order to enhance IC layout routability and timing performance. To achieve this, IncreMacro utilizes several methods including kd-tree-based macro diagnosis, gradient-based macro shifting and constraint-graph-based LP for macro legalization. By employing these techniques iteratively, IncreMacro meets two critical solution requirements of macro placement: (1) pushing macros to the chip boundary; and (2) preserving the original macro relative positional relationship. The proposed approach has been incorporated into DREAMPlace and AutoDMP, and is evaluated on several RISC-V benchmark circuits at the 7-nm technology node. Experimental results show that, compared with the macro placement solution provided by DREAMPlace (AutoDMP), IncreMacro reduces routed wirelength by 6.5% (16.8%), improves the routed worst negative slack (WNS) and total negative slack (TNS) by 59.9% (99.6%) and 63.9% (99.9%), and reduces the total power consumption by 3.3% (4.9%).
References
[1]
Y. Lin, S. Dhar, W. Li, H. Ren, B. Khailany, and D. Z. Pan, "Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement," in Proc. DAC, 2019, pp. 1--6.
[2]
C.-K. Cheng, A. B. Kahng, I. Kang, and L. Wang, "Replace: Advancing solution quality and routability validation in global placement," IEEE TCAD, vol. 38, no. 9, pp. 1717--1730, 2018.
[3]
J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng, and C.-K. Cheng, "ePlace: Electrostatics-based placement using fast fourier transform and Nesterov's method," ACM TODAES, vol. 20, no. 2, pp. 1--34, 2015.
[4]
T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, "Ntuplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints," IEEE TCAD, vol. 27, no. 7, pp. 1228--1240, 2008.
[5]
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.
[6]
R. Cheng and J. Yan, "On joint learning for solving placement and routing in chip design," Proc. NeurIPS, vol. 34, pp. 16 508--16 519, 2021.
[7]
A. Mirhoseini, A. Goldie, M. Yazgan, J. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, S. Bae et al., "Chip placement with deep reinforcement learning," arXiv preprint arXiv:2004.10746, 2020.
[8]
R. Cheng, X. Lyu, Y. Li, J. Ye, J. Hao, and J. Yan, "The policy-gradient placement and generative routing neural networks for chip design," Proc. NeurIPS, vol. 35, pp. 26 350--26 362, 2022.
[9]
Y. Lai, Y. Mu, and P. Luo, "Maskplace: Fast chip placement via reinforced visual representation learning," arXiv preprint arXiv:2211.13382, 2022.
[10]
Y. Lai, J. Liu, Z. Tang, B. Wang, J. Hao, and P. Luo, "Chipformer: Transferable chip placement via offline decision transformer," arXiv preprint arXiv:2306.14744, 2023.
[11]
Z. Jiang, E. Songhori, S. Wang, A. Goldie, A. Mirhoseini, J. Jiang, Y.-J. Lee, and D. Z. Pan, "Delving into macro placement with reinforcement learning," in Proc. MLCAD. IEEE, 2021, pp. 1--3.
[12]
T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and D. Liu, "MP-trees: A packing-based macro placement algorithm for mixed-size designs," in Proc. DAC, 2007, pp. 447--452.
[13]
Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, "Routability-driven blockage-aware macro placement," in Proc. DAC, 2014, pp. 1--6.
[14]
C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, "Circular-contour-based obstacle-aware macro placement," in Proc. ASPDAC, 2016, pp. 172--177.
[15]
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE TCAD, vol. 15, no. 12, pp. 1518--1524, 1996.
[16]
X. Hong, "Non-slicing floorplan and placement using corner block list topological representation," IEEE TCAS I, vol. 51, no. 5, pp. 228--233, 2004.
[17]
Y.-C. Liu, T.-C. Chen, Y.-W. Chang, and S.-Y. Kuo, "Mdp-trees: multi-domain macro placement for ultra large-scale mixed-size designs," in Proc. ASPDAC, 2019, pp. 557--562.
[18]
A. B. Kahng, R. Varadarajan, and Z. Wang, "RTL-MP: toward practical, human-quality chip planning and macro placement," in Proc. ISPD, 2022, pp. 3--11.
[19]
T.-C. Chen and Y.-W. Chang, "Modern floorplanning based on fast simulated annealing," in Proc. ISPD, 2005, pp. 104--112.
[20]
C.-H. Chang, Y.-W. Chang, and T.-C. Chen, "A novel damped-wave framework for macro placement," in Proc. ICCAD, 2017, pp. 504--511.
[21]
H.-C. Chen, Y.-L. Chuang, Y.-W. Chang, and Y.-C. Chang, "Constraint graph-based macro placement for modern mixed-size circuit designs," in Proc. ICCAD, 2008, pp. 218--223.
[22]
A. Agnesina, P. Rajvanshi, T. Yang, G. Pradipta, A. Jiao, B. Keller, B. Khailany, and H. Ren, "AutoDMP: Automated DREAMPlace-based Macro Placement," in Proc. ISPD, 2023, pp. 149--157.
[23]
J. H. Friedman, J. L. Bentley, and R. A. Finkel, "An algorithm for finding best matches in logarithmic expected time," ACM Transactions on Mathematical Soft-ware, vol. 3, no. 3, pp. 209--226, 1977.
[24]
M.-K. Hsu, V. Balabanov, and Y.-W. Chang, "TSV-aware analytical placement for 3-D IC designs based on a novel weighted-average wirelength model," IEEE TCAD, vol. 32, no. 4, pp. 497--509, 2013.
[25]
J. Cong and M. Xie, "A robust detailed placement for mixed-size ic designs," in Proc. ASPDAC, 2006, pp. 7--pp.
[26]
D. F. Shanno and R. L. Weil, ""linear" programming with absolute-value functionals," Operations Research, vol. 19, no. 1, pp. 120--124, 1971.
[27]
"Pytorch," https://pytorch.org/.
[28]
"Gurobi," https://www.gurobi.com/.
[29]
A. Amid, D. Biancolin, A. Gonzalez, D. Grubb, S. Karandikar, H. Liew, A. Magyar, H. Mao, A. Ou, N. Pemberton et al., "Chipyard: Integrated design, simulation, and implementation framework for custom SoCs," IEEE Micro, vol. 40, no. 4, pp. 10--21, 2020.
[30]
K. Asanovic, R. Avizienis, J. Bachrach, S. Beamer, D. Biancolin, C. Celio, H. Cook, D. Dabbelt, J. Hauser, A. Izraelevitz et al., "The rocket chip generator," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2016--17, vol. 4, 2016.
[31]
K. Asanovic, D. A. Patterson, and C. Celio, "The berkeley out-of-order machine (boom): An industry-competitive, synthesizable, parameterized risc-v processor," University of California at Berkeley Berkeley United States, Tech. Rep., 2015.
[32]
L. T. Clark, V. Vashishtha, L. Shifren, A. Gujja, S. Sinha, B. Cline, C. Ramamurthy, and G. Yeric, "ASAP7: A 7-nm FinFET predictive process design kit," Microelectronics Journal, vol. 53, pp. 105--115, 2016.
Index Terms
- IncreMacro: Incremental Macro Placement Refinement
Recommendations
Handling complexities in modern large-scale mixed-size placement
DAC '09: Proceedings of the 46th Annual Design Automation ConferenceIn this paper, we propose an effective algorithm flow to handle large-scale mixed-size placement. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow consists of four steps: 1) The objects in the ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation ConferenceIn this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation ConferenceWe present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2024
286 pages
ISBN:9798400704178
DOI:10.1145/3626184
- General Chair:
- Iris Hui-Ru Jiang,
- Program Chair:
- Gracieli Posser
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 March 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISPD '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 62 of 172 submissions, 36%
Upcoming Conference
ISPD '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 519Total Downloads
- Downloads (Last 12 months)519
- Downloads (Last 6 weeks)103
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in