research-article

Progress and challenges in VLSI placement research

Authors:

Igor L. Markov,

Myung-Chul KimAuthors Info & Claims

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

Pages 275 - 282

https://doi.org/10.1145/2429384.2429441

Published: 05 November 2012 Publication History

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.

Digital Library

[2]

S. N. Adya, I. L. Markov, P. G. Villarrubia, "On Whitespace and Stability in Physical Synthesis", Integration 39(4) 2006, pp. 340--362.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[7]

C. J. Alpert, Z. Li, G.-J. Nam, C. N. Sze, N. Viswanathan, S. Ward, "Placement: Hot or Not?" ICCAD 2012.

Digital Library

[8]

C. J. Alpert, D. P. Mehta, S. S. Sapatnekar (eds.), Handbook of Algorithms for VLSI Physical Design Automation, CRC Press 2008.

Digital Library

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

Digital Library

[11]

U. Brenner, J. Vygen, "Faster Optimal Single-row Placement with Fixed Ordering", DATE 2000, pp. 117--121.

Digital Library

[12]

U. Brenner, J. Vygen, "Legalizing a Placement with Minimum Total Movement", TCAD 23(12) 2004, pp. 1597--1613.

Digital Library

[13]

U. Brenner, M. Struzyna, J. Vygen, "BonnPlace: Placement of Leading-edge Chips by Advanced Combinatorial Algorithms", TCAD 27(9) 2008, pp. 1607--1620.

Digital Library

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

Digital Library

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

Digital Library

[17]

A. E. Caldwell, A. B. Kahng, I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?" DAC 2000, pp. 477--482.

Digital Library

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

Digital Library

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

Digital Library

[20]

T. F. Chan, J. Cong, K. Sze, "Multilevel Generalized Force-directed Method for Circuit Placement", ISPD 2005, pp. 185--192.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[25]

C. Chang, J. Cong, X. Yuan, "Multi-level Placement for Large-scale Mixed-size IC Design", ASPDAC 2003, pp. 325--330.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[30]

C. E. Cheng, "RISA: Accurate and Efficient Placement Routability Modeling", ICCAD 1994, pp. 650--695.

Digital Library

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

Digital Library

[32]

Y. Cheon, P.-H. Ho, A. B. Kahng, S. Reda, Q. Wang, "Power-aware Placement", DAC 2005, pp. 795--800.

Digital Library

[33]

M.-F. Chiang, T. Okamoto, T. Yoshimura, "Register Placement for High-performance Circuits", DATE 2009, pp. 1470--1475.

Digital Library

[34]

M. Cho, H. Ren, H. Xiang, R. Puri, "History-based VLSI Legalization using Network Flow", DAC 2010, pp. 286--291.

Digital Library

[35]

W. Choi, K. Bazargan, "Hierarchical Global Floorplacement using Simulated Annealing and Network Flow Area Migration", DATE 2003, pp. 1104--5.

Digital Library

[36]

S. Chou, M.-K. Hsu, Y.-W. Chang, "Structure-aware Placement for Datapath-intensive Circuit Designs", DAC 2012, pp. 762--767.

Digital Library

[37]

A. Chowdhary et al., "How Accurately Can We Model Timing in a Placement Engine", DAC 2005, pp. 801--806.

Digital Library

[38]

C. Chu, M. Pan, "IPR: An Integrated Placement and Routing Algorithm", DAC 2007, pp. 59--62.

Digital Library

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

Digital Library

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

Digital Library

[41]

J. Cong, B. Liu, G. Luo, R. Prabhakar, "Towards Layout-friendly High-level Synthesis", ISPD 2012, pp. 165--172.

Digital Library

[42]

J. Cong, G. Luo, E. Radke, "Highly Efficient Gradient Computation for Density-constrained Analytical Placement", TCAD 27(12) 2008, pp. 2133--44.

Digital Library

[43]

J. Cong, J. R. Shinnerl, M. Xie, T. Kong, X. Yuan, "Large-scale Circuit Placement", TODAES 10(2) 2005, pp. 389--430.

Digital Library

[44]

