Unification of budgeting and placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Unification of budgeting and placement

Full text

Pdf (171 KB)

Source

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

Anaheim, California, United States

Pages: 758 - 761

Year of Publication: 1997

ISBN:0-89791-920-3

Authors

Majid Sarrafzadeh	Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL
David Knol	Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL
Gustavo Tellez	Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL

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): 7, Downloads (12 Months): 12, Citation Count: 10

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

ABSTRACT

In this paper we present a novel formulation for thenet-based timing-driven placement problem.The new formulationperforms budgeting (net delay upper bounds) andplacement modification simultaneously thus alleviates theproblem of going back-and-forth between budgeting andplacement.An algorithm to accomplished the proposedtask is presented.The proposed algorithm uses a simulatedannealing approach and a modified graph-based simplexmethod.A general formulation of timing-sriven placementis presented.It is proved that both net-based andpath-based approaches to timing-driven placement are specialcases of a more general formulation.The proposed algorithmhas been incorporated into a (timing-driven) placementpackage.Experiments on MCNC benchmarks showstrong results.The proposed algorithm offers 54% to 68%reduction over the longest path compared with the existingalgorithms.

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	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
	2	T. Gao, P. M. Vaidya, and C. L. Liu. "A New Performace Driven Placement Algorithm". In International Conference on Computer-Aided Design, pages 44-47. IEEE/ACM, 1991.
	3	J. F. Lee and C. K. Wong. "A Performance-Aimed Cell Compactor with Automatic Jogs". IEEE Transactions on Computer Aided Design, CAD-11(12):1495- 1507, December 1992.
	4	Sching L. Lin , Jonathan Allen, Minplex—a compactor that minimizes the bounding rectangle and individual rectangles in a layout, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.123-130, July 1986, Las Vegas, Nevada, United States
	5	D. G. Luenberger. "Linear and Nonlinear Programruing". Addison-Wesley, Reading, Massachusetts, 1984.
	6	G. E. T~llez, David Knol, and M. Sarrafzadeh. "A Graph-Based Delay Budgeting Algorithm for Large Scale Timing-Driven Placement Problems". In 5th A CM/SIGDA Physical Design Workshop, 1996.

CITED BY 10

	Andrew A. Kennings , Igor L. Markov, Analytical minimization of half-perimeter wirelength, Proceedings of the 2000 conference on Asia South Pacific design automation, p.179-184, January 2000, Yokohama, Japan
	Amir H. Ajami , Massoud Pedram, Post-layout timing-driven cell placement using an accurate net length model with movable Steiner points, Proceedings of the 2001 conference on Asia South Pacific design automation, p.595-600, January 2001, Yokohama, Japan
	Wilm Donath , Prabhakar Kudva , Leon Stok , Lakshmi Reddy , Andrew Sullivan , Kanad Chakraborty , Paul Villarrubia, Transformational placement and synthesis, Proceedings of the conference on Design, automation and test in Europe, p.194-201, March 27-30, 2000, Paris, France
	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
	Chien Chu Kuo , Allen C. H. Wu, Delay budgeting for a timing-closure-driven design method, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	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
	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
	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