Timing driven placement using physical net constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing driven placement using physical net constraints

Full text

Pdf (185 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 38th annual Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 780 - 783

Year of Publication: 2001

ISBN:1-58113-297-2

Authors

Bill Halpin	Design Technology, Intel, 2200 Mission College, Santa Clara, CA
C. Y. Roger Chen	Syracuse University, Department of EE&CS, Syracuse, NY
Naresh Sehgal	EPD, Intel, 2200 Mission College, Santa Clara, CA

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

This paper presents a new timing driven placement algorithm that explicitly meets physical net lengths constraints. It is the first recursive bi-section placement (RBP) algorithm that meets precise half perimeter bounding box constraints on critical nets. At each level of the recursive bi-section, we use linear programming to ensure that all net constraints are met. Our method can easily be incorporated with existing RBP methods. We use the net constraint based placer to improve timing results by setting and meeting constraints on timing critical nets. We report significantly better timing results on each of the MCNC benchmarks and achieve an average optimization exploitation of 69% versus previously reported 53%.

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	Michael A. B. Jackson, Arvind Srinivasan and E. S. Kuh, "A Fast Algorithm for Performance-Driven Placement," Digest of Technical Papers, ICCAD, pp. 328-331, November 1990.
	2	Dennis Sylvester , Kurt Keutzer, Getting to the bottom of deep submicron, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.203-211, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288614]
	3	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]
	4	Wern-Jieh and Carl Sechen, "Efficient and Effective Placement for Very Large Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 349-359, 1995.
	5	A. Srinivasan, A K. Chaudhary, E. S. Kuh, "RITUAL: Performance Driven Placement Algorithm for Small Cell ICs," ICCAD, pp. 48-51, Nov. 1991.
	6	Jurgen M. Kleinhans, Georg Sigl, Frank M. Johannes, and Kurt Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Transactions on Computer Aided Design, Volume 10, No. 3 pp. 356-365, 1991.
	7	K. Doll, F. M. Johannes, and K.J. Antreich, "Iterative placement improvement by network flow methods," IEEE Transactions on CAD, vol. 13 pp.1190-1200, Oct 1994.
	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	J. Cong, "Timing models for Interconnects and Devices," DAC, 1997.
	10	R.S. Tsay, "Timing-Driven Placement," DAC, 1997.
	11	Shih-Lian Ou , Massoud Pedram, Timing-driven placement based on partitioning with dynamic cut-net control, Proceedings of the 37th conference on Design automation, p.472-476, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337548]
	12	Sung Woo Hur , John Lillis, Mongrel: hybrid techniques for standard cell placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	13	Jorge Nocedal and Stephen J. Wright, "Numerical Optimization," Springer-Verlag, 1999.
	14	H. Paul Williams, "Model Building in Mathematical Programming," John Wiley and Sons, 1999.
	15	Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, A sensitivity based placer for standard cells, Proceedings of the 10th Great Lakes symposium on VLSI, p.193-196, March 02-04, 2000, Chicago, Illinois, United States [doi>10.1145/330855.331040]
	16	Ren-Song Tsay , Juergen Koehl, An analytic net weighting approach for performance optimization in circuit placement, Proceedings of the 28th conference on ACM/IEEE design automation, p.620-625, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.122882]
	17	ftp://ftp.es.ele.tue.nl/pub/lp_solve/. Information and Communication Systems group at the Electrical Engineering department of the Eindhoven University of Technology, 1998.
	18	"www.cbl.ncsu.edu/benchmarks/layoutsynth92/

CITED BY 22

	Qinghua Liu , Bo Hu , Malgorzata Marek-Sadowska, Wire length prediction in constraint driven placement, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	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
	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
	Mongkol Ekpanyapong , Jacob R. Minz , Thaisiri Watewai , Hsien-Hsin S. Lee , Sung Kyu Lim, Profile-guided microarchitectural floorplanning for deep submicron processor design, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, 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
	Zhong Xiu , David A. Papa , Philip Chong , Christoph Albrecht , Andreas Kuehlmann , Rob A. Rutenbar , Igor L. Markov, Early research experience with OpenAccess gear: an open source development environment for physical design, 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
	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
	Qinghua Liu , Bo Hu , Malgorzata Marek-Sadowska, Individual wire-length prediction with application to timing-driven placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1004-1014, October 2004
	Amit Chowdhary , Karthik Rajagopal , Satish Venkatesan , Tung Cao , Vladimir Tiourin , Yegna Parasuram , Bill Halpin, How accurately can we model timing in a placement engine?, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	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
	Tao Luo , David Newmark , David Z. Pan, A new LP based incremental timing driven placement for high performance designs, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Michael D. Moffitt , David A. Papa , Zhuo Li , Charles J. Alpert, Path smoothing via discrete optimization, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Min Pan , Chris Chu, FastRoute: a step to integrate global routing into placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	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
	Jason Cong , Tim Kong , Joseph R. Shinnerl , Min Xie , Xin Yuan, Large-Scale Circuit Placement: Gap and Promise, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.883, November 09-13, 2003
	Wonjoon Choi , Kia Bazargan, Incremental Placement for Timing Optimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.463, November 09-13, 2003
	Andrew B. Kahng , Igor L. Markov , Sherief Reda, Boosting: Min-Cut Placement with Improved Signal Delay, Proceedings of the conference on Design, automation and test in Europe, p.21098, February 16-20, 2004
	Tao Luo , David Newmark , David Z. Pan, Total power optimization combining placement, sizing and multi-Vt through slack distribution management, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Tao Luo , David A. Papa , Zhuo Li , C. N. Sze , Charles J. Alpert , David Z. Pan, Pyramids: an efficient computational geometry-based approach for timing-driven placement, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California