Placement feedback: a concept and method for better min-cut placements

ABSTRACT

The advent of strong multi-level partitioners has made topdown min-cut placers a favored choice for modern placer implementations. We examine terminal propagation, an important step in min-cut placers, because it is responsible for translating partitioning results into global placement wirelength assumptions. In this work, we identify a previously overlooked problem - ambiguous terminal propagation - and propose a solution based on the concept of feedback from automatic control systems. Implementing our approach in Capo (version 8.7 [5, 10]) and applying it to standard benchmark circuits yields up to 14% wirelength reductions for the IBM benchmarks and 10% reductions for PEKO instances. Experiments also show consistent improvements for routed wirelength, yielding up to 9% wirelength reductions with practical increase in placement runtime. In addition, our method significantly improves routability without building congestion maps, and reduces the number of vias.

REFERENCES

• 1: Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003 [doi>10.1109/ICCAD.2003.107]
• 2: Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003 [doi>10.1109/ICCAD.2003.72]
• 3: 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]
• 4: A. E. Caldwell , A. B. Kahng , I. L. Markov, Optimal partitioners and end-case placers for standard-cell layout, Proceedings of the 1999 international symposium on Physical design, p.90-96, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300032]
• 5: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 6: A. E. Caldwell, A. B. Kahng and I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19(11), 2000, pp. 1304--1313.
• 7: Chin-Chih Chang , Jason Cong , Min Xie, Optimality and scalability study of existing placement algorithms, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119914]
• 8: Richard C. Dorf , Robert H. Bishop, Modern Control Systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 2000
• 9: A. E. Dunlop and B. W. Kernighan, "A Procedure for Placement of Standard-Cell VLSI Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4(1), 1985, pp. 92--98.
• 10: http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Capo, GSRC Bookshelf.
• 11: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 12: I. L. Markov, Private communication, November 2003.
• 13: P. R. Suaris and G. Kedem, "A Quadrisection-Based Combined Place and Route Scheme for Standard Cells," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8(3), 1989, pp. 234--244.
• 14: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 15: 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]
• 16: Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379064]
• 17: Mehmet Can Yildiz , Patrick H. Madden, Global objectives for standard cell placement, Proceedings of the 11th Great Lakes symposium on VLSI, p.68-72, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368801]
• 18: Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
feedback, min-cut placement, terminal propagation