Min-max placement for large-scale timing optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Min-max placement for large-scale timing optimization

Full text

Pdf (119 KB)

Source

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

San Diego, CA, USA

SESSION: Poster Paper Introductions table of contents

Pages: 143 - 148

Year of Publication: 2002

ISBN:1-58113-460-6

Authors

Andrew B. Kahng	UCSD, La Jolla, CA
Stefanus Mantik	UCLA, Los Angeles, CA
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): 4, Downloads (12 Months): 24, Citation Count: 16

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.505423 What is a DOI?

ABSTRACT

At the 250nm technology node, interconnect delays account for over 40% of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven placement for VLSI. Our work introduces a novel minimization of maximal path delay that improves upon previously known algorithms for timing-driven placement. Our placement algorithms have provable properties and are fast in practice. Empirical validation is based on extending a scalable min-cut placer with proven quality in wirelength- and congestion-driven placement [4]. The CPU overhead of the timing-driven capability is within 50%. We placed industrial circuits and evaluated the resulting layouts with a commercial static timing analyzer.

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 Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
	2	A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov and A. Zelikovsky, "On Wirelength Estimations for Row-Based Placement", IEEE Trans. on CAD, 18(9), Sept. 1999, pp. 1265--1278.
	3	A. E. Caldwell, A. B. Kahng and I. L. Markov, "Optimal Partitioning and End-Case Placement for Standard-Cell Layout", IEEE Trans. on CAD, 19(11), Nov. 2000, pp. 1304--1313.
	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	C.-C. Chang, J. Lee, M. Stabenfeldt and R.-S. Tsay, "A Practical All-Path Timing-Driven Place and Route Design System", Proc. Asia-Pacific Conf. on Circuits and Systems, 1994, pp. 560--563.
	6	A. H. Chao, E. M. Nequist and T. D. Vuong, "Direct Solutions of Performance Constraints During Placement", Proc. Custom Integrated Circuits Conf., 1990, pp. 27.2.1--27.2.4.
	7	Yih-Chih Chou , Youn-Long Lin, A performance-driven standard-cell placer based on a modified force-directed algorithm, Proceedings of the 2001 international symposium on Physical design, p.24-29, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369722]
	8	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	9	A. E. Dunlop and B. W. Kernighan, "A Procedure for Placement of Standard Cell VLSI Circuits", IEEE Trans. on CAD 4(1), 1985, pp. 92--98.
	10	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]
	11	J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
	12	Padmini Gopalakrishnan , Altan Odabasioglu , Lawrence Pileggi , Salil Raje, Overcoming wireload model uncertainty during physical design, Proceedings of the 2001 international symposium on Physical design, p.182-189, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369769]
	13	Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379065]
	14	Takeo Hamada , Chung-Kuan Cheng , Paul M. Chau, Prime: a timing-driven placement tool using a piecewise linear resistive network approach, Proceedings of the 30th international conference on Design automation, p.531-536, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165015]
	15	P. S. Hauge, R. Nair and E. J. Yoffa, "Circuit Placement for Predictable Performance", Proc. Intl. Conf. on Computer-Aided Design, 1987, pp. 88--91.
	16	R. B. Hitchcock, Sr., G. L. Smith and D. D. Cheng, "Timing Analysis of Computer Hardware", IBM J. Res. Develop. 26(1), 1982, pp. 100--108.
	17	M. A. B. Jackson, A. Srinivasan and E. S. Kuh, "A Fast Algorithm for Performance-Driven Placement", Proc. Intl. Conf. on Computer-Aided Design, pp. 328--331.
	18	T. Koide, M. Ono, S. Wakabayashi and Y. Nishimaru, "Par-POPINS: A Timing-Driven Parallel Placement Method with the Elmore Delay Model for Row Based VLSIs". Proc. Asia and South Pacific Design Automation Conf., 1997, pp. 133--140.
	19	D. G. Luenberger, Linear and Nonlinear Programming, 2nd ed., Addison Wesley, 1984.
	20	W. K. Luk, A fast physical constraint generator for timing driven layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.626-631, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.114161]
	21	M. Marek-Sadowska and S. P. Lin, "Timing-Driven Layout of Cell-Based ICs", VLSI Systems Design, May 1986, pp.63--73.
	22	M. Marek-Sadowska and S. P. Lin, "Timing Driven Placement", Proc. Intl. Conf. on Computer-Aided Design, 1989, pp. 94--97.
	23	R. Nair, C. L. Berman, P. S. Hauge and E. J. Yoffa, "Generation of Performance Constraints for Layout", IEEE Trans. on CAD 8(8), Aug. 1989, pp. 860--874.
	24	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]
	25	B. M. Riess and G. G. Ettelt, "Speed: Fast and Efficient Timing Driven Placement", Proc. Intl. Symp. on Circuits And Systems, 1995, pp. 377--380.
	26	Majid Sarrafzadeh , David Knol , Gustavo Tellez, Unification of budgeting and placement, Proceedings of the 34th annual conference on Design automation, p.758-761, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266364]
	27	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]
	28	H. Youssef, R.-B. Lin and E. Shragowitz, "Bounds on Net Delays for VLSI Circuits", IEEE Trans. on Circuits and Systems, 39(11), Nov. 1992, pp. 815--824.

CITED BY 16

	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
	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
	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
	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
	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
	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
	Bin Liu , Yici Cai , Qiang Zhou , Xianlong Hong, Power driven placement with layout aware supply voltage assignment for voltage island generation in Dual-Vdd designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	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
	S. Ghiasi , E. Bozorgzadeh , S. Choudhuri , M. Sarrafzadeh, A unified theory of timing budget management, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.653-659, November 07-11, 2004
	Soheil Ghiasi , Po-Kuan Huang, Probabilistic Delay Budgeting for Soft Realtime Applications, Proceedings of the 7th International Symposium on Quality Electronic Design, p.141-146, March 27-29, 2006
	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