[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. |