Physical Layout after Half a Century: From Back-Board Ordering to Multi-Dimensional Placement and Beyond

ABSTRACT

Innovations and advancements on physical design (PD) in the past half century significantly contribute to the progresses of modern VLSI designs. While ``Moore's Law'' and ``Dennard Scaling'' have become slowing down recently, physical design society encountered a set of challenges and opportunities. This article is presented at the event of the Life Time Achievement Award for Dr. Satoshi Goto by ISPD 2017. Dr. Goto's career in VLSI designs sets an exemplar role model for young engineers. Thus, we use his contributions as a thread to describe our personal view of physical layout from early back-board ordering to recent multi-dimensional placement and the future.

References

1. R. Aitken, G. Yeric, B. Cline, S. Sinha, L. Shifren, I. Iqbal and V. Chandra, "Physical Design and FinFETs", Proc. ISPD, 2014, pp. 65--68.
2. C. J. Alpert, "The ISPD98 Circuit Benchmark Suite", Proc. ISPD, 1998, pp. 80--85.
3. C. Alpert, Z. Li, G.-J. Nam, C. N. Sze, N. Viswanathan and S. I. Ward, "Placement: How or Not"?, Proc. ICCAD, 2012, pp. 283--290.
4. K.J. Antreich, F.M. Johnnes, and F.H. Kirsch, "A New Approach for Solving the Placement Problem using Force Models," IEEE Int. Symp. Circuits and Systems, 1982, pp. 481--486.
5. F. Brglez, D. Bryan and K. Kozminski, "Combinational Profiles of Sequential Benchmark Circuits", Proc. ISCAS, 1989, pp. 1929--1934.
6. I. S. Bustany, D. Chinnery, J. R. Shinnerl and V. Yutsis, "ISPD 2015 Benchmarks with Fence Regions and Routing Blockages for Detailed-Routing-Driven Placement", Proc. ISPD, 2015, pp. 157--164.
7. T. F. Chan, J. Cong, M. Romesis, J. R. Shinnerl, K. Sze and M. Xie, "mPL6: A Robust Multilevel Mixed-Size Placement Engine", Proc. ISPD, 2005, pp. 227--229.
8. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen and Y.-W. Chang, "NTUplace3: An Analytical Placer for Large-Scale Mixed-Size Designs with Preplaced Blocks and Density Constraints", Trans. on CAD, 27(7), 2008, pp. 1228--1240.
9. C.-K. Cheng and E. S. Kuh, "Module Placement Based on Resistive Network Optimization", Trans. on CAD, 3(3), 1984, pp. 218--225.
10. S. Goto, I. Cederbaum and B. S. Ting, "Suboptimum Solution of the Back-Board Ordering with Channel Capacity Constraint", IEEE Trans. on CAS CAS-24(11), 1977, pp. 645--652.
11. S. Goto and E. S. Kuh, "An Approach to the Two-Dimensional Placement Problem in Circuit Layout", IEEE Trans. on CAS CAS-25(4), 1978, pp. 208--217.
12. S. Goto, "A Two-Dimensional Placement Algorithm for the Master Slice LSI Layout Problem", Proc. DAC, 1979, pp. 11--17.
13. S. Goto, "An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout", IEEE Trans. on CAS CAS-28(1), 1981, pp. 12--18.
14. S. Goto, T. Matsuda, K. Takamizawa, T. Fujita, H. Mizumura, H. Nakamura and F. Kitajima, "LAMBDA, an Integrated Master-Slice LSI CAD System", Integration, the VLSI Journal 1(1), 1983, Elsevier, pp. 53--69.
15. O. He, S. Dong, J. Bian, S. Goto and C.-K. Cheng, "A Novel Fixed-Outline Floorplanner with Zero Deadspace for Hierarchical Design", Proc. ICCAD, 2008, pp. 16--23.
16. T.C. Hu and E.S. Kuh, VLSI Circuit Layout Theory and Design, IEEE Press, 1985.
17. O. He, S. Dong, J. Bian, S. Goto and C.-K. Cheng, "Bus Via Reduction Based on Floorplan Revising", Proc. GLSVLSI, 2010, pp. 9--14.
18. X. He, T. Huang, L. Xiao, H. Tian, G. Cui and E. F. Y. Young, "Ripple: An Effective Routability-Driven Placer by Iterative Cell Movement", Proc. ICCAD, 2011, pp. 74--79.
19. X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng and J. Gu, "Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan", Proc. ICCAD, 2000, pp. 8--12.
20. A. B. Kahng, "A Roadmap and Vision for Physical Design", Proc. ISPD, 2002, pp. 112--117.
21. A. B. Kahng, M. Luo, G.-J. Nam, S. Nath, D. Z. Pan and G. Robins, "Toward Metrics of Design Automation Research Impact", Proc. ICCAD, 2015, pp. 263--270.
22. A. B. Kahng, S. Reda and Q. Wang, "APlace: A General Analytic Placement Framework", Proc. ISPD, 2005, pp. 233--235.
23. M.-C. Kim, J. Hu and N. Viswanathan, "ICCAD-2014 CAD Contest in Incremental Timing-Driven Placement and Benchmark Suite", Proc. ICCAD, 2014, pp. 361--366.
24. M.-C. Kim, J. Hu, J. Li and N. Viswanathan, "ICCAD-2015 CAD Contest in Incremental Timing-Driven Placement and Benchmark Suite", Proc. ICCAD, 2015, pp. 921--926.
25. M.-C. Kim, D.-J. Lee and I. L. Markov, "SimPL: An Effective Placement Algorithm", Trans. on CAD, 31(1), 2012, pp. 50--60.
26. M.-C. Kim, N. Viswanathan, Z. Li and C. Alpert, "ICCAD-2013 CAD contest in Placement Finishing and Benchmark Suite", Proc. ICCAD, 2013, pp. 268--270.
27. J. M. Kleinhans, G. Sigl, F. M. Johannes and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", Trans. on CAD, 10(3), 1991, pp. 356--365.
28. E. S. Kuh, Quote from a Recommendation Letter, Personal Communication.
29. J. Liu, S. Dong, X. Hong and S. Goto, "Floorplanning with Constraint Extraction based on Interconnecting Information Analysis", Proc. ASICON, 2007, pp. 1084--1087.
30. J. Lu, P. Chen, C.-C. Chang, L. Sha, D. Huang, C.-C. Teng and C.-K. Cheng, "ePlace: Electrostatics based Placement using Fast Fourier Transform and Nesterov's Method", Trans. on DAES 20(2), 2015, article 17.
31. J. Lu, H. Zhang, P. Chen H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng and C.-K. Cheng, "ePlace-MS: Electrostatics-Based Placement for Mixed-Size Circuits", IEEE Trans. on CAD 34(5), 2015, pp. 685--698.
32. M. Marek-Sadowska and S. P. Lin, "Timing Driven Placement", Proc. ICCAD, 1989, pp. 94--97.
33. I. L. Markov, J. Hu and M.-C. Kim, "Progress and Challenges in VLSI Placement Research", Proc. ICCAD, 2012, pp. 275--282.
34. H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair", Trans. on CAD, 15(12), 1996, pp. 1518--1524.
35. G.-J. Nam, "ISPD 2006 Placement Contest: Benchmark Suite and Results", Proc. ISPD, 2006, pp. 167.
36. G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter and M. Yildiz, "The ISPD2005 Placement Contest and Benchmark Suite", Proc. ISPD, 2005, pp. 216--220.
37. R. H. J. M. Otten, "Automatic Floorplan Design", Proc. DAC, 1982, pp. 261--267.
38. B. T. Preas and W. M. van Cleemput, "Placement Algorithms for Arbitrarily Shaped Blocks", Proc. DAC, 1979, pp. 474--480.
39. F. Qiao, I. Kang, D. Kane, E. F. Y. Young, C.-K. Cheng and R. Graham, "3D Floorplan Representations: Corner Links and Partial Order", Proc. 3DIC, 2016, to appear.
40. N. Quinn and M. Breuer, "A Forced Directed Component Placement Procedure for Printed Circuit Boards", IEEE Trans. on CAS, 26(6), 1979, pp. 377--388.
41. C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf Placement and Routing Package", IEEE Journal of SSC, 20(2), 1985, pp. 510--522.
42. L. Steinberg, "The Backboard Wiring Problem: A Placement Algorithm," SIAM Review 3(1), 1961, pp. 37--50.
43. J. E. Stevens, "Fast Heuristic Techniques for Placing and Wiring Printed Circuit Boards", Ph. D. dissertation, University of Illinois at Urbana-Champaign, 1972.
44. X. Tang and D. F. Wong, "FAST-SP: A Fast Algorithm for Block Placement Based on Sequence Pair", Proc. ASP-DAC, 2001, pp. 521--526.
45. A. Thierer and A. Castillo, "Projecting the Growth and Economic Impact of the Internet of Things", Technology Policy, Policy Briefing, Mercatus Center at George Mason University, June 15, 2015, https://www.mercatus.org/system/files/IoT-EP-v3.pdf.
46. N. Viswanathan, C. J. Alpert, C. N. Sze, Z. Li and Y. Wei, "The DAC 2012 Routability-driven Placement Contest and Benchmark Suite", Proc. DAC, 2012, pp. 774--782.
47. N. Viswanathan, C. J. Alpert, C. N. Sze, Z. Li and Y. Wei, "ICCAD-2012 CAD Contest in Design Hierarchy Aware Routability-Driven Placement and Benchmark Suite", Proc. ICCAD, 2012, pp. 345--348.
48. N. Viswanathan, C. J. Alpert, C. N. Sze, Z. Li, G.-J. Nam and J. A. Roy, "The ISPD-2011 Routability-Driven Placement Contest and Benchmark Suite", Proc. ISPD , 2011, pp. 141--146.
49. N. Viswanathan, M. Pan and C. Chu, "FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control", Proc. ASP-DAC, 2007, pp. 135--140.
50. M. B. Weindling, "A Method for the Best Geometric Placement of Units on a Plane", Proc. DAC, 1964, pp. 5.1--5.54.
51. G. J. Wipfler, M. Wiesel and D. A. Mlynski, "A combined force and cut algorithm for hierarchical VLSI layout" Proc. DAC, 1982, pp. 671--677.
52. D. F. M. Wong and C.-L. Liu "A New Algorithm for Floorplan Design", Proc. DAC, 1986, pp. 101--107.
53. J. Z. Yan, N. Viswanathan and C. Chu, "Handling Complexities in Modern Large-Scale Mixed-Size Placement", Proc. DAC, 2009, pp. 436--441.
54. S. Yang, A. Gayasen, C. Mulpuri, S. Reddy and R. Aggarwal, "Routability-Driven FPGA Placement Contest", Proc. ISPD, 2016, pp. 139--143.
55. V. Yutsis, I. S. Bustany, D. Chinnery, J. Shinnerl and W.-H. Liu, "ISPD 2014 Benchmarks with Sub-45nm Technology Rules for Detailed-Routing-Driven Placement", Proc. ISPD, 2014, pp. 161--168.
56. ISPD-2017 Contest, http://www.ispd.cc/contests/17/.
57. ITRS Report 2015 Edition, http://www.semiconductors.org/main/2015_international_technology_roadmap_for_semiconductors_itrs/.
58. Hardware Design Cost: Faster, Cooler, Simpler, could FD-SOI be Cheaper too?, https://www.semiwiki.com/forum/content/2991-faster-cooler-simpler-could-fd-soi-cheaper-too.html.
59. Many Ways to Shrink: The Right Moves to 10 Nanometer and Beyond, https://staticwww.asml.com/doclib/investor/asml_3_Investor_Day-Many_ways_to_shrink_MvdBrink1.pd

Index Terms

• Hardware

  • Very large scale integration design

    • Application-specific VLSI designs

      • Application specific integrated circuits