超大规模集成电路布局的优化模型与算法

doi:10.15960/j.cnki.issn.1007-6093.2021.03.002

摘要/Abstract

摘要： 布局确定集成电路单元在芯片中的具体位置，在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题，是超大规模集成电路物理设计的核心问题之一，对集成电路的性能指标，如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中，布局问题通常包含数百万个集成电路单元，以及大小相异的异质性模块，和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展，综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法，并展望进一步的研究方向。

关键词: 超大规模集成电路, 总体布局, 合法化, 优化算法

Abstract: Placement is one of the critical stages in the physical design of very large scale integrated circuits (VLSI), which has significant impact on the performance of integrated circuits, such as routability, delay, power consumption, circuit reliability, etc. Placement determines the specific positions of cells of a chip, by optimizing some performance metrics under the constraint of cells non-overlapping, which is an NP-hard combinatorial optimization problem. Modern placement algorithms need to deal with large-scale designs with millions of cells, heterogeneous modules with different sizes, and various complex placement constraints. Modern placement algorithms usually consist of three steps:global placement, legalization, and detailed placement. Based on the recent research progress of VLSI placement algorithms, this paper surveys related optimization models and algorithms for VLSI global placement, legalization and detailed placement, and discusses possible research directions.

Key words: VLSI, global placement, legalization, optimization algorithm

中图分类号:

TP302.1
O221

黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[J]. 运筹学学报, 2021, 25(3): 15-36.

HUANG Zhipeng, LI Xingquan, ZHU Wenxing. Optimization models and algorithms for placement of very large scale integrated circuits[J]. Operations Research Transactions, 2021, 25(3): 15-36.

参考文献

