Improved cut sequences for partitioning based placement

ABSTRACT

Recursive partitioning based placement has a long history, but there has been little consensus on how cut sequences should be chosen. In this paper, we present a dynamic programming approach to cut sequence generation. If certain assumptions hold, these sequences are optimal. After study of these optimal sequences, we observe that an extremely simple method can be used to construct sequences that are near optimal.Using this method, our bisection based placement tool Feng Shui outperforms the previously presented Capo tool by 11% on a large benchmark. By integrating our cut sequence method into Capo, we are able to improve performance by 5%, bringing the results of Feng Shui and Capo closer together.

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: Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
• 3: 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]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: [5] A. E. Dunlop and B. W. Kernighan. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, CAD-4(1):92-98, January 1985.
• 6: 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]
• 7: 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]
• 8: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 9: [9] Brian W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291-307, 1970.
• 10: Krzysztof Koźmiński, Benchmarks for layout synthesis—evolution and current status, Proceedings of the 28th conference on ACM/IEEE design automation, p.265-270, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127678]
• 11: [11] B. Landman and R. Russo. On a pin versus block relationship for partitioning of logic graphs. IEEE Trans. on Computers, C-20:1469-1479, December 1971.
• 12: Shih-Lian Ou , Massoud Pedram, Timing-driven placement based on partitioning with dynamic cut-net control, Proceedings of the 37th conference on Design automation, p.472-476, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337548]
• 13: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 14: [14] P. R. Suaris and G. Kedem. An algorithm for quadrisection and its application to standard cell placement. IEEE Trans. on Circuits and Systems, 35(3):394-303, 1988.
• 15: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
• 16: [16] Kazuhiro Takahashi, Kazuo Nakajima, Masayuki Terai, and Koji Sato. Min-cut placement with global objective functions for large scale sea-of-gates arrays. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 14(4):434-446, April 1995.
• 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

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

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

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