J. Cong, M. Xie, "A Robust Detailed Placement for Mixed-size IC Designs", ASPDAC 2006, pp. 188--194.

Digital Library

[45]

J. Cong, M. Romesis, J. R. Shinnerl, "Robust Mixed-size Placement Under Tight White-space Constraints", ICCAD 2005, pp. 165--172.

Digital Library

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

Digital Library

[47]

K. Doll, F. M. Johannes, K. J. Antreich, "Iterative Placement Improvement by Network Flow Methods", TCAD 13(10) 1994, pp. 1189--1200.

Digital Library

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

Digital Library

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

Digital Library

[50]

H. Eisenmann, F. M. Johannes, "Generic Global Placement and Floorplanning", DAC 1998, pp. 269--274.

Digital Library

[51]

T. Gao, P. M. Vaidya, C. L. Liu, "A Performance Driven Macro-cell Placement Algorithm", DAC 1992, pp. 147--152.

Digital Library

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

Digital Library

[53]

B. Halpin, C. Y. R. Chen, N. Sehgal, "A Sensitivity Based Placer for Standard Cells", GSLVLSI, 2000, pp. 193--196.

Digital Library

[54]

B. Halpin, C. Y. R. Chen, N. Sehgal, "Timing Driven Placement using Physical Net Constraints", DAC 2001, pp. 780--783.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[62]

M.-K. Hsu, Y.-W. Chang, "Unified Analytical Global Placement for Large-scale Mixed-size Circuit Designs", ICCAD 2010, pp. 657--662.

Digital Library

[63]

M.-K. Hsu, Y.-W. Chang, V. Balabanov, "TSV-aware Analytical Placement for 3D IC Designs", DAC 2011, pp. 664--669.

Digital Library

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

Digital Library

[65]

B. Hu, M. Marek-Sadowska, "Congestion Minimization during Placement without Estimation", ICCAD 2002, pp. 739--745.

Digital Library

[66]

B. Hu, M. Marek-Sadowska, "Multilevel Fixed-point-addition-based VLSI Placement", TCAD 24(8) 2005, pp. 1188--1203.

Digital Library

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

Digital Library

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

Digital Library

[69]

J. Hu, J. A. Roy, I. L. Markov, "Completing High-quality Routes", ISPD 2010, pp. 35--41.

Digital Library

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

Digital Library

[72]

S.-W. Hur, J. Lillis, "Mongrel: Hybrid Techniques for Standard Cell Placement", ICCAD 2000, pp. 165--170.

Digital Library

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

Digital Library

[75]

D. Jariwala, J. Lillis, "RBI: Simultaneous Placement and Routing Optimization Technique", TCAD 26(1) 2007, pp. 127--141.

Digital Library

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

Digital Library

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

Digital Library

[78]

A. B. Kahng, "Classical Floorplanning Harmful?" ISPD 2000, pp. 207--213.

Digital Library

[79]

A. B. Kahng, J. Lienig, I. L. Markov, J. Hu, "VLSI Physical Design: From Graph Partitioning to Timing Closure", Springer 2011.

Digital Library

[80]

A. B. Kahng, I. L. Markov, S. Reda, "On Legalization of Row-based Placements", GSLVLSI, 2004, pp. 214--219.

Digital Library

[81]

A. B. Kahng, C.-H. Park, P. Sharma, Q. Wang, "Lens Aberration Aware Placement for Timing Yield", TODAES 14(1) 2009, no. 16.

Digital Library

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

Digital Library

[84]

J. Knechtel, I. L. Markov, J. Lienig, "Assembling 2-D Blocks Into 3-D Chips", TCAD 31(2) 2012, pp. 228--241.

Digital Library

[85]

M.-C. Kim, D.-J. Lee, I. L. Markov, "SimPL: An Effective Placement Algorithm", ICCAD 2010, pp. 649--656.

Digital Library

[86]

M.-C. Kim, J. Hu, D.-J. Lee, I. L. Markov, "A SimPLR Method for Routability-driven Placement", ICCAD 2011, pp. 67--73.

Digital Library

[87]

