Recursive bisection based mixed block placement

ABSTRACT

Many current designs contain a large number of standard cells intermixed with larger macro blocks. The range of size in these "mixed block" designs complicates the placement process considerably; traditional methods produce results that are far from satisfactory.In this paper we extend the traditional recursive bisection standard cell placement tool Feng Shui to directly consider mixed block designs. On a set of recent benchmarks, the new version obtains placements with wire lengths substantially lower than other current tools. Compared to Feng Shui 2.4, the placements of a Capo-based approach have 29% higher wire lengths, while the placements of mPG are 26% higher. Run times of our tool are also lower, and the general approach is scalable.

REFERENCES

• 1: Fixed-Outline Floorplanning through Better Local Search, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.328, September 23-26, 2001
• 2: Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505392]
• 3: 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]
• 4: 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]
• 5: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 6: Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
• 7: 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]
• 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: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 10: 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 andSystems, CAD-4(1):92--98, January 1985.
• 11: 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]
• 12: GSRC. Bookshelf slot. http://www.gigascale.org/bookshelf.
• 13: D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design, 2002.
• 14: 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]
• 15: J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on Computer-Aided Design of Integrated Circuits andSystems, 10(3):356--365, 1991.
• 16: C. Li and C.-K. Koh. On improving recursive bipartitioning-based placement. Technical Report TR-ECE-03-14, Purdue University ECE, 2003.
• 17: Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379062]
• 18: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1518--1524, 1996.
• 19: Ralph H. J. M. Otten, What is a floorplan?, Proceedings of the 2000 international symposium on Physical design, p.201-206, May 2000, San Diego, California, United States [doi>10.1145/332357.332400]
• 20: Yingxin Pang , Florin Balasa , Koen Lampaert , Chung-Kuan Cheng, Block placement with symmetry constraints based on the O-tree non-slicing representation, Proceedings of the 37th conference on Design automation, p.464-467, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337545]
• 21: Carl Sechen, Chip-planning, placement, and global routing of macro/custom cell integrated circuits using simulated annealing, Proceedings of the 25th ACM/IEEE conference on Design automation, p.73-80, June 12-15, 1988, Atlantic City, New Jersey, United States
• 22: A. Shanbhag, S. Danda, and N. Sherwani. Floorplanning for mixed macro block and standard cell designs. In Proc. Great Lakes Symposium on VLSI, pages 26--29, 1994.
• 23: 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]
• 24: William Paul Swartz, Jr., Automatic layout of analog and digital mixed macro/standard cell integrated circuits, Yale University, New Haven, CT, 1993
• 25: Michael Upton , Khosrow Samii , Stephen Sugiyama, Integrated placement for mixed macro cell and standard cell designs, Proceedings of the 27th ACM/IEEE conference on Design automation, p.32-35, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123219]
• 26: 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
• 27: Hong Yu , Xianlong Hong , Yici Cai, MMP: a novel placement algorithm for combined macro block and standard cell layout design, Proceedings of the 2000 conference on Asia South Pacific design automation, p.271-276, January 2000, Yokohama, Japan [doi>10.1145/368434.368632]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms

Keywords:
floorplanning, mixed block design, placement