Progress and challenges in VLSI placement research

ABSTRACT

Given the significance of placement in IC physical design, extensive research studies performed over the last 50 years addressed numerous aspects of global and detailed placement. The objectives and the constraints dominant in placement have been revised many times over, and continue to evolve. Additionally, the increasing scale of placement instances affects the algorithms of choice for high-performance tools. We survey the history of placement research, the progress achieved up to now, and outstanding challenges.

References

1. S. N. Adya, I. L. Markov, "Combinatorial Techniques for Mixed-size Placement", TODAES 10(1) 2005, pp. 58--90.
2. S. N. Adya, I. L. Markov, P. G. Villarrubia, "On Whitespace and Stability in Physical Synthesis", Integration 39(4) 2006, pp. 340--362.
3. A. Agnihorti, M. C. Yildiz, A. Khatkhate, A. Mathur, S. Ono, P. H. Madden, "Fractional Cut: Improved Recursive Bisection Placement", ICCAD 2003, pp. 307--310.
4. C. J. Alpert et al., "Techniques for Fast Physical Synthesis", IEEE 95(3) 2007, pp. 573--599.
5. C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, S. T. Quay, "Porosity Aware Buffered Steiner Tree Construction", ISPD 2003, pp. 158--165.
6. C. J. Alpert, Z. Li, M. D. Moffitt, G.-J. Nam, J. A. Roy, G. Tellez, "What Makes a Design Difficult to Route", ISPD 2010, pp. 7--12.
7. C. J. Alpert, Z. Li, G.-J. Nam, C. N. Sze, N. Viswanathan, S. Ward, "Placement: Hot or Not?" ICCAD 2012.
8. C. J. Alpert, D. P. Mehta, S. S. Sapatnekar (eds.), Handbook of Algorithms for VLSI Physical Design Automation, CRC Press 2008.
9. U. Brenner, "VLSI Legalization with Minimum Perturbation by Iterative Augmentation", DATE 2012 pp. 1385--1390.
10. U. Brenner, A. Rohe, "An Effective Congestion Driven Placement Framework", ISPD 2002, pp. 6--11.
11. U. Brenner, J. Vygen, "Faster Optimal Single-row Placement with Fixed Ordering", DATE 2000, pp. 117--121.
12. U. Brenner, J. Vygen, "Legalizing a Placement with Minimum Total Movement", TCAD 23(12) 2004, pp. 1597--1613.
13. U. Brenner, M. Struzyna, J. Vygen, "BonnPlace: Placement of Leading-edge Chips by Advanced Combinatorial Algorithms", TCAD 27(9) 2008, pp. 1607--1620.
14. M. Breuer, "Min-cut Placement", Journal of Design Automation and Fault-tolerant Computing 10 (1977), pp. 343--382.
15. M. Burstein, M. N. Youssef, "Timing Influenced Layout Design", DAC 1985, pp. 124--130.
16. A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov, A. Zelikovsky, "On Wirelength Estimations for Row-based Placement", TCAD 18(9) 1999, pp. 1265--1278.
17. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?" DAC 2000, pp. 477--482.
18. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", TCAD 19(11) 2000, pp. 1304--1313.
19. S. Cauley, V. Balakrishnan, Y. C. Hu, C.-K. Koh, "A Parallel Branch-and-Cut Approach for Detailed Placement", TODAES 16(2) 2011, no. 18.
20. T. F. Chan, J. Cong, K. Sze, "Multilevel Generalized Force-directed Method for Circuit Placement", ISPD 2005, pp. 185--192.
21. T. F. Chan, J. Cong, M. Romesis, J. R. Shinnerl, K. Sze, M. Xie, "mPL6: Enhanced Multilevel Mixed-size Placement with Congestion Control", Modern Circuit Placement, 2007, pp. 247--288.
22. T. F. Chan, J. Cong, E. Radke, "A Rigorous Framework for Convergent Net Weighting Schemes in Timing-driven Placement", ICCAD 2009, pp. 288--294.
23. Y.-T. Chang, C.-C. Hsu, M. P.-H. Lin, Y.-W. Tsi, S.-F. Chen, "Post-placement Power Optimization with Multi-bit Flip-flops", ICCAD 2010, pp. 218--223.
24. H. Chang, E. Shragowitz, J. Liu, H. Youssef, B. Lu, S. Sutanthavibul, "Net Criticality Revisited: An Effective Method to Improve Timing in Physical Design", ISPD 2002, pp. 155--160.
25. C. Chang, J. Cong, X. Yuan, "Multi-level Placement for Large-scale Mixed-size IC Design", ASPDAC 2003, pp. 325--330.
26. H.-C. Chen, Y.-L. Chuang, Y.-W. Chang, Y.-C. Chang, "Constraint Graph-based Macro Placement for Modern Mixed-size Circuit Designs", ICCAD 2008, pp. 218--223.
27. T.-C. Chen, A. Chakraborty, D. Z. Pan, "An Integrated Nonlinear Placement Framework with Congestion and Porosity Aware Buffer Planning", DAC 2008, pp. 702--707.
28. T.-C. Chen, M. Cho, D. Z. Pan, Y.-W. Chang, "Metal-density-driven Placement for CMP Variation and Routability", TCAD 27(12) 2008, pp. 2145--2155.
29. T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, T.-Y. Liu, "MP-Trees: A Packing-based Macro Placement Algorithm for Modern Mixed-size Designs", TCAD 27(9) 2008, pp. 1621--1634.
30. C. E. Cheng, "RISA: Accurate and Efficient Placement Routability Modeling", ICCAD 1994, pp. 650--695.
31. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, Y.-W. Chang, "NTUPlace3: An Analytical Placer for Large-scale Mixed-size Designs with Preplaced Blocks and Density Constraints", TCAD 27(7) 2008, pp. 1228--1240.
32. Y. Cheon, P.-H. Ho, A. B. Kahng, S. Reda, Q. Wang, "Power-aware Placement", DAC 2005, pp. 795--800.
33. M.-F. Chiang, T. Okamoto, T. Yoshimura, "Register Placement for High-performance Circuits", DATE 2009, pp. 1470--1475.
34. M. Cho, H. Ren, H. Xiang, R. Puri, "History-based VLSI Legalization using Network Flow", DAC 2010, pp. 286--291.
35. W. Choi, K. Bazargan, "Hierarchical Global Floorplacement using Simulated Annealing and Network Flow Area Migration", DATE 2003, pp. 1104--5.
36. S. Chou, M.-K. Hsu, Y.-W. Chang, "Structure-aware Placement for Datapath-intensive Circuit Designs", DAC 2012, pp. 762--767.
37. A. Chowdhary et al., "How Accurately Can We Model Timing in a Placement Engine", DAC 2005, pp. 801--806.
38. C. Chu, M. Pan, "IPR: An Integrated Placement and Routing Algorithm", DAC 2007, pp. 59--62.
39. Y.-L. Chuang, H.-T. Lin, T.-Y. Ho, Y.-W. Chang, D. Marculescu, "PRICE: Power Reduction by Placement and Clock-network Co-synthesis for Pulsed-latch Designs", ICCAD 2011, pp. 85--90.
40. Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. A. Roy, N. Viswanathan, "Design-hierarchy Aware Mixed-size Placement for Routability Optimization", ICCAD 2010, pp. 663--668.
41. J. Cong, B. Liu, G. Luo, R. Prabhakar, "Towards Layout-friendly High-level Synthesis", ISPD 2012, pp. 165--172.
42. J. Cong, G. Luo, E. Radke, "Highly Efficient Gradient Computation for Density-constrained Analytical Placement", TCAD 27(12) 2008, pp. 2133--44.
43. J. Cong, J. R. Shinnerl, M. Xie, T. Kong, X. Yuan, "Large-scale Circuit Placement", TODAES 10(2) 2005, pp. 389--430.
44. J. Cong, M. Xie, "A Robust Detailed Placement for Mixed-size IC Designs", ASPDAC 2006, pp. 188--194.
45. J. Cong, M. Romesis, J. R. Shinnerl, "Robust Mixed-size Placement Under Tight White-space Constraints", ICCAD 2005, pp. 165--172.
46. K.-R. Dai, C.-H. Lu, Y.-L. Li, "GRPlacer: Improving Routability and Wirelength of Global Routing with Circuit Replacement", ICCAD 2009, pp. 351--356.
47. K. Doll, F. M. Johannes, K. J. Antreich, "Iterative Placement Improvement by Network Flow Methods", TCAD 13(10) 1994, pp. 1189--1200.
48. W. E. Donath, P. Kudva, L. Stok, P. G. Villarrubia, L. N. Reddy, A. Sullivan and K. Chakraborty, "Transformational Placement and Synthesis", DATE 2000, 194--201.
49. A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F. Jukl, P. Kozak, M. Wiesel, "Chip Layout Optimization using Critical Path Weighting", DAC 1984, pp. 133--136.
50. H. Eisenmann, F. M. Johannes, "Generic Global Placement and Floorplanning", DAC 1998, pp. 269--274.
51. T. Gao, P. M. Vaidya, C. L. Liu, "A Performance Driven Macro-cell Placement Algorithm", DAC 1992, pp. 147--152.
52. S. Ghiasi, E. Bozorgzadeh, P.-K. Huang, R. Jafari, M. Sarrafzadeh, "A Unified Theory of Timing Budget Management", TCAD 25(11) 2006, pp. 2364--2375.
53. B. Halpin, C. Y. R. Chen, N. Sehgal, "A Sensitivity Based Placer for Standard Cells", GSLVLSI, 2000, pp. 193--196.
54. B. Halpin, C. Y. R. Chen, N. Sehgal, "Timing Driven Placement using Physical Net Constraints", DAC 2001, pp. 780--783.
55. B. Halpin, C. Y. R. Chen, N. Sehgal, "Detailed Placement with Net Length Constraints", IWSOC 2003, pp. 22--27.
56. T. Hamada, C. K. Cheng, P. M. Chau, "Prime: A Timing-driven Placement Tool using a Piecewise Linear Resistive Network Approach", DAC 1993, pp. 531--536, 1993.
57. P. S. Hauge, R. Nair, E. J. Yoffa, "Circuit Placement for Predictable Performance", ICCAD 1987, pp. 88--91.
58. X. He, T. Huang, L. Xiao, H. Tian, G. Cui, E. F. Young, "Ripple: An Effective Routability-driven Placer by Iterative Cell Movement", ICCAD 2011, pp. 74--79.
59. D. Hill, Method and System for High Speed Detailed Placement of Cells within an Integrated Circuit Design, U.S. Patent 6370673, 2001.
60. T.-Y. Ho, S.-H. Liu, "Fast Legalization for Standard Cell Placement with Simultaneous Wirelength and Displacement Minimization", VLSI-SoC 2010, pp. 369--374.
61. W. Hou, H. Yu, X. Hong, Y. Cai, W. Wu, J. Gu, W. H. Kao, "A New Congestion-driven Placement Algorithm Based on Cell Inflation", ASPDAC 2001, pp. 723--728.
62. M.-K. Hsu, Y.-W. Chang, "Unified Analytical Global Placement for Large-scale Mixed-size Circuit Designs", ICCAD 2010, pp. 657--662.
63. M.-K. Hsu, Y.-W. Chang, V. Balabanov, "TSV-aware Analytical Placement for 3D IC Designs", DAC 2011, pp. 664--669.
64. M.-K. Hsu, S. Chou, T.-H. Lin, Y.-W. Chang, "Routability-driven Analytical Placement for Mixed-size Circuit Designs", ICCAD 2011, pp. 80--84.
65. B. Hu, M. Marek-Sadowska, "Congestion Minimization during Placement without Estimation", ICCAD 2002, pp. 739--745.
66. B. Hu, M. Marek-Sadowska, "Multilevel Fixed-point-addition-based VLSI Placement", TCAD 24(8) 2005, pp. 1188--1203.
67. J. Hu, A. B. Kahng, S.-H. Kang, M.-C. Kim, I. L. Markov, "Sensitivity-guided Metaheuristics for Accurate Discrete Gate Sizing", ICCAD 2012.
68. J. Hu, Y. Shin, N. Dhanwada, R. Marculescu, "Architecting Voltage Islands in Core-based System-on-a-Chip Designs", ISLPED 2004, pp. 180--5.
69. J. Hu, J. A. Roy, I. L. Markov, "Completing High-quality Routes", ISPD 2010, pp. 35--41.
70. T. C. Hu, K. Moerder, "Multiterminal Flows in a Hypergraph", VLSI Circuit Layout: Theory and Design (T. C. Hu, E. S. Kuh, eds.), IEEE, 1985.
71. S. Hur, T. Cao, K. Rajagopal, Y. Parasuram, A. Chowdhary, V. Tiourin, B. Halpin, "Force Directed Mongrel with Physical Net Constraints", DAC 2003, pp. 214--219.
72. S.-W. Hur, J. Lillis, "Mongrel: Hybrid Techniques for Standard Cell Placement", ICCAD 2000, pp. 165--170.
73. International Technology Roadmap for Semiconductors (ITRS). http://public.itrs.net
74. M. A. B. Jackson, E. S. Kuh, "Performance-driven Placement of Cell Based ICs", DAC 1989, pp. 370--375.
75. D. Jariwala, J. Lillis, "RBI: Simultaneous Placement and Routing Optimization Technique", TCAD 26(1) 2007, pp. 127--141.
76. Z.-W. Jiang, B.-Y. Su, Y.-W. Chang, "Routability-driven Analytical Placement by Net Overlapping Removal for Large-scale Mixed-size Designs", DAC 2008, pp. 167--172.
77. H.-R. Jiang, C.-L. Chang, Y.-M. Yang, "INTEGRA: Fast Multibit Flip-flop Clustering for Clock Power Saving", TCAD 31(2) 2012, pp. 192--204.
78. A. B. Kahng, "Classical Floorplanning Harmful?" ISPD 2000, pp. 207--213.
79. A. B. Kahng, J. Lienig, I. L. Markov, J. Hu, "VLSI Physical Design: From Graph Partitioning to Timing Closure", Springer 2011.
80. A. B. Kahng, I. L. Markov, S. Reda, "On Legalization of Row-based Placements", GSLVLSI, 2004, pp. 214--219.
81. A. B. Kahng, C.-H. Park, P. Sharma, Q. Wang, "Lens Aberration Aware Placement for Timing Yield", TODAES 14(1) 2009, no. 16.
82. A. B. Kahng, P. Tucker, A. Zelikovsky, "Optimization of Linear Placements for Wirelength Minimization with Free Sites", ASPDAC 1999, pp. 241--4.
83. A. B. Kahng, Q. Wang, "A Faster Implementation of A Place", ISPD 2006, pp. 218--220.
84. J. Knechtel, I. L. Markov, J. Lienig, "Assembling 2-D Blocks Into 3-D Chips", TCAD 31(2) 2012, pp. 228--241.
85. M.-C. Kim, D.-J. Lee, I. L. Markov, "SimPL: An Effective Placement Algorithm", ICCAD 2010, pp. 649--656.
86. M.-C. Kim, J. Hu, D.-J. Lee, I. L. Markov, "A SimPLR Method for Routability-driven Placement", ICCAD 2011, pp. 67--73.
87. M.-C. Kim, D.-J. Lee, I. L. Markov, "SimPL: An Effective Placement Algorithm", TCAD 31(1) 2012, pp. 50--60.
88. M.-C. Kim, I. L. Markov, "ComPLx: A Competitive Primal-dual Lagrange Optimization for Global Placement", DAC 2012, pp. 747--752.
89. M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, S. Ramji, "MAPLE: Multilevel Adaptive PLacEment for Mixed-size Designs", ISPD 2012, pp. 193--200.
90. T. Kong, "A Novel Net Weighting Algorithm for Timing-driven Placement", ICCAD 2002, pp. 172--176.
91. D. E. Lackey, P. S. Zuchowski, T. R. Bednar, D. W. Stout, S. W. Gould and J. M. Cohn, "Managing Power and Performance for System-on-Chip Designs using Voltage Islands", ICCAD 2002, pp. 195--202.
92. D.-J. Lee, I. L. Markov, "Obstacle-aware Clock-tree Shaping during Placement", TCAD 31(2) 2012, pp. 205--216.
93. Y.-M. Lee, T.-Y. Wu, P.-Y. Chang, "A Hierarchical Bin-based Legalizer for Standard-cell Designs with Minimal Disturbance", ASPDAC 2010, pp. 568--573.
94. C. Li, C.-K. Koh, "Recursive Function Smoothing of Half-perimeter Wirelength for Analytical Placement", ISQED, 2007, pp. 829--834.
95. C. Li, C.-K. Koh, P. H. Madden, "Floorplan Management: Incremental Placement for Gate Sizing and Buffer Insertion", ASPDAC 2005, pp. 349--54.
96. C. Li, M. Xie, C.-K. Koh, J. Cong, P. H. Madden, "Routability-driven Placement and White Space Allocation", TCAD 26(5) 2007, pp. 858--871.
97. S. Li, C.-K. Koh, "Mixed Integer Programming Models for Detailed Placement", ISPD 2012, pp. 87--94.
98. Z. Li, C. N. Sze, C. J. Alpert, J. Hu, W. Shi, "Making Fast Buffer Insertion Even Faster via Approximation Techniques", ASPDAC 2005, pp. 13--18.
99. Z. Li, W. Wu, X. Hong, "Congestion Driven Incremental Placement Algorithm for Standard Cell Layout", ASPDAC 2003, pp. 723--728.
100. B. Liu, Y. Cai, Q. Zhou, X. Hong, "Power Driven Placement with Layout Aware Supply Voltage Assignment for Voltage Island Generation in Dual-Vdd Designs", ASPDAC 2006, pp. 582--587.
101. W. K. Luk, "A Fast Physical Constraint Generator for Timing Driven Placement", DAC 1991, pp. 626--631.
102. T. Luo, D. Newmark, D. Z. Pan, "A New LP Based Incremental Timing Driven Placement for High Performance Designs", DAC 2006, pp. 1115--20.
103. T. Luo, D. Z. Pan, "DPlace2.0: A Stable and Efficient Analytical Placement Based on Diffusion", ASPDAC 2008, pp. 346--351.
104. T. Luo, H. Ren, C. J. Alpert, D. Z. Pan, "Computational Geometry Based Placement Migration", DAC 2007, pp. 41--47.
105. Y. Lu, C. N. Sze, X. Hong, Q. Zhou, Y. Cai, L. Huang, J. Hu, "Navigating Registers in Placement for Clock Network Minimization", DAC 2005, pp. 176--181.
106. N. Magen, A. Kolodny, U. Weiser, N. Shamir, "Interconnect-power Dissipation in a Microprocessor", SLIP 2004, pp. 7--13.
107. M. D. Moffitt, J. A. Roy, I. L. Markov, M. E. Pollack, "Constraint-driven Floorplan Repair", TODAES 13(4) 2008, pp. 1--13.
108. R. Nair, C. L. Berman, P. S. Hauge, E. J. Yoffa, "Generation of Performance Constraints for Layout", TCAD 8(8) 1989, pp. 860--874.
109. G.-J. Nam, J. Cong, Modern Circuit Placement: Best Practices and Results, Springer 2007.
110. B. Obermeier, F. M. Johannes, "Temperature-aware Global Placement", ASPDAC 2004, pp. 143--148.
111. B. Obermeier, H. Ranke, F. M. Johannes, "Kraftwerk: a Versatile Placement Approach", ISPD 2005, pp. 242--244.
112. M. Orshansky, S. Nassif, D. Boning, Design for Manufacturability and Statistical Design: A Constructive Approach (Integrated Circuits and Systems), Springer 2010.
113. M. M. Ozdal, C. Amin, A. Ayupov, S. Burns, G. Wilke, C. Zhuo, "The ISPD-2012 Discrete Cell Sizing Contest and Benchmark Suite", ISPD 2012, pp. 161--164.
114. M. Pan, C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement", ICCAD 2006, pp. 59--62.
115. M. Pan, N. Viswanathan, C. Chu, "An Efficient and Effective Detailed Placement Algorithm", ICCAD 2005, pp. 48--55.
116. D. A. Papa, S. Krishnaswamy, I. L. Markov, "SPIRE: A Retiming-based Physical-synthesis Transformation System", ICCAD 2010, pp. 373--380.
117. D. A. Papa, M. D. Moffitt, C. J. Alpert, I. L. Markov, "Speeding Up Physical Synthesis with Transactional Timing Analysis", Design and Test 27(5) 2010, pp. 14--25.
118. D. A. Papa et al., "RUMBLE: An Incremental, Timing-driven, Physical-synthesis Optimization Algorithm", TCAD 27(12) 2008, pp. 2156--2168.
119. D. A. Papa, N. Viswanathan, C. N. Sze, Z. Li, G.-J. Nam, C. J. Alpert, I. L. Markov, "Physical Synthesis with Clock-Network Optimization for Large Systems on Chips", Micro 31(4) 2011, pp. 51--62.
120. P. N. Parakh, R. B. Brown, K. A. Sakallah, "Congestion Driven Quadratic Placement", DAC 1998, pp. 275--278.
121. S. Plaza, I. L. Markov, V. Bertacco, "Optimizing Non-Monotonic Interconnect using Functional Simulation and Logic Restructuring", TCAD 27(12) 2008, pp. 2107--2119.
122. R. Puri, L. Stok, S. Bhattacharya, "Keeping Hot Chips Cool", DAC 2005, pp. 285--288.
123. R. Puri et al., "Pushing ASIC Performance in a Power Envelope", DAC 2003, pp. 788--793.
124. K. Rajagopal et al., "Timing Driven Force Directed Placement with Physical Net Constraints", ISPD 2003, pp. 60--66.
125. B. M. Reiss, G. G. Ettelt, "SPEED: Fast and Efficient Timing Driven Placement", ISCAS 1995, pp. 377--380.
126. H. Ren, D. Z. Pan, C. J. Alpert, P. G. Villarrubia, "Diffusion-based Placement Migration", DAC 2005, pp. 515--520.
127. H. Ren, D. Z. Pan, C. J. Alpert, G.-J. Nam, P. G. Villarrubia, "Hippocrates: First-Do-No-Harm Detailed Placement", ASPDAC 2007, pp. 141--146.
128. H. Ren, D. Z. Pan, D. S. Kung, "Sensitivity Guided Net Weighting for Placement Driven Synthesis", TCAD 24(5) 2005, pp. 711--721.
129. J. A. Roy, S. N. Adya, D. A. Papa, I. L. Markov, "Min-cut Floorplacement", TCAD 25(7) 2006, pp. 1313--1326.
130. J. A. Roy, I. L. Markov, "Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement", TCAD 23(4) 2007, pp. 632--644.
131. J. A. Roy, I. L. Markov, "ECO-System: Embracing the Change in Placement", TCAD 26(12) 2007, pp. 2173--2185.
132. J. A. Roy, A. N. Ng, R. Aggarwal, V. Ramachandran, I. L. Markov, "Solving Modern Mixed-size Placement Instances", Integration 42(2) 2009, pp. 262--275.
133. J. A. Roy et al., "Capo: Robust and Scalable Open-source Min-Cut Floorplacer", ISPD 2005, pp. 224--226, vlsicad.eecs.umich.edu/BK/PDtools/.
134. J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, I. L. Markov, "CRISP: Congestion Reduction by Iterated Spreading during Placement", ICCAD 2009, pp. 357--362.
135. A. E. Ruehli, P. K. Wolff, G. Goertzel, "Analytical Power/Timing Optimization Technique for Digital Systems", DAC 1977, pp. 142--146.
136. S. M. Sait, M. R. Minhas, J. A. Khan, "Performance and Low Power Driven VLSI Standard Cell Placement using Tabu Search", Congress on Evolutionary Computation, 2002, pp. 372--377.
137. M. Sarrafzadeh, M. Wang, "NRG: Global and Detailed Placement", ICCAD 1997, p. 532--537.
138. P. Saxena, "On Controlling Perturbation Due to Repeaters during Quadratic Placement", TCAD 25(9) 2006, pp. 1733--1743.
139. N. Selvakkumaran, P. N. Parakh, G. Karypis, "Perimeter-degree: A Priori Metric for Directly Measuring and Homogenizing Interconnection Complexity in Multilevel Placement", SLIP 2003, pp. 53--59.
140. W. Shen, Y. Cai, X. Hong, J. Hu, "Activity and Register Placement Aware Gated Clock Network Design", ISPD 2008, pp. 182--189.
141. R. E. Showalter, "Monotone Operators in Banach Space and Nonlinear Partial Differential Equations", Mathematical Surveys and Monographs 49. Providence, RI: American Mathematical Society, 1997, pp. 162--163.
142. G. Sigl, K. Doll, F. Johannes, "Analytical Placement: A Linear or a Quadratic Objective Function?" DAC 1991, pp. 427--432.
143. P. Spindler, F. M. Johannes, "Fast and Accurate Routing Demand Estimation for Efficient Routability-driven Placement", DATE 2007, pp. 1226--31.
144. P. Spindler, U. Schlichtmann, F. M. Johannes, "Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement", ISPD 2008, pp. 47--53.
145. P. Spindler, U. Schlichtmann, F. M. Johannes, "Kraftwerk2 - A Fast Force-directed Quadratic Placement Approach using an Accurate Net Model", TCAD 27(8) 2008, pp. 1398--1411.
146. A. Srinivasan, K. Chaudhary, E. S. Kuh, "Ritual: A Performance Driven Placement Algorithm for Small Cell ICs", ICCAD 1991, pp. 48--51.
147. W. Swartz, C. Sechen, "Timing Driven Placement for Large Standard Cell Circuits", DAC 1995, pp. 211--215.
148. H. Tennakoon, C. Sechen, "Nonconvex Gate Delay Modeling and Delay Optimization", TCAD 27(9) 2003, pp. 1583--1594.
149. M. Terai, K. Takahashi, K. Sato, "A New Min-cut Placement Algorithm for Timing Assurance Layout Design Meeting Net Length Constraint", DAC 1990, pp. 96--102.
150. L. Trevillyan, D. Kung, R. Puri, L. N. Reddy, M. A. Kazda, "An Integrated Environment for Technology Closure of Deep-Submicron IC Designs", Design and Test 21(1) 2004, pp. 14--22.
151. R. S. Tsay, J. Koehl, "An Analytic Net Weighting Approach for Performance Optimization in Circuit Placement", DAC 1991, pp. 636--639.
152. K. Tsota, C. Koh, V. Balakrishnan, "Guiding Global Placement with Wire Density", ICCAD 2008, pp. 212--217.
153. H. Vaishnav, M. Pedram, "PCUBE: A Performance Driven Placement Algorithm for Low Power Designs", DAC with EURO-VHDL, 1993, pp. 72--77.
154. L. P. P. P. van Ginneken, "Buffer Placement in Distributed RC-tree Network for Minimal Elmore Delay", ISCAS 1990, pp. 865--868.
155. N. Viswanathan, C. J. Alpert, Z. Li, G.-J. Nam, J. A. Roy, "The ISPD-2011 Routability-driven Placement Contest and Benchmark Suite", ISPD 2011, pp. 141--146.
156. N. Viswanathan, C. J. Alpert, C. N. Sze, Z. Li, Y. Wei, "The DAC 2012 Routability-driven Placement Contest and Benchmark Suite", DAC 2012, pp. 774--782.
157. N. Viswanathan, M. Pan, C. Chu, "FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control", ASPDAC 2007, pp. 135--140.
158. N. Viswanathan, G.-J. Nam, C. J. Alpert, P. G. Villarrubia, H. Ren, "RQL: Global Placement via Relaxed Quadratic Spreading and Linearization", DAC 2007, pp. 453--458.
159. M. Vujkovic, D. Wadkins, B. Swartz, C. Sechen, "Efficient Timing Closure without Timing Driven Placement and Routing", DAC 2004, pp. 268--73.
160. S. Ward, D. Ding, D. Z. Pan, "PADE: A High-performance Placer with Automatic Datapath Extraction and Evaluation Through High Dimensional Data Learning", DAC 2012, pp. 756--761.
161. M. Wang, M. Sarrafzadeh, "On the Behaviour of Congestion Minimization during Placement", ISPD 1999, pp. 145--150.
162. M. Wang, M. Sarrafzadeh, "Model and Minimization of Routing Congestion", ASPDAC 2000, pp. 185--190.
163. M. Wang X. Yang, M. Sarrafzadeh, "Congestion Minimization during Placement", in TCAD 19(10) 2000, pp. 1140--1148.
164. M. Wang, X. Yang, K. Eguro, M. Sarrafzadeh, "Multicenter Congestion Estimation and Minimization during Placement", ISPD 2000, pp. 147--152.
165. Y. Wang, Q. Zhou, X. Hong, Y. Cai, "Clock-tree Aware Placement Based on Dynamic Clock-tree Building", ISCAS 2007, pp. 2040--2043.
166. E. Wein, J. Benkoski, "Hard Macros Will Revolutionize SoC Design", EE Times Online, August 20, 2004. http://www.eetimes.com/news/design/showArtical.jhtml?articalID=26807055
167. J. Werber, D. Rautenbach, C. Szegedy, "Timing Optimization by Restructuring Long Combinatorial Paths", ICCAD 2007, pp. 536--543.
168. J. Westra, C. Bartels, P. Groeneveld, "Probabilistic Congestion Prediction", ISPD 2004, pp. 204--209.
169. J. Westra, P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?" SLIP 2005, pp. 99--106.
170. B. P. Wong, A. Mittal, G. W. Starr, F. Zach, V. Moroz, A. Kahng, Nano-CMOS Design for Manufacturability, John Wiley and Sons 2009.
171. H. Xiang, H. Ren, L. Trevillyan, L. Reddy, R. Puri, M. Cho, "Logical and Physical Restructuring of Fan-in Trees", ISPD 2010, pp. 67--74.
172. Zhong Xiu, R. Rutenbar, "Timing-driven Placement by Grid-warping", DAC 2005, pp. 585--590.
173. Y. Xu, Y. Zhang, C. Chu, "FastRoute 4.0: Global Router with Efficient Via Minimization", ASPDAC 2009, pp. 576--581.
174. J. Z. Yan, N. Viswanathan, C. Chu, "Handling Complexities in Modern Large-scale Mixed-size Placement", DAC 2009, pp. 436--441.
175. X. Yang, B.-K. Choi, M. Sarrafzadeh, "Routability-driven White Space Allocation for Fixed-die Standard-cell Placement", TCAD 22(4) 2003, pp. 410--419.
176. C. Yeh, Y. Kang, S. Shieh, J. Wang, "Layout Techniques Supporting the Use of Dual Supply Voltages for Cell-based Designs", DAC 1999, pp. 62--67.
177. H. Youssef, E. Shragowitz, "Timing Constraints for Correct Peformance", ICCAD 1990, pp. 24--27.
178. Y. Zhang, C. Chu, "CROP: Fast and Effective Congestion Refinement of Placement", ICCAD 2009, pp. 344--350.
179. K. Zhong, S. Dutt, "Algorithms for Simultaneous Satisfaction of Multiple Constraints and Objective Optimization in a Placement Flow with Application to Congestion Control", DAC 2002, pp. 854--859.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing

  • Very large scale integration design