On structure and suboptimality in placement

ABSTRACT

Regular structures are present in many types of circuits. If this structure can be identified and utilized, performance can be improved dramatically. In this paper, we present a novel placement approach that successfully identifies regularity, and obtains placements that are superior to other "general purpose" methods. This method has been integrated into our Feng Shui 2.6 bisection-based placement tool.On experiments with the PEKO benchmarks, our results are within 32% of optimal for both the large and small suites. The largest example, with 2.1 million cells, can be completed in sixteen hours. The majority of our run time is during detail placement--global placement takes under three hours. The success of our method shows that it can find structure, even when the structure was not expected or intended.As part of this work, we have made a number of observations related to the nature of suboptimality in placement. These observations have shown that some neglected research areas have great potential, while problems that receive considerable attention are essentially adequately solved.

REFERENCES

• 1: 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]
• 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: 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]
• 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 , 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]
• 6: Jason Cong , Yiping Fan , Xun Yang , Zhiru Zhang, Architecture and synthesis for multi-cycle communication, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640040]
• 7: Jason Cong , Cheng-Kok Koh, Interconnect layout optimization under higher-order RLC model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.713-720, November 09-13, 1997, San Jose, California, United States
• 8: 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]
• 9: 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]
• 10: D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design, 2002.
• 11: Bo Hu , Hailin Jiang , Qinghua Liu , Malgorzata Marek-Sadowska, Synthesis and placement flow for gain-based programmable regular fabrics, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640041]
• 12: Paolo Ienne , Alexander Grießing, Practical experiences with standard-cell based datapath design tools: do we really need regular layouts?, Proceedings of the 35th annual conference on Design automation, p.396-401, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277152]
• 13: Andrew B. Kahng , Chung-Wen Albert Tsao, Low-cost single-layer clock trees with exact zero Elmore delay skew, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.213-218, November 06-10, 1994, San Jose, California, United States
• 14: Andrew B. Kahng , Qinke Wang, Implementation and extensibility of an analytic placer, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981071]
• 15: 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]
• 16: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, May 1983.
• 17: 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.
• 18: P. H. Madden. Reporting of standard cell placement results. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 21(2):240--247, February 2002.
• 19: Deepak D. Sherlekar, Design considerations for regular fabrics, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981087]
• 20: 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]
• 21: 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]
• 22: 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