[1] Alpert C J, Mehta D P, Sapatnekar S S. Handbook of Algorithms for Physical Design Automation[M]. Florida:CRC Press, 2009:109-134.
[2] 徐宁, 洪先龙. 超大规模集成电路物理设计理论与算法[M]. 北京:清华大学出版社, 2009.
[3] Markov I L, Kim M C. Progress and challenges in VLSI placement research[C]//Proceedings of IEEE, 2015, 103(11):1985-2003.
[4] Chang Y W, Jiang Z W, Chen T C. Essential issues in analytical placement algorithms[J]. IPSJ Transactions on System LSI Design Methodology, 2009, 2:145-166.
[5] Sechen C, Sangiovanni-Vincentelli A. Timberwolf 3.2:a new standard cell placement and global routing package[C]//Proceedings of ACM/IEEE Design Automation Conference, 1986:432-439.
[6] Wang M, Yang X, Sarrafzadeh M. Dragon2000:standard-cell placement tool for large industry circuits[C]//Proceedings of IEEE/ACM International Conference on Computer Aided Design, 2000:260-263.
[7] Taghavi T, Yang X, Choi B K. Dragon2005:large-scale mixed-size placement tool[C]//Proceedings of International Symposium on Physical Design, 2005:212-217.
[8] Breuer M. Min-cut placement[J]. Journal of Design Automation Fault-Tolerant Computing, 1977, 10:343-382.
[9] Dunlop A E, Agrawal V D, Deutsch D N, et al. Chip layout optimization using critical path weighting[C]//Proceedings of Design Automation Conference Proceedings, 1984:133-136.
[10] Tsay R S, Kuh E S, Hsu C P. Proud:A fast sea-of-gates placement algorithm[C]//Proceedings of ACM/IEEE Design Automation Conference, 1988.
[11] Burkard R E, Karisch S E, Rendl F. QAPLIB-A quadratic assignment problem library[J]. Journal of Global Optimization, 1997, 10:391-403.
[12] Caldwell A E, Kahng A B, Markov I L. Can recursive bisection produce routable placements[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2000:477-482.
[13] Roy J A, Papa D A, Adya S N, et al. Capo:robust and scalable open-source min-cut floorplacer[C]//Proceedings of International Symposium on Physical Design, 2005:224-226.
[14] Roy J A, Adya S N, Papa D A, et al. Min-cut floorplacement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(7):1313-1326.
[15] Agnihotri A R, Ono S, Madden P H. Recursive bisection placement:feng shui 5.0 implementation detail[C]//Proceedings of International Symposium on Physical Design, 2005:230-232.
[16] Kleinhans J M, Sigl G, Johannes F M, et al. GORDIAN:VLSI placement by quadratic programming and slicing optimization[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(3):356-365.
[17] Naylor W C, Donelly R, Sha L. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. US 6301693[P]. 2001-08-28.
[18] Hu B, Zeng Y, Marek-Sadowska M. mFAR:Fixed-points-addition-based VLSI placement algorithm[C]//Proceedings of International Symposium on Physical Design, 2005:18-25.
[19] Kahng A B, Wang Q. Implementation and extensibility of an analytic placer[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(5):734-747.
[20] Kahng A B, Wang Q. A faster implementation of APlace[C]//Proceedings of International Symposium on Physical Design, 2006:218-220.
[21] Chan T F, Cong J, Shinnerl J R, et al. mPL6:Enhanced multilevel mixed-size placement[C]//Proceedings of International Symposium on Physical Design, 2006:212-214.
[22] Viswanathan N, Pan M, Chu C. FastPlace 2.0:An efficient analytical placer for mixed-mode designs[C]//Proceedings of Asia and South Pacific Conference on Design Automation, 2006:195-200.
[23] Viswanathan N, Pan M, Chu C. FastPlace 3.0:a fast multilevel quadratic placement algorithm with placement congestion control[C]//Proceedings of Asia and South Pacific Conference on Design Automation, 2007:135-140.
[24] Viswanathan N, Nam G J, Alpert C J, et al. RQL:Global placement via relaxed quadratic spreading and linearization[C]//Proceedings of ACM/IEEE Design Automation Conference, 2007:453-458.
[25] Brenner U, Struzyna M, Vygen J. BonnPlace:Placement of leading-edge chips by advanced combinatorial algorithms[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(9):1607-1620.
[26] Spindler P, Schlichtmann U, Johannes F M. Kraftwerk2:a fast force-directed quadratic placement approach using an accurate net model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(8):1389-1411.
[27] Chen T C, Jiang Z W, Hsu T C, et al. NTUplace3:An analytical placer for large-scale mixed-size design with preplaced blocks and density constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(7):1228-1240.
[28] Hsu M K, Chen Y F, Huang C C, et al. NTUplace4h:A novel routability-driven placement algorithm for hierarchical mixed-size circuit designs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(12):1914-1927.
[29] Huang C C, Lee H Y, Lin B Q, et al. NTUplace4dr:A detailed-routing-driven placer for mixed-size circuit designs with technology and region constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(3):669-681.
[30] Chen J, Lin Z, Kuo Y C, et al. Clock-aware placement for large-scale heterogeneous FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12):5042-5055.
[31] Kim M C, Lee D J, Markov I L. SimPL:An effective placement algorithm[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(1):50-60.
[32] Kim M C, Lee D J, Markov I L. SimPL:An algorithm for placing VLSI circuits[J]. Communication of the ACM, 2013, 56(6):105-113.
[33] Kim M C, Viswanathan N, Alpert C J, et al. MAPLE:Multilevel adaptive placement for mixed-size designs[C]//Proceedings of ACM International Symposium on Physical Design, 2012:193-200.
[34] Chen J, Zhu W. An analytical placer for VLSI standard cell placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(8):1208-1221.
[35] Lin T, Chu C. POLAR 2.0:An effective routability-driven placer[C]//Proceedings of ACM/ESDA/IEEE Design Automation Conference, 2014:1-6.
[36] Lin T, Chu C, Shinnerl J R, et al. POLAR:a high performance mixed-size wirelength-driven placer with density constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(3):447-459.
[37] Zhu W, Chen J, Peng Z, et al. Nonsmooth optimization method for VLSI global placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(4):642-655.
[38] Lu J, Chen P, Chang C C, et al. ePlace:electrostatics based placement using fast fourier transform and Nesterov's method[J]. ACM Transactions on Design Automation of Electronic Systems, 2015, 20(2):1-34.
[39] Lu J, Zhuang H, Chen P, et al. ePlace-MS:Electrostatics based placement for mixed-size circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(5):685-698.
[40] Cheng C K, Kahng A B, Kang I, et al. RePlAce:Advancing solution quality and routability validation in global placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(9):1717-1730.
[41] Li W, Lin Y, Pan D Z. elfPlace:Electrostatics-based placement for large-scale heterogeneous FPGAs[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2019:1-8.
[42] Zhu W, Huang Z, Chen J, et al. Analytical solution of Poisson's equation and its application to VLSI global placement[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2018.
[43] Chen J, Zhu W, Yu J, et al. Analytical placement with 3D Poisson's equation and ADMM based optimization for large-scale 2.5D heterogeneous FPGAs[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2019.
[44] Lin Y, Dhar S, Li W, et al. DREAMPIace:Deep learning toolkit-enabled GPU acceleration for modern VLSI placement[C]//Proceedings of ACM/IEEE Design Automation Conference, 2019.
[45] Lin Y, Pan D Z, Ren H, et al. DREAMPlace 2.0:Open-source GPU-accelerated global and detailed placement for large-scale VLSI designs[C]//Proceedings of China Semiconductor Technology International Conference, 2020.
[46] Gu J, Jiang Z, Lin Y, et al. DREAMPlace 3.0:Multi-electrostatics based robust VLSI placement with region constraints[C]//Proceedings of IEEE/ACM International Conference On Computer Aided Design, 2020.
[47] Nam G J, Cong J. Modern Circuit Placement:Best Practices and Results[M]. New York:Springer-Verlag, 2007.
[48] Kahng A B, Lee H, Li J. Horizontal benchmark extension for improved assessment of physical CAD research[C]//Proceedings of Great Lakes Symposium on VLSI, 2014:27-32.
[49] Chu C. Placement, in Electronic Design Automation:Synthesis, Verification, and Testing[M]. San Francisco:Morgan Kaufmann Publishers Inc, 2009:635-686.
[50] Viswanathan N, Chu C C N. Fastplace:Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(5):722-733.
[51] Hsu M K, Chang Y W, Balabanov V. TSV-aware analytical placement for 3D IC design[C]//Proceedings of ACM/IEEE Design Automation Conference, 2011:664-669.
[52] Chan T, Cong J, Sze K. Multilevel generalized force-directed method for circuit placement[C]//Proceedings of International Symposium on Physical Design, 2005:185-192.
[53] Brenner U, Struzyna M. Faster and better global placement by a new transportation algorithm[C]//Proceedings of ACM/IEEE Design Automation Conference, 2005:591-596.
[54] Fiduccia C M, Mattheyses R M. A linear-time heuristic for improving network partitions[C]//Proceedings of ACM/IEEE Design Automation Conference, 1982:175-181.
[55] Huang D J H, Kahng A B. Partitioning-based standard-cell global placement with an exact objective[C]//Proceedings of ACM International Symposium on Physical Design, 1997:18-25.
[56] Vygen J. Algorithms for large-scale flat placement[C]//Proceedings of ACM/IEEE Design Automation Conference, 1997:746-751.
[57] Agnihotri A R, Madden P H. Fast analytic placement using minimum cost flow[C]//Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, 2007:128-134.
[58] Ren H, Pan D Z, Alpert C J, et al. Diffusion-based placement migration with application on legalization[J]. IEEE Transations on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(12):2158-2172.
[59] Press W H, Teukolsky S A, Vetterling W T, et al. Numerical recipes in C++[M]. Cambridge:Cambridge University Press, 2002.
[60] Yao B, Chen H, Cheng C K, et al. Unified quadratic programming approach for mixed mode placement[C]//Proceedings of ACM International Symposium on Physical Design, 2005:193-199.
[61] Vorwerk K, Kennings A, Vannelli A. Engineering details of a stable force-directed placer[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2004:573-580.
[62] Kowarschik M, Weiß C. DiMEPACK-A cache-optimized multigrid library[C]//Proceedings of Conference on Parallel and Distributed Processing Techniques and Applications, 2001:425-430.
[63] Nam G J, Reda S, Alpert C J, et al. A fast hierarchical quadratic placement algorithm[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(4):678-691.
[64] Luo T, Pan D Z. DPlace2.0:A stable and efficient analytical placement based on diffusion[C]//Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, 2008:346-351.
[65] Luenberger D G. Linear and Nonlinear Programming[M]. New Jersey:Addison Wesley, 1984.
[66] Karypis G, Kumar V. Multilevel k-way hypergraph partitioning[C]//Proceedings of ACM/IEEE Design Automation Conference, 1999:343-348.
[67] Alpert C J, Kahng A B, Nam G J, et al. A semi-persistent clustering technique for VLSI circuit placement[C]//Proceedings of International Symposium on Physical Design, 2005:200-207.
[68] Nesterov Y E. A method of solving a convex programming problem with convergence rate O(1/k²)[J]. Dokl. Akad. Nauk SSSR, 1983, 269(3):543-547.
[69] Hestenes M R. Multiplier and gradient methods[J]. Journal of Optimization Theory and Applications, 1969, 4(5):303-320.
[70] Zhu W, Chen J, Li W. An augmented Lagrangian method for VLSI global placement[J]. The Journal of Supercomputing, 2014, 69:714-738.
[71] Zhu Z, Chen J, Peng Z, et al. Generalized augmented Lagrangian and its applications to VLSI global placement[C]//Proceedings of ACM/ESDA/IEEE Design Automation Conference, 2018.
[72] Peng Z, Chen J, Zhu W. A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints[J]. Journal of Global Optimization, 2015, 62:711-728.
[73] Chen J, Yang L, Peng Z, et al. Novel proximal group ADMM for placement considering fogging and proximity effects[C]//Proceedings of IEEE/ACM International Conference on ComputerAided Design, 2018.
[74] Shahsavani S N, Pedram M. TDP-ADMM:A timing driven placement approach for superconductive electronic circuits using alternating direction method of multipliers[C]//Proceedings of ACM/IEEE Design Automation Conference, 2020.
[75] Chen J, Huang Z, Huang Y, et al. An efficient EPIST algorithm for global placement with non-integer multiple-height cells[C]//202057th ACM/IEEE Design Automation Conference, 2020.
[76] Lin Y. GPU acceleration in VLSI back-end design:overview and case studies[C]//Proceedings of IEEE/ACM International Conference On Computer Aided Design, 2020.
[77] Hill D. Method and system for high speed detailed placement of cells within an intergrated circuit design. US 6370673[P]. 2002-04-09.
[78] Spindler P, Schlichtmann U, Johannes F M. Abacus:Fast legalization of standard cell circuits with minimal movement[C]//Proceedings of International Symposium on Physical Design, 2008:47-53.
[79] Caldwell A E, Kahng A B, Markov I L. Optimal partitioners and end-case placers for standardcell layout[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(11):1304-1313.
[80] Jonker R, Volgenant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems[J]. Computing, 1987, 38(4):325-340.
[81] Pan M, Viswanathan N, Chu C. An efficient and effective detailed placement algorithm[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2005:48-55.
[82] Agnihotri A, Yildiz M C, Khatkhate A, et al. Fractional cut:improved recursive bisection placement[C]//Proceedings of IEEE International Conference on Computer-Aided Design, 2003:307-310.
[83] Doll K, Johannes F M, Antreich K J. Iterative placement improvement by network flow methods[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(10):1189-1200.
[84] Brenner U, Vygen J. Legalizing a placement with mimimum total movement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23(12):1597-1613.
[85] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2010, 17(6):917-933.
[86] Chen J, Zhu Z, Zhu W, et al. A robust modulus-based matrix splitting iteration method for mixed-cell-height circuit legalization[J]. ACM Transactions on Design Automation of Electronic Systems, 2021, 26(2):1-28.
[87] Chen J, Yang P, Li X, et al. Mixed-cell-height placement with complex minimum-implantarea constraints[C]//Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2018.
[88] Zhu Z, Chen J, Zhu W, et al. Mixed-cell-height legalization considering technology and region constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12):5128-5141.
[89] Zhu Z, Huang Z, Yang Peng, et al. Mixed-cell-height legalization considering complex minimum width constraints and half-row fragmentation effect[J]. Integration, 2020, 71:1-10.
[90] Li X, Chen J, Zhu W, et al. Analytical mixed-cell-height legalization considering average and maximum movement minimization[C]//Proceedings of International Symposium on Physical Design, 2019:27-34.
[91] Li H, Chow W K, Chen G, et al. Routability-driven and fence-aware legalization for mixed-cellheight circuits[C]//Proceedings of ACM/ESDA/IEEE Design Automation Conference, 2018.
[92] Cauley S, Balakrishnan V, Hu Y C, et al. A parallel branch-and-cut approach for detailed placement[J]. ACM Transactions on Design Automation of Electronic Systems, 2011, 16(2):1-19.