北大中文核心期刊 中国科学引文数据库（CSCD）来源期刊 中国科技核心期刊 入选数学领域高质量科技期刊 Scopus EBSCO
北大中文核心期刊 中国科学引文数据库（CSCD）来源期刊 中国科技核心期刊 入选数学领域高质量科技期刊 Scopus EBSCO
运筹学学报 ›› 2021, Vol. 25 ›› Issue (3): 15-36.doi: 10.15960/j.cnki.issn.1007-6093.2021.03.002
所属专题： 第七届中国运筹学会科学技术奖获奖者专辑
黄志鹏1, 李兴权2, 朱文兴1,2,*
收稿日期:2021-03-15
发布日期:2021-09-26
通讯作者:
朱文兴 E-mail:wxzhu@fzu.edu.cn
基金资助:HUANG Zhipeng1, LI Xingquan2, ZHU Wenxing1,2,*
Received:2021-03-15
Published:2021-09-26
摘要： 布局确定集成电路单元在芯片中的具体位置，在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题，是超大规模集成电路物理设计的核心问题之一，对集成电路的性能指标，如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中，布局问题通常包含数百万个集成电路单元，以及大小相异的异质性模块，和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展，综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法，并展望进一步的研究方向。
中图分类号:
黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[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/k2)[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. |
| [1] | 魏佳祯, 边伟. 共识优化算法的研究进展综述[J]. 运筹学学报（中英文）, 2026, 30(1): 1-23. |
| [2] | 袁柳洋, 汤梦瑶, 迟晓妮. 一类新的无参数的填充打洞函数法[J]. 运筹学学报（中英文）, 2025, 29(2): 214-220. |
| [3] | 周宇阳, 张惠珍, 马良. 求解应急医疗设施分层递进式选址问题的改进免疫算法[J]. 运筹学学报, 2021, 25(2): 15-34. |
| [4] | 黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106. |
| [5] | 简金宝, 杨林峰, 张晨. 电力系统机组组合问题的模型与优化方法[J]. 运筹学学报（中英文）, 2020, 24(2): 87-102. |
| [6] | 孔令臣, 陈丙振, 修乃华, 戚厚铎. 高维约束矩阵回归问题[J]. 运筹学学报, 2017, 21(2): 31-38. |
| [7] | 董振宇, 冯恩民, 尹洪超, 张誉铎. 国际原油价格预测的双层随机整数规划模型、算法及应用[J]. 运筹学学报, 2015, 19(3): 18-25. |
| [8] | 叶敏, 吴至友, 张亮. 线性约束三次规划问题的全局最优性必要条件和最优化算法[J]. 运筹学学报, 2015, 19(2): 15-28. |
| [9] | 田静, 吴至友, J. Ugon. 一类特殊多项式整数规划问题的最优化算法[J]. 运筹学学报, 2011, 15(4): 23-35. |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||