M.-C. Kim, D.-J. Lee, I. L. Markov, "SimPL: An Effective Placement Algorithm", TCAD 31(1) 2012, pp. 50--60.

Digital Library

[88]

M.-C. Kim, I. L. Markov, "ComPLx: A Competitive Primal-dual Lagrange Optimization for Global Placement", DAC 2012, pp. 747--752.

Digital Library

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

Digital Library

[90]

T. Kong, "A Novel Net Weighting Algorithm for Timing-driven Placement", ICCAD 2002, pp. 172--176.

Digital Library

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

Digital Library

[92]

D.-J. Lee, I. L. Markov, "Obstacle-aware Clock-tree Shaping during Placement", TCAD 31(2) 2012, pp. 205--216.

Digital Library

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

Digital Library

[94]

C. Li, C.-K. Koh, "Recursive Function Smoothing of Half-perimeter Wirelength for Analytical Placement", ISQED, 2007, pp. 829--834.

Digital Library

[95]

C. Li, C.-K. Koh, P. H. Madden, "Floorplan Management: Incremental Placement for Gate Sizing and Buffer Insertion", ASPDAC 2005, pp. 349--54.

Digital Library

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

Digital Library

[97]

S. Li, C.-K. Koh, "Mixed Integer Programming Models for Detailed Placement", ISPD 2012, pp. 87--94.

Digital Library

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

Digital Library

[99]

Z. Li, W. Wu, X. Hong, "Congestion Driven Incremental Placement Algorithm for Standard Cell Layout", ASPDAC 2003, pp. 723--728.

Digital Library

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

Digital Library

[101]

W. K. Luk, "A Fast Physical Constraint Generator for Timing Driven Placement", DAC 1991, pp. 626--631.

Digital Library

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

Digital Library

[103]

T. Luo, D. Z. Pan, "DPlace2.0: A Stable and Efficient Analytical Placement Based on Diffusion", ASPDAC 2008, pp. 346--351.

Digital Library

[104]

T. Luo, H. Ren, C. J. Alpert, D. Z. Pan, "Computational Geometry Based Placement Migration", DAC 2007, pp. 41--47.

Digital Library

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

Digital Library

[106]

N. Magen, A. Kolodny, U. Weiser, N. Shamir, "Interconnect-power Dissipation in a Microprocessor", SLIP 2004, pp. 7--13.

Digital Library

[107]

M. D. Moffitt, J. A. Roy, I. L. Markov, M. E. Pollack, "Constraint-driven Floorplan Repair", TODAES 13(4) 2008, pp. 1--13.

Digital Library

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

Digital Library

[109]

G.-J. Nam, J. Cong, Modern Circuit Placement: Best Practices and Results, Springer 2007.

Digital Library

[110]

B. Obermeier, F. M. Johannes, "Temperature-aware Global Placement", ASPDAC 2004, pp. 143--148.

Digital Library

[111]

B. Obermeier, H. Ranke, F. M. Johannes, "Kraftwerk: a Versatile Placement Approach", ISPD 2005, pp. 242--244.

Digital Library

[112]

M. Orshansky, S. Nassif, D. Boning, Design for Manufacturability and Statistical Design: A Constructive Approach (Integrated Circuits and Systems), Springer 2010.

Digital Library

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

Digital Library

[114]

M. Pan, C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement", ICCAD 2006, pp. 59--62.

Digital Library

[115]

M. Pan, N. Viswanathan, C. Chu, "An Efficient and Effective Detailed Placement Algorithm", ICCAD 2005, pp. 48--55.

Digital Library

[116]

D. A. Papa, S. Krishnaswamy, I. L. Markov, "SPIRE: A Retiming-based Physical-synthesis Transformation System", ICCAD 2010, pp. 373--380.

Digital Library

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

Digital Library

[118]

D. A. Papa et al., "RUMBLE: An Incremental, Timing-driven, Physical-synthesis Optimization Algorithm", TCAD 27(12) 2008, pp. 2156--2168.

Digital Library

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

Digital Library

[120]

P. N. Parakh, R. B. Brown, K. A. Sakallah, "Congestion Driven Quadratic Placement", DAC 1998, pp. 275--278.

