Recursive bisection placement: feng shui 5.0 implementation details

ABSTRACT

In this paper, we summarize circuit placement techniques and algorithms developed by the BLAC CAD research group; these have been integrated into our recursive bisection based placement tool feng shui. We also briefly describe current research interests.

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: Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
• 4: 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]
• 5: 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]
• 6: 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]
• 7: 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.
• 8: 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]
• 9: D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design, 2002.
• 10: 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]
• 11: Andrew B. Kahng , Sherief Reda, Placement feedback: a concept and method for better min-cut placements, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996670]
• 12: Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981084]
• 13: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, May 1983.
• 14: 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 and Systems, 10(3):356--365, 1991.
• 15: C. Li and C.-K. Koh. On improving recursive bipartitioning-based placement. Technical Report TR-ECE-03-14, Purdue University ECE, 2003.
• 16: 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]
• 17: Chen Li , Cheng-Kok Koh , Patrick H. Madden, Floorplan management: incremental placement for gate sizing and buffer insertion, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120867]
• 18: Patrick H. Madden, Partitioning by iterative deletion, Proceedings of the 1999 international symposium on Physical design, p.83-89, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300030]
• 19: Satoshi Ono , Patrick H. Madden, On structure and suboptimality in placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120864]
• 20: C. E. Radke, A justification of, and an improvement on, a useful rule for predicting circuit-to-pin ratios, Proceedings of the 6th annual conference on Design Automation, p.257-267, January 1969 [doi>10.1145/800260.809030]
• 21: Pradeep Ramachandaran , Ameya R. Agnihotri , Satoshi Ono , Purushothaman Damodaran , Krishnaswami Srihari , Patrick H. Madden, Optimal placement by branch-and-price, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120865]
• 22: Carl Sechen , Alberto Sangiovanni-Vincentelli, TimberWolf3.2: a new standard cell placement and global routing package, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.432-439, July 1986, Las Vegas, Nevada, United States
• 23: 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.
• 24: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 25: 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]
• 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: 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]
• 28: 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]

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