Large-Scale Circuit Placement: Gap and Promise

ABSTRACT

Placement is one of the most important steps in the RTL-to-GDSII synthesis process, as it directly defines the interconnects, which have become the bottleneck in circuit andsystem performance in deep submicron technologies. Theplacement problem has been studied extensively in the past30 years. However, recent studies show that existing placement solutions are surprisingly far from optimal. The first part of this tutorial summarizes results from recent optimality and scalability studies of existing placement tools. Thesestudies show that the results of leading placement tools fromboth industry and academia may be up to 50% to 150% awayfrom optimal in total wirelength. If such a gap can be closed,the corresponding performance improvement will be equivalent to several technology-generation advancements. Thesecond part of the tutorial highlights the recent progress onlarge-scale circuit placement, including techniques for wirelength minimization, routability optimization, and performance optimization.

References

1. {1} http://cadlab.cs.ucla.edu/~pubbench.
2. {2} S. N. Adya, M. Yildiz, I. L. Markov, P. G. Villarrubia, P. N. Parakh, and P. H. Madden. Benchmarking for large-scale placement and beyond. In Proc. Intl. Symp. on Physical Design (ISPD), pages 95-103, 2003.
3. {3} C. J. Alpert. The ispd98 circuit benchmark suite. In Proc. International Symposium on Physical Design, pages 85-90, 1998.
4. {4} A. Brandt and D. Ron. Multigrid Solvers and Multilevel Optimization Strategies, chapter 1 of Multilevel Optimization and VLSICAD. Kluwer Academic Publishers, Boston, 2002.
5. {5} U. Brenner and A. Rohe. An effective congestion-driven placement framework. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(4):387-394, April 2003.
6. {6} U. Brenner and A. Rohe. An effective congestion-driven placement framework. In Proc. International Symposium on Physical Design, Apr 2002.
7. {7} M. Breuer. Min-cut placement. J. Design Automat. Fault Tolerant Comp., 1(4):343-362, Oct 1977.
8. {8} W. L. Briggs, V. E. Henson, and S. F. McCormick. A Multigrid Tutorial. SIAM, Philadelphia, second edition, 2000.
9. {9} M. Burstein and M. N. Youssef. Timing influenced layout design. In Proc. ACM/IEEE Design Automation Conference, pages 124-130, 1985.
10. {10} Cadence Design Systems, Inc. Envisia ultra placer reference. QPlace version 5.1.55, compiled on 10/25/1999.
11. {11} A. Caldwell, A.B. Kahng, and I. Markov. Optimal partitioners and end-case placers for standard-cell layout. IEEE Trans. on CAD, 19(11):1304-1314, 2000.
12. {12} A. Caldwell, A. Kahng, and I. Markov. Can recursive bisection alone produce routable placements? In Proc. 37th IEEE/ACM Design Automation Conf., 2000.
13. {13} T. Chan, J. Cong, T. Kong, and J. Shinnerl. Multilevel optimization for large-scale circuit placement. In Proc. IEEE International Conference on Computer Aided Design, pages 171-176, San Jose, CA, Nov 2000.
14. {14} T. Chan, J. Cong, T. Kong, J. Shinnerl, and K. Sze. An enhanced multilevel algorithm for circuit placement. In Proc. IEEE International Conference on Computer Aided Design, San Jose, CA, Nov 2003.
15. {15} C.-C. Chang, J. Cong, D. Pan, and X. Yuan. Multilevel global placement with congestion control. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(4):395-409, April 2003.
16. {16} C.C. Chang, J. Cong, and M. Xie. Optimality and scalability study of existing placement algorithms. In Proc. Asia South Pacific Design Automation Conference, pages 621-627, 2003.
17. {17} C.-C. Chang, J. Lee, M. Stabenfeldt, and R.S. Tsay. A practical all-path timing-driven place and route design system. In Proc. Asia-Pacific Conference on Circuits and Systems, pages 560-563, 1994.
18. {18} C. Chen, X. Yang, and M. Sarrafzadeh. Potential slack: An effective metric of combinational circuit performance. In IEEE/ACM International Conference on Computer-Aided Design, pages 198-201, 2000.
19. {19} H. Chen, C.-K. Cheng, N.-C. Chou, A. Kahng, J. MacDonald, P. Suaris, B. Yao, and Z. Zhu. An algebraic multigrid solver for analytical placement with layout-based clustering. In Proc. IEEE/ACM Design Automation Conf., pages 794-799, 2003.
20. {20} C. Cheng and E. Kuh. Module placement based on resistive network optimization. IEEE Transactions on Computer-Aided Design, CAD-3(3), Jul 1984.
21. {21} C.-L. E. Cheng. RISA: accurate and efficient placement routability modeling. In Proc. Int. Conf. on Computer Aided Design, pages 690-695, Nov. 1994.
22. {22} J. Cong. An interconnect-centric design flow for nanometer technologies. Proceedings of the IEEE, 89(4):505-527, April 2001.
23. {23} J. Cong and S. K. Lim. Edge separability based circuit clustering with application to circuit partitioning. In Asia South Pacific Design Automation Conference, Yokohama Japan, pages 429-434, 2000.
24. {24} J. Cong, M. Romesis, and M. Xie. Optimality, scalability and stability study of partitioning and placement algorithms. In Proc. International Symposium on Physical Design, pages 88-94, 2003.
25. {25} J. Cong, M. Romesis, and M. Xie. Optimality and stability of timing-driven placement algorithms. In Proc. IEEE International Conference on Computer Aided Design, San Jose, CA, Nov 2003.
26. {26} J. Cong and J. R. Shinnerl, editors. Multilevel Optimization in VLSICAD. Kluwer Academic Publishers, Boston, 2003.
27. {27} A. Dunlop and B. Kernighan. A procedure for placement of standard-cell vlsi circuits. IEEE Transactions on Computer-Aided Design, CAD-4(1), Jan 1985.
28. {28} A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F. Jukl, P. Kozak, and M. Wiesel. Chip layout optimization using critical path weighting. In Proc. ACM/IEEE Design Automation Conference, pages 133-136, 1984.
29. {29} H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proc. 35th ACM/IEEE Design Automation Conference, pages 269-274, 1998.
30. {30} T. Gao, P. M. Vaidya, and C. L. Liu. A new performance driven placement algorithm. In IEEE/ACM International Conference on Computer-Aided Design, pages 44-47, 1991.
31. {31} S. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. on Circuits and Systems, 28(1):12-18, January 1981.
32. {32} L. W. Hagen, D. J.-H. Huang, and A. B. Kahng. Quantified suboptimality of vlsi layout heuristics. In Proc. Design Automation Conference, pages 216-221, 1995.
33. {33} B. Halpin, C. Chen, and N. Sehgal. Timing driven placement using physical net constraints. In Proc. ACM/IEEE Design Automation Conference, pages 780-783, 2001.
34. {34} T. Hamada, C. K. Cheng, and P. M. Chau. Prime: a timing-driven placement tool using a piecewise linear resistive network approach. In Proc. ACM/IEEE Design Automation Conference, pages 531-536, 1993.
35. {35} P. S. Hauge, R. Nair, and E. J. Yoffa. Circuit placement for predictable performance. In IEEE/ACM International Conference on Computer-Aided Design, pages 88-91, 1987.
36. {36} B. Hu and M. Marek-Sadowska. Congestion minimization during placement without estimation. In Proc. Int. Conf. on Computer Aided Design, pages 739-745, Nov. 2002.
37. {37} B. Hu and M. Marek-Sadowska. Fine granularity clustering for large-scale placement problems. In Proc. Design Automation Conference, pages 67-74, Jun. 2003.
38. {38} S.-W. Hur and J. Lillis. Mongrel: Hybrid techniques for standard-cell placement. In Proc. IEEE International Conference on Computer Aided Design, pages 165-170, San Jose, CA, Nov 2000.
39. {39} M. Jackson and E. S. Kuh. Performance-driven placement of cell based IC's. In Proc. ACM/IEEE Design Automation Conference, pages 370-375, 1989.
40. {40} G. Karypis. Multilevel Hypergraph Partitioning, chapter 3 of Multilevel Optimization and VLSICAD. Kluwer Academic Publishers, Boston, 2002.
41. {41} J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. Gordian: Vlsi placement by quadratic programming and slicing optimization. IEEE Trans. on Computer-Aided Design, CAD-10:356-365, 1991.
42. {42} T. Kong. A novel net weighting algorithm for timing-driven placement. In IEEE/ACM International Conference on Computer-Aided Design, pages 172-176, 2002.
43. {43} J. Lou, S. Thakur, S. Krishnamoorthy, and H. Sheng. Estimating routing congestion using probabilistic analysis. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 21(1):32-41, January 2002.
44. {44} W. K. Luk. A fast physical constraint generator for timing driven layout. In Proc. ACM/IEEE Design Automation Conference, pages 626-631, 1991.
45. {45} M. Marek-Sadowska and S. P. Lin. Timing driven placement. In IEEE/ACM International Conference on Computer-Aided Design, pages 94-97, 1989.
46. {46} A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In ACM Symposium on FPGAs, pages 203-213, 2000.
47. {47} S. Mayrhofer and U. Lauther. Congestion-driven placement using a new multi-partitioning heuristic. In Proc. Int. Conf. on Computer Aided Design, pages 332-335, 1990.
48. {48} R. Nair, C. L. Berman, P. Hauge, and E. J. Yoffa. Generation of performance constraints for layout. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(8):860-874, 1989.
49. {49} P. N. Parakh, R. B. Brown, and K. A. Sakallah. Congestion driven quadratic placement. In Proc. Design Automation Conference, pages 275-278, 1998.
50. {50} Y. Sankar and J. Rose. Trading quality for compile time: Ultra-fast placement for FPGAs. In FPGA '99, ACM Symp. on FPGAs, pages 157-166, 1999.
51. {51} M. Sarrafzadeh, D. A. Knol, and G. E. Tellez. A delay budgeting algorithm ensuring maximum flexibility in placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(11):1332-1341, 1997.
52. {52} M. Sarrafzadeh, D. A. Knol, and G. E. Tellez. Unification of budgeting and placement. In Proc. ACM/IEEE Design Automation Conference, pages 758-761, 1997.
53. {53} M. Sarrafzadeh, M. Wang, and X. Yang. Modern Placement Techiques. Kluwer Academic Publishers, Boston, 2002.
54. {54} M. Senn, U. Seidl, and F. Johannes. High quality deterministic timing driven FPGA placement. In ACM Symposium on FPGAs, 2002.
55. {55} G. Sigl, K. Doll, and F. M. Johannes. Analytical placement: A linear or a quadratic objective function? In Proc. 28th ACM/IEEE Design Automation Conference, pages 427-432, 1991.
56. {56} A. Srinivasan, K. Chaudhary, and E. S. Kuh. RITUAL: A performance driven placement for small-cell ICs. In IEEE/ACM International Conference on Computer-Aided Design, pages 48-51, 1991.
57. {57} W. Swartz and C. Sechen. Timing-driven placement for large standard cell circuits. In Proc. ACM/IEEE Design Automation Conference, pages 211-215, 1995.
58. {58} G. E. Tellez, D. A. Knol, and M. Sarrafzadeh. A performance-driven placement technique based on a new net budgeting criterion. In International Symposium on Circuits and Systems, pages 504-507, 1996.
59. {59} R. Tsay, E. Kuh, and C. Hsu. Proud: A fast sea-of-gates placement algorithm. IEEE Design and Test of Computers, pages 44-56, 1988.
60. {60} R. S. Tsay and J. Koehl. An analytic net weighting approach for performance optimization in circuit placement. In Proc. ACM/IEEE Design Automation Conference, pages 620-625, 1991.
61. {61} J. Vygen. Algorithms for large-scale flat placement. In Proc. 34th ACM/IEEE Design Automation Conference, pages 746-751, 1997.
62. {62} M. Wang, X. Yang, and M. Sarrafzadeh. Dragon2000: Standard-cell placement tool for large circuits. Proc. IEEE/ACM International Conference on Computer-Aided Design, pages 260-263, Apr 2000.
63. {63} X. Yang, B. Choi, and M. Sarrafzadeh. Timing-driven placement using design hierarchy guided constraint generation. In IEEE/ACM International Conference on Computer-Aided Design, pages 177-180, 2002.
64. {64} X. Yang, B.-K. Choi, and M. Sarrafzadeh. Routability-driven white space allocation for fixed-die standard-cell placement. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(4):410-419, April 2003.
65. {65} X. Yang, R. Kastner, and M. Sarrafzadeh. Congestion estimation during top-down placement. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 21(1):72-80, January 2002.
66. {66} M. C. Yildiz and P. H. Madden. Global objectives for standard cell placement. In Eleventh Great-Lakes Symposium on VLSI, pages 68-72, 2001.
67. {67} M. C. Yildiz and P. H. Madden. Improved cut sequences for partitioning-based placement. In Proc. Design Automation Conference, pages 776-779, 2001.
68. {68} H. Youssef, R. B. Lin, and S. Shragowitz. Bounds on net delays. IEEE Transactions on Circuits and Systems, 39(11):815-824, 1992.
69. {69} H. Youssef and E. Shragowitz. Timing constraints for correct performance. In IEEE/ACM International Conference on Computer-Aided Design, pages 24-27, 1990.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • Buses and high-speed links

  • Electronic design automation

    • Physical design (EDA)

      • Partitioning and floorplanning

      • Placement

      • Wire routing