Fast and robust quadratic placement combined with an exact linear net model

ABSTRACT

This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlapfree placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented.

In addition, a new linear net model is proposed, which accurately models the half-perimeter wirelength (HPWL) in the quadratic cost function of quadratic placement. HPWL in general is a linear metric for netlength and represents an efficient and common estimation for routed wirelength. Compared with the classical clique net model, our linear net model reduces memory usage by 75%, CPU time by 23% and netlength by 8%, which is measured by the HPWL of all nets.

Using the ISPD-2005 benchmark suite for comparison, our placer combined with the new linear net model has just 5.9% higher netlength but is 16x faster than APlace, which offers the best netlength in this benchmark. Compared to Capo, our placer has 9.2% lower netlength and is 5.4x faster.

In the recent ISPD-2006 placement contest, in which quality is mainly determined by netlength and CPU time, our placer together with the new net model produced excellent results.

REFERENCES

• 1: International symposium on physical design. http://www.ispd.cc.
• 2: International technology roadmap for semiconductors. http://public.itrs.net.
• 3: Ucla/umich physical design tools. http://vlsicad.eecs.umich.edu/BK/PDtools.
• 4: S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382639]
• 5: A. R. Agnihorti, S. Ono, C. Li, M. C. Yildiz, A. Khathate, C.-K. Koh, and P. H. Madden. Mixed block placement via fractional cut recursive bisection. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(5):748--761, May 2005.
• 6: Ulrich Brenner , Markus Struzyna, Faster and better global placement by a new transportation algorithm, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065733]
• 7: Tony Chan , Jason Cong , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055177]
• 8: Tony F. Chan , Jason Cong , Michalis Romesis , Joseph R. Shinnerl , Kenton Sze , Min Xie, mPL6: a robust multilevel mixed-size placement engine, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055185]
• 9: Tung-Chieh Chen , Tien-Chang Hsu , Zhe-Wei Jiang , Yao-Wen Chang, NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055188]
• 10: C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382665]
• 11: W. E. Donath, Complexity theory and design automation, Proceedings of the 17th conference on Design automation, p.412-419, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804563]
• 12: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 13: K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219--229, Nov. 1970.
• 14: M. Hanan. On Steiner's Problem with Rectiliner Distance. SIAM Journal of Applied Mathemetics, 14(2):255--265, 1966.
• 15: Bo Hu , Malgorzata Marek-Sadowska, FAR: fixed-points addition & relaxation based placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505426]
• 16: B. Hu and M. Marek-Sadowska. Multilevel fixed-point-addition-based vlsi placement. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(8):1188--1203, Aug. 2005.
• 17: A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
• 18: A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(05):734--747, May 2005.
• 19: J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Transactions on Computer-Aided Design of Circuits and Systems, CAD-10(3):356--365, Mar. 1991.
• 20: M. Kowarschik and C. Weiß. DiMEPACK -- A Cache-Optimized Multigrid Library. In H. Arabnia, editor, Proc. of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA 2001), pages 425--430. CSREA Press, June 2001.
• 21: M. C. V. Lier and R. H. J. M. Otten. Planarization by transformation. IEEE Transactions on Circuits and Systems CAS, 20(2):169--171, Mar. 1973.
• 22: K. G. Murty and F.-T. Yu. Linear complementary, linear and nonlinear programming. http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarit%y_webbook/.
• 23: Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Bruce Winter , Mehmet Yildiz, The ISPD2005 placement contest and benchmark suite, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055182]
• 24: G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng. A fast hierarchical quadratic placement algorithm. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 25(4):678--691, Apr. 2006.
• 25: W. Naylor, R. Donelly, and L. Sha. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. U.S. Patent 6301693, Oct. 2001.
• 26: Bernd Obermeier , Frank M. Johannes, Quadratic placement using an improved timing model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996760]
• 27: Bernd Obermeier , Frank M. Johannes, Temperature-aware global placement, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 28: Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055184]
• 29: Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
• 30: Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
• 31: Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi, Dragon2005: large-scale mixed-size placement tool, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055191]
• 32: N. Viswanathan and C. C.-N. Chu. Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(5):722--733, May 2005.
• 33: Jens Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th annual conference on Design automation, p.746-751, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266360]
• 34: A Standard-Cell Placement Tool for Designs with High Row Utilization, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.45, September 16-18, 2002

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Quadratic programming methods

General Terms:
Algorithms, Design, Performance