Timing-driven placement based on partitioning with dynamic cut-net control

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing-driven placement based on partitioning with dynamic cut-net control

Full text

Pdf (106 KB)

Source

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

Los Angeles, California, United States

Pages: 472 - 476

Year of Publication: 2000

ISBN:1-58113-187-9

Authors

Shih-Lian Ou	Department of EE-Systems, University of Southern California, Los Angeles, CA
Massoud Pedram	Department of EE-Systems, University of Southern California, Los Angeles, CA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 20, Citation Count: 23

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

ABSTRACT

This paper presents a partitioning-based, timing-driven placement algorithm. The partitioning step itself is timing-driven and based on solving a quadratic programming problem iteratively. The placement algorithm does not rely on interleaved timing calculations, which tend to be inaccurate. Instead, it achieves the desired result by controlling the number of times that a path in the circuit can be cut. In addition to the cutting constraint, a pre-locking mechanism and timing-aware terminal propagation are developed and integrated into the flow. The detailed placement step is formulated as a constrained quadratic program and solved efficiently. Results show improvements of 23.41% on average compared to another timingdriven placement system Timing-QUAD and significant improvements over Eisenmanns placement algorithm.

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	Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
	2	T. S. Mob, T. S. Chang, and S.L.Hakimi. "Globally optimal floorplanning for a layout problem". IEEE Trans. on Circuit and Systems - I: Fundamental Theory and Applications, Vol.43:pp.713-720, Sep. 1996.
	3	Temo Chen , Michael K. H. Fan, On convex formulation of the floorplan area minimization problem, Proceedings of the 1998 international symposium on Physical design, p.124-128, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274553]
	4	K. Wang and W.K. Chen. "Floorplan Area Optimization using Network Analogous Approach". In Proc. oflEEE International Symposium on Circuits and Systems, pages 167-170, 1995.
	5	Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

CITED BY 23

	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
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Timing-driven placement for hierarchical programmable logic devices, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.3-11, February 2001, Monterey, California, United States
	Patrick H. Madden, Reporting of standard cell placement results, Proceedings of the 2001 international symposium on Physical design, p.30-35, April 01-04, 2001, Sonoma, California, United States
	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
	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
	Shyam Ramji , Nagu R. Dhanwada, Design topology aware physical metrics for placement analysis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., 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
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Adaptive delay estimation for partitioning-driven PLD placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.60-63, February 2003
	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
	Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, 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
	Ting-Yuan Wang , Jeng-Liang Tsai , Charlie Chung-Ping Chen, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Zhong Xiu , Rob A. Rutenbar, Timing-driven placement by grid-warping, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Wenting Hou , Xianlong Hong , Weimin Wu , Yici Cai, A path-based timing-driven quadratic placement algorithm, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, 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
	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
	Lihong Zhang , Rabin Raut , Yingtao Jiang , Ulrich Kleine , Yoohwan Kim, Macro-cell placement for analog physical designs using a hybrid genetic algorithm with simulated annealing, Integrated Computer-Aided Engineering, v.12 n.4, p.379-396, October 2005
	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
	Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States
	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
	Cheng-Yu Wang , Wai-Kei Mak, Signal skew aware floorplanning and bumper signal assignment technique for flip-chip, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Masato Inagi , Yasuhiro Takashima , Yuichi Nakamura , Yoji Kajitani, A Performance-Driven Circuit Bipartitioning Method Considering Time-Multiplexed I/Os, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.924-931, May 2007