Digital Library

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

Digital Library

[122]

R. Puri, L. Stok, S. Bhattacharya, "Keeping Hot Chips Cool", DAC 2005, pp. 285--288.

Digital Library

[123]

R. Puri et al., "Pushing ASIC Performance in a Power Envelope", DAC 2003, pp. 788--793.

Digital Library

[124]

K. Rajagopal et al., "Timing Driven Force Directed Placement with Physical Net Constraints", ISPD 2003, pp. 60--66.

Digital Library

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

Digital Library

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

Digital Library

[128]

H. Ren, D. Z. Pan, D. S. Kung, "Sensitivity Guided Net Weighting for Placement Driven Synthesis", TCAD 24(5) 2005, pp. 711--721.

Digital Library

[129]

J. A. Roy, S. N. Adya, D. A. Papa, I. L. Markov, "Min-cut Floorplacement", TCAD 25(7) 2006, pp. 1313--1326.

Digital Library

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

Digital Library

[131]

J. A. Roy, I. L. Markov, "ECO-System: Embracing the Change in Placement", TCAD 26(12) 2007, pp. 2173--2185.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[135]

A. E. Ruehli, P. K. Wolff, G. Goertzel, "Analytical Power/Timing Optimization Technique for Digital Systems", DAC 1977, pp. 142--146.

Digital Library

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

Digital Library

[138]

P. Saxena, "On Controlling Perturbation Due to Repeaters during Quadratic Placement", TCAD 25(9) 2006, pp. 1733--1743.

Digital Library

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

Digital Library

[140]

W. Shen, Y. Cai, X. Hong, J. Hu, "Activity and Register Placement Aware Gated Clock Network Design", ISPD 2008, pp. 182--189.

Digital Library

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

Digital Library

[143]

P. Spindler, F. M. Johannes, "Fast and Accurate Routing Demand Estimation for Efficient Routability-driven Placement", DATE 2007, pp. 1226--31.

Digital Library

[144]

P. Spindler, U. Schlichtmann, F. M. Johannes, "Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement", ISPD 2008, pp. 47--53.

Digital Library

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

Digital Library

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

Digital Library

[148]

H. Tennakoon, C. Sechen, "Nonconvex Gate Delay Modeling and Delay Optimization", TCAD 27(9) 2003, pp. 1583--1594.

Digital Library

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

Digital Library

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

Digital Library

[151]

R. S. Tsay, J. Koehl, "An Analytic Net Weighting Approach for Performance Optimization in Circuit Placement", DAC 1991, pp. 636--639.

Digital Library

[152]

K. Tsota, C. Koh, V. Balakrishnan, "Guiding Global Placement with Wire Density", ICCAD 2008, pp. 212--217.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[159]

M. Vujkovic, D. Wadkins, B. Swartz, C. Sechen, "Efficient Timing Closure without Timing Driven Placement and Routing", DAC 2004, pp. 268--73.

Digital Library

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

Digital Library

[161]

M. Wang, M. Sarrafzadeh, "On the Behaviour of Congestion Minimization during Placement", ISPD 1999, pp. 145--150.

Digital Library

[162]

M. Wang, M. Sarrafzadeh, "Model and Minimization of Routing Congestion", ASPDAC 2000, pp. 185--190.

Digital Library

[163]

M. Wang X. Yang, M. Sarrafzadeh, "Congestion Minimization during Placement", in TCAD 19(10) 2000, pp. 1140--1148.

Digital Library

[164]

M. Wang, X. Yang, K. Eguro, M. Sarrafzadeh, "Multicenter Congestion Estimation and Minimization during Placement", ISPD 2000, pp. 147--152.

Digital Library

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

Digital Library

[168]

J. Westra, C. Bartels, P. Groeneveld, "Probabilistic Congestion Prediction", ISPD 2004, pp. 204--209.

Digital Library

[169]

J. Westra, P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?" SLIP 2005, pp. 99--106.

Digital Library

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

Digital Library

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

Digital Library

[172]

