A performance-driven standard-cell placer based on a modified force-directed algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A performance-driven standard-cell placer based on a modified force-directed algorithm

Full text

Pdf (256 KB)

Source

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

Sonoma, California, United States

Pages: 24 - 29

Year of Publication: 2001

ISBN:1-58113-347-2

Authors

Yih-Chih Chou	Department of Computer Science, National Tsing Hua University, Hsin-Chu 30043, Taiwan, R.O.C.
Youn-Long Lin	Department of Computer Science, National Tsing Hua University, Hsin-Chu 30043, Taiwan, R.O.C.

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 27, Citation Count: 11

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/369691.369722 What is a DOI?

ABSTRACT

We propose a performance-driven cell placement method based on a modified force-directed approach. A pseudo net is added to link the source and sink flip-flops of every critical path to enforce their closeness. Given user-specified I/O pad locations at the chip boundaries and starting with all core cells in the chip center, we iteratively move a cell to its force-balanced location assuming all other cells are fixed. The process stops when no cell can be moved farther than a threshold distance. Next, cell rows are adjusted one at a time starting from the top and bottom. After forming these two rows (top/bottom), all movable core cells force-balanced locations are updated. The row-formation-and-update process continues until all rows are adjusted and, hence, a legal placement is obtained. We have integrated the proposed approach into an industrial APR flow. Experimental results on benchmark circuits up to 191K-cell (500K-gate) show that the critical path delay can be improved by as much as 11.5%. We also study the effect on both layout quality and CPU time consumption due to the amount of pseudo net added. We found that the introduction of pseudo net indeed significantly improves the layout quality.

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	Neil R. Quinn, Jr., The placement problem as viewed from the physics of classical mechanics, Proceedings of the 12th conference on Design automation, p.173-178, January 1975
	2	K. J. Antreich, F. M. Johannes, and F. H. Kirsch, ''A new approach for solving the placement problem using force models," in Proc. of the IEEE International Symposium on Circuits and Systems, pp. 481-486, 1982.
	3	K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
	4	Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
	5	Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
	6	Too-Seng Tia and C. L. Liu, ''A New Performance Driven Macro-Cell Placement Algorithm," in Proc. of EURO- DAC'93, pp. 66-71, 1993
	7	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
	8	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
	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	Pran Kurup , Taher Abbasi, Logic synthesis using Synopsys (2nd ed.), Kluwer Academic Publishers, Norwell, MA, 1997
	11	Artisan Components Inc., http://artisan.com.
	12	Cadence Design Systems, Inc., ''LEF/DEF Language Reference," Product Version 5.0, February 1997.

CITED BY 11

	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
	Sung-Woo Hur , Tung Cao , Karthik Rajagopal , Yegna Parasuram , Amit Chowdhary , Vladimir Tiourin , Bill Halpin, Force directed mongrel with physical net constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Karthik Rajagopal , Tal Shaked , Yegna Parasuram , Tung Cao , Amit Chowdhary , Bill Halpin, Timing driven force directed placement with physical net constraints, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Bernd Obermeier , Frank M. Johannes, Quadratic placement using an improved timing model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Timing-driven placement using design hierarchy guided constraint generation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.177-180, November 10-14, 2002, San Jose, California
	Young-Su Kwon , Payam Lajevardi , Anantha P. Chandrakasan , Frank Honoré , Donald E. Troxel, A 3-D FPGA wire resource prediction model validated using a 3-D placement and routing tool, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA
	Chanseok Hwang , Massoud Pedram, Timing-driven placement based on monotone cell ordering constraints, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	Aiqun Cao , Ruibing Lu , Chen Li , Cheng-Kok Koh, Postlayout optimization for synthesis of Domino circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.4, p.797-821, October 2006
	Jun Cheng Chi , Hung Hsie Lee , Sung Han Tsai , Mely Chen Chi, Gate level multiple supply voltage assignment algorithm for power optimization under timing constraint, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.6, p.637-648, June 2007
	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