Consistent placement of macro-blocks using floorplanning and standard-cell placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Consistent placement of macro-blocks using floorplanning and standard-cell placement

Full text

Pdf (1.60 MB)

Source

International Symposium on Physical Design archive
Proceedings of the 2002 international symposium on Physical design table of contents

San Diego, CA, USA

SESSION: Placement table of contents

Pages: 12 - 17

Year of Publication: 2002

ISBN:1-58113-460-6

Authors

Saurabh N. Adya	University of Michigan, Ann Arbor, MI
Igor L. Markov	University of Michigan, Ann Arbor, MI

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 22, Citation Count: 28

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/505388.505392 What is a DOI?

ABSTRACT

While a number of recent works address large-scale standard-cell placement, they 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 in a design flow that solves the more general placement problem. Our work shows how to place macros consistently with large numbers of small standard cells. Our techniques can also be used to guide circuit designers who prefer to place macros by hand.

The proposed 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. Empirical evaluation on ibm benchmarks shows, in most cases, wirelength improvements of 10%-50% compared to Cadence QPlace, as well as runtime improvements.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	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]
	3	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]
	4	Cadence Inc, "Openbook documentation for QPlace", QP version 5.1.67 10/27/2000.
	5	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]
	6	A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", IEEE Trans. on CAD, vol. 19, no. 11, 2000, pp. 1304--1314.
	7	A. E. Caldwell, A. B. Kahng, I. L. Markov, "VLSI CAD Bookshelf" http://vlsicad.eecs.umich.edu/BK
	8	K. Doll, F. M. Johannes and K. J. Antreich, "Iterative Placement Improvement By Network Flow Methods". IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol.13, (no.10), Oct. 1994. pp. 1189--1200.
	9	S. Dutt, "Effective Partition-Driven Placement with Simultaneous Level Processing and a Global Net Views", ICCAD 2000, p. 254.
	10	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]
	11	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]
	12	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]
	13	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
	14	H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence pair", IEEE Trans. on CAD, vol 15(12), pp. 1518--1524, 1996.
	15	Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
	16	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]
	17	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]
	18	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
	19	M. C. Yildiz and P. H. Madden, "Improved Cut Sequences for Partitioning Based Placement", DAC 2001.

CITED BY 28

	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
	Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Andrew B. Kahng , John F. MacDonald , Peter Suaris , Bo Yao , Zhengyong Zhu, An algebraic multigrid solver for analytical placement with layout based clustering, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Lung-Tien Liu , Peter Suaris, Unified quadratic programming approach for mixed mode placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005
	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
	Yan Feng , Dinesh P. Mehta , Hannah Yang, Constrained "Modern" Floorplanning, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	S. N. Adya , I. L. Markov, Combinatorial techniques for mixed-size placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.58-90, January 2005
	Tung-Chieh Chen , Yao-Wen Chang, Modern floorplanning based on fast simulated annealing, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Ulrich Brenner , Markus Struzyna, Faster and better global placement by a new transportation algorithm, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Jin Guo , Antonis Papanikolaou , Pol Marchal , Francky Catthoor, Energy/area/delay trade-offs in the physical design of on-chip segmented bus architecture, Proceedings of the international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany
	Natarajan Viswanathan , Min Pan , Chris Chong-Nuen Chu, FastPlace: an analytical placer for mixed-mode designs, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Natarajan Viswanathan , Min Pan , Chris Chu, FastPlace 2.0: an efficient analytical placer for mixed-mode designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Jason Cong , Min Xie, A robust detailed placement for mixed-size IC designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On whitespace and stability in physical synthesis, Integration, the VLSI Journal, v.39 n.4, p.340-362, July 2006
	Chiu-wing Sham , Evangeline F. Y. Young , Chris Chu, Optimal cell flipping in placement and floorplanning, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Zhong Xiu , Rob A. Rutenbar, Mixed-size placement with fixed macrocells using grid-warping, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Shantanu Dutt , Huan Ren , Fenghua Yuan , Vishal Suthar, A network-flow approach to timing-driven incremental placement for ASICs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Bo Hu , M. Marek-Sadowska, Multilevel expansion-based VLSI placement with blockages, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.558-564, November 07-11, 2004
	A. B. Kahng , Q. Wang, An analytic placer for mixed-size placement and timing-driven placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.565-572, November 07-11, 2004
	K. Vorwerk , A. Kennings , A. Vannelli, Engineering details of a stable force-directed placer, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.573-580, November 07-11, 2004
	Min Pan , N. Viswanathan , C. Chu, An efficient and effective detailed placement algorithm, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.48-55, November 06-10, 2005, San Jose, CA
	Tung-Chieh Chen , Yao-Wen Chang , Shyh-Chang Lin, IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.159-164, November 06-10, 2005, San Jose, CA
	J. Cong , M. Romesis , J. R. Shinnerl, Robust mixed-size placement under tight white-space constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.165-172, November 06-10, 2005, San Jose, CA
	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
	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
	Sani R. Nassif, Power grid analysis benchmarks, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Chiu-Wing Sham , Evangeline F. Y. Young , Hai Zhou, Optimizing wirelength and routability by searching alternative packings in floorplanning, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.1, p.1-13, January 2008