Combinatorial techniques for mixed-size placement

ABSTRACT

While recent literature on circuit layout addresses large-scale standard-cell placement, the authors typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. Therefore we combine floorplanning techniques with placement techniques to solve the more general placement problem. Our work shows how to place macros consistently with large numbers of small standard cells. Proposed techniques can also be used to guide circuit designers who prefer to place macros by hand.We address the computational difficulty of layout problems involving large macros and numerous small logic cells at the same time. Proposed algorithms are evaluated in the context of wirelength minimization because a computational method that is not scalable in optimizing wirelength is unlikely to be successful for more complex objectives (congestion, delay, power, etc.)We propose several different design flows to place mixed-size placement instances. The first flow relies on an arbitrary black-box standard-cell placer to obtain an initial placement and then removes possible overlaps using a fixed-outline floorplanner. This results in valid placements for macros, which are considered fixed. Remaining standard cells are then placed by another call to the standard-cell placer. In the second flow a standard-cell placer generates an initial placement and a force-directed placer is used in the engineering change order (ECO) mode to generate an overlap-free placement. Empirical evaluation on ibm benchmarks shows that in most cases our proposed flows compare favorably with previously published mixed-size placers, Kraftwerk, and the mixed-size floor-placer proposed at the 2003 Conference on Design, Automation, and Test in Europe (DATE 2003), and are competitive with mPG-MS.

REFERENCES

• 1: 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]
• 2: 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
• 3: 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]
• 4: Adya, S. N. and Markov, I. L. 2003. Fixed-outline floorplanning: Enabling hierarchical design. IEEE Trans. VLSI Syst. 11, 6 (Dec.), 1120--1135.
• 5: 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]
• 6: Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640022]
• 7: Adya, S. N., Yildiz, M., Markov, I. L., Villarrubia, P. G., Parakh, P. N., and Madden, P. H. 2004b. Benchmarking for large-scale placement and beyond. IEEE Trans. Comput. Aided. Des 23, 4 (April), 472--487.
• 8: 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]
• 9: 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]
• 10: Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774682]
• 11: Cadence. 2000. Openbook documentation for QPlace version 5.1.67. Cadence, San Jose, CA.
• 12: Caldwell, A. E., Kahng, A. B., and Markov, I. L. VLSI CAD Bookshelf. Available online at http://vlsicad.eecs.umich.edu/BK.
• 13: 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]
• 14: Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2000b. Optimal partitioners and end-case placers for standard-cell layout. IEEE Trans. Comput.-Aided Des. 19, 11, 1304--1314.
• 15: Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2003. Hierarchical whitespace allocation in top-down placement. IEEE Trans. Comput.-Aided Des. 22, 11 (Nov.), 716--724.
• 16: 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]
• 17: Wonjoon Choi , Kia Bazargan, Hierarchical Global Floorplacement Using Simulated Annealing and Network Flow Area Migration, Proceedings of the conference on Design, Automation and Test in Europe, p.11104, March 03-07, 2003
• 18: Willaim J. Dally , Andrew Chang, The role of custom design in ASIC Chips, Proceedings of the 37th conference on Design automation, p.643-647, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337604]
• 19: Doll, K., Johannes, F. M., and Antreich, K. J. 1994. Iterative placement improvement by network flow methods. IEEE Trans. Comput.-Aided Des. 13, 10 (Oct.), 1189--1200.
• 20: 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
• 21: 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]
• 22: Kunihiro Fujiyoshi , Hiroshi Murata, Arbitrary convex and concave rectilinear block packing using sequence-pair, Proceedings of the 1999 international symposium on Physical design, p.103-110, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300034]
• 23: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 24: Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States [doi>10.1145/332357.332401]
• 25: Andrew B. Kahng , Stefanus Mantik , Igor L. Markov, Min-max placement for large-scale timing optimization, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505423]
• 26: 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]
• 27: 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]
• 28: 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]
• 29: Fan Mo , Abdallah Tabbara , Robert K. Brayton, A force-directed macro-cell placer, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 30: Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y. 1996. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. Comput.-Aided Des. 15, 12, 1518--1524.
• 31: Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
• 32: Sudip Nag , Kamal Chaudhary, Post-placement residual-overlap removal with minimal movement, Proceedings of the conference on Design, automation and test in Europe, p.116-es, January 1999, Munich, Germany [doi>10.1145/307418.307568]
• 33: Yingxin Pang , Chung-Kuan Cheng , Takeshi Yoshimura, An enhanced perturbing algorithm for floorplan design using the O-tree representation, Proceedings of the 2000 international symposium on Physical design, p.168-173, May 2000, San Diego, California, United States [doi>10.1145/332357.332395]
• 34: Sarrafzadeh, M., Wang, M., and Yang, X. 2002. Modern Placement Techniques. Kluwer, Dordrecht, The Netherlands.
• 35: Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
• 36: Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France [doi>10.1145/343647.343713]
• 37: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]
• 38: Varadrajan, R. and DeLendonck, G. 2002. Personal communication.
• 39: Vijayan, G. 1991. Overlap elimination in floorplans. In Proceedings of the VLSI Design Conference. 157--162.
• 40: 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
• 41: 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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
VLSI, floorplanning, placement