A high-quality mixed-size analytical placer considering preplaced blocks and density constraints

ABSTRACT

In addition to wirelength, modern placers need to consider various constraints such as preplaced blocks and density. We propose a high-quality analytical placement algorithm considering wirelength, preplaced blocks, and density based on the log-sum-exp wirelength model proposed by Naylor et al. [20] and the multilevel framework. To handle preplaced blocks, we use a two-stage smoothing technique, Gaussian smoothing followed by level smoothing, to facilitate block spreading during global placement. The density is controlled by white-space re-allocation using partitioning and cut-line shifting during global placement and cell sliding during detailed placement. We further use the conjugate gradient method with dynamic step-size control to speed up the global placement and macro shifting to and better macro positions. Experimental results show that our placer obtains the best published results.

REFERENCES

• 1: ICCAD04 Mixed-Size Placement Benchmarks. http://vlsicad.eecs.umich.edu/BK/ICCAD04bench/.
• 2: ISPD 2005 Placement Contest. http://www.sigda.org/ispd2005/contest.htm.
• 3: ISPD 2006 Program. http://www.ispd.cc/program.html.
• 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: Ameya R. Agnihotri , Satoshi Ono , Patrick H. Madden, Recursive bisection placement: feng shui 5.0 implementation details, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055186]
• 6: Tony F. Chan , Jason Cong , Joseph R Shinnerl , Kenton Sze , Min Xie, mPL6: enhanced multilevel mixed-size placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123055]
• 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: Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119835]
• 9: 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]
• 10: J. Gu and X. Huang. Efficient local search with search space smoothing: A case study of the traveling salesman problem (TSP). IEEE Trans. on Systems, Man and Cybernetics, 24(5):728--735, 1994.
• 11: D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an intergrated circuit design. 2002.
• 12: Zhe-Wei Jiang , Tung-Chieh Cheny , Tien-Chang Hsuy , Hsin-Chen Chenz , Yao-Wen Changyz, NTUplace2: a hybrid placer using partitioning and analytical techniques, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123056]
• 13: Andrew B. Kahng , Sherief Reda , Qinke Wang, APlace: a general analytic placement framework, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055187]
• 14: 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
• 15: A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Trans. on CAD, 24(5), May 2005.
• 16: Andrew B. Kahng , Qinke Wang, A faster implementation of APlace, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123057]
• 17: M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. Gordian: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on CAD, 10(3):356--365, 1991.
• 18: Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382607]
• 19: Gi-Joon Nam, ISPD 2006 Placement Contest: Benchmark Suite and Results, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123042]
• 20: W. C. Naylor, R. Donelly, and L. Sha. US patent 6,301,693: Non-linear optimization system and method for wire length and dealy optimization for an automatic electric circuit placer. 2001.
• 21: Jarrod A. Roy , David A. Papa , Aaron N. Ng , Igor L. Markov, Satisfying whitespace requirements in top-down placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123053]
• 22: Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi , Maogang Wang , Majid Sarrafzadeh, Dragon2006: blockage-aware congestion-controlling mixed-size placer, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123054]
• 23: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Routability driven white space allocation for fixed-die standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505400]
• 24: Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Lung-Tien Liu , Peter Suaris, Unified quadratic programming approach for mixed mode placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055178]

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
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Performance