Quadratic placement revisited

ABSTRACT

The "quadratic placement" methodology is rooted in [Module Placement Based on Resistive Network Optimization, Proud: A Sea-Of-Gate Placement Algorithm, A Combined Force and Cut Algorithm for Hierarchical VLSI Layout]and is reputedly used in many commercial and in-house tools forplacement of standard-cell and gate-array designs. The methodologyiterates between two basic steps: solving sparse systems oflinear equations, and repartitioning. This work dissects the implementationand motivations for quadratic placement. We firstshow that (i) Krylov subspace engines for solving sparse systemsof linear equations are more effective than the traditional successiveover-relaxation (SOR) engine [A Unified Approach to Partitioning and Placement] and (ii) order convergence criteriacan maintain solution quality while using substantially fewersolver iterations. We then discuss the motivations and relevanceof the quadratic placement approach, in the context of past and futurealgorithmic technology, performance requirements, and designmethodology. We provide evidence that the use of numerical linearsystems solvers with quadratic wirelength objective may be due tothe pre-1990's weakness of min-cut partitioners, i.e., numerical engineswere needed to provide helpful hints to min-cut partitioners.Finally, we note emerging methodology drivers in deep-submicrondesign that may require new placement approaches to the placement problem.

REFERENCES

• 1: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 2: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 3: C. J. Alpert, T. Chan, D. J.-H. Huang, I. Markov and K. Yan, "Quadratic Placement Revisited", Technical Report #970012, UCLA Computer Science Dept., March 1997.
• 4: R. Barret, M. Berry, T. Chan et al "Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods", SlAM 1995, http://netlib2, cs. utk. edu/linalg/html_templates/ Templates. html
• 5: T. Bui , C. Heigham , C. Jones , T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, Proceedings of the 26th ACM/IEEE conference on Design automation, p.775-778, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74527]
• 6: C. K. Cheng and E. S. Kuh. "Module Placement Based on Resistive Network Optimization", IEEE Trans. on CAD 3 (1984), pp. 218-225.
• 7: Howard C. Elman , Michael P. Chernesky, Ordering effects on relaxation methods applied to the discrete one-dimensional convection-diffusion equation, SIAM Journal on Numerical Analysis, v.30 n.5, p.1268-1290, Oct. 1993 [doi>10.1137/0730066]
• 8: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 9: Kunio Fukunaga , Shoichiro Yamada , Harold S. Stone , Tamotsu Kasai, Placement of circuit modules using a graph space approach, Proceedings of the 20th conference on Design automation, p.465-471, June 27-29, 1983, Miami Beach, Florida, United States
• 10: W. Hackbush, "Iterative Solution of Large Sparse Systems" Springer Verlag, 1994.
• 11: Lars W. Hagen , Dennis J. H. Huang , Andrew B. Kahng, Quantified suboptimality of VLSI layout heuristics, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.216-221, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217532]
• 12: J. Kleinhans, G. Sigl, F. Johannes and K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on CAD. 10(3) (1991) pp. 356-365.
• 13: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 14: Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, PROUD: A Sea-Of-Gates Placement Algorithm, IEEE Design & Test, v.5 n.6, p.44-56, November 1988 [doi>10.1109/54.9271]
• 15: R. S. Tsay and E. Kuh, "A Unified Approach to Partitioning and Placement", IEEE Trans. on Circuits and Systems, 38(5) (1991), pp. 521-633.
• 16: G. J. Wipfler , M. Wiesel , D. A. Mlynski, A combined force and cut algorithm for hierarchical VLSI layout, Proceedings of the 19th conference on Design automation, p.671-677, January 1982

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  C. Computer Systems Organization

General Terms:
Design, Experimentation, Measurement, Performance, Theory