Zhong Xiu, R. Rutenbar, "Timing-driven Placement by Grid-warping", DAC 2005, pp. 585--590.

Digital Library

[173]

Y. Xu, Y. Zhang, C. Chu, "FastRoute 4.0: Global Router with Efficient Via Minimization", ASPDAC 2009, pp. 576--581.

Digital Library

[174]

J. Z. Yan, N. Viswanathan, C. Chu, "Handling Complexities in Modern Large-scale Mixed-size Placement", DAC 2009, pp. 436--441.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

Cited By

Nikolić SNikolić S(2025)Dedicated Placement for Fixed-Connectivity PatternsModern Programmable Interconnect Design10.1007/978-3-031-80629-2_8(237-282)Online publication date: 7-Mar-2025
https://doi.org/10.1007/978-3-031-80629-2_8
Geng ZWang JLiu ZXu STang ZYuan MHao JZhang YWu FSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Reinforcement learning within tree search for fast macro placementProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692687(15402-15417)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692687
Yu SDu SYang C(2024)A Deep Reinforcement Learning Floorplanning Algorithm Based on Sequence PairsApplied Sciences10.3390/app1407290514:7(2905)Online publication date: 29-Mar-2024
https://doi.org/10.3390/app14072905
Show More Cited By

Index Terms

Progress and challenges in VLSI placement research
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Very large scale integration design

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

November 2012

781 pages

ISBN:9781450315739

DOI:10.1145/2429384

General Chair:
Alan J. Hu
Univ. of British Columbia, Vancouver, BC, Canada

Copyright © 2012 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 ACM 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

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICCAD '12

Sponsor:

SIGDA

ICCAD '12: The International Conference on Computer-Aided Design

November 5 - 8, 2012

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
509
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)7

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nikolić SNikolić S(2025)Dedicated Placement for Fixed-Connectivity PatternsModern Programmable Interconnect Design10.1007/978-3-031-80629-2_8(237-282)Online publication date: 7-Mar-2025
https://doi.org/10.1007/978-3-031-80629-2_8
Geng ZWang JLiu ZXu STang ZYuan MHao JZhang YWu FSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Reinforcement learning within tree search for fast macro placementProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692687(15402-15417)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692687
Yu SDu SYang C(2024)A Deep Reinforcement Learning Floorplanning Algorithm Based on Sequence PairsApplied Sciences10.3390/app1407290514:7(2905)Online publication date: 29-Mar-2024
https://doi.org/10.3390/app14072905
Tan ZMu Y(2024)Hierarchical reinforcement learning for chip-macro placement in integrated circuitPattern Recognition Letters10.1016/j.patrec.2024.02.002179(108-114)Online publication date: Mar-2024
https://doi.org/10.1016/j.patrec.2024.02.002
Zou JWang XGuo JLiu WZhang QHuang COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Circuit as set of pointsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667532(32468-32480)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667532
Shi YXue KSong LQian COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Macro placement by wire-mask-guided black-box optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666421(6825-6843)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666421
Gandhi VPatel YSoni BJoshi G(2023)Power Budget Improvement Using Floorplan Methodologies In Lower(28nm) Technology Node2023 IEEE International Symposium on Smart Electronic Systems (iSES)10.1109/iSES58672.2023.00088(397-400)Online publication date: 18-Dec-2023
https://doi.org/10.1109/iSES58672.2023.00088
Yang HChen JCai ZGuo JGuo Y(2023)Multi-instantiated Block Top-layer Routing Technique Based on Steiner Tree Algorithm2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218543(274-279)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218543
Jeevan BBikshalu KHari krishna ESivani K(2023)Design of 2-1 Multiplexer based high-speed, Two-Stage 90 nm Carry Select Adder for fast arithmetic unitsMicroprocessors and Microsystems10.1016/j.micpro.2023.10484699(104846)Online publication date: Jun-2023
https://doi.org/10.1016/j.micpro.2023.104846
Liao PLiu SChen ZLv WLin YYu B(2022)DREAMPlace 4.0: Timing-driven Global Placement with Momentum-based Net Weighting2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774725(939-944)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774725
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten