A novel net weighting algorithm for timing-driven placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A novel net weighting algorithm for timing-driven placement

Full text

Pdf (120 KB)

Source

International Conference on Computer Aided Design archive
Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design table of contents

San Jose, California

Pages: 172 - 176

Year of Publication: 2002

ISBN ~ ISSN:1092-3152 , 0-7803-7607-2

Author

Tim (Tianming) Kong

Aplus Design Technologies, Inc., Los Angeles, CA

Sponsors

: IEEE Circuits & Systems Society
IEEE-CS\DATC : IEEE Computer Society
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 66, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/774572.774597 What is a DOI?

ABSTRACT

Net weighting for timing-driven placement has been very popular in industry and academia. It has various advantages such as low complexity, high flexibility and ease of implementation. Existing net weighting algorithms, however, are often ad-hoc. There is generally no known good net weighting algorithms. In this paper, we present a novel net weighting algorithm based on the concept of path-counting, and apply it in timing-driven FPGA placement application. Theoretically this is the first ever known accurate, all-path counting algorithm. Experimental data shows that compared with the weighting algorithm used in state-of-the-art FPGA placement package VPR[1], this new algorithm can achieve the longest path delay reduction of up to 38.8%, 15.6% on average with no runtime overhead and only a 4.1% increase in total wirelength.

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	Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
	2	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]
	3	A. Srinivasan, K. Chaudhary, and E. S. Kuh, "RITUAL: Performance driven placement algorithm for small cell ICs," in IEEE/ACM International Conference on Computer-Aided Design, pp. 48--51, 1991.
	4	M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
	5	T. Gao , P. M. Vaidya , C. L. Liu, A performance driven macro-cell placement algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.147-152, June 08-12, 1992, Anaheim, California, United States
	6	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]
	7	M. Marek-Sadowska and S. P. Lin, "Timing driven placement," in IEEE/ACM International Conference on Computer-Aided Design, pp. 94--97, 1989.
	8	B. M. Riess and G. G. Ettelt, "Speed: fast and efficient timing driven placement," in International Symposium on Circuits and Systems, pp. 377--380, 1995.
	9	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]
	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	Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
	12	M. Senn, U. Seidl, and F. Johannes, "High quality deterministic timing driven FPGA placement," in ACM Symposium on FPGAs, 2002.
	13	http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html, "The FPGA place-and-route challenge."

CITED BY 27

	Jason Cong , Xin Yuan, Multilevel global placement with retiming, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, 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
	Michael G. Wrighton , André M. DeHon, Hardware-assisted simulated annealing with application for fast FPGA placement, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, 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
	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
	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
	Mongkol Ekpanyapong , Sung Kyu Lim, Performance-driven global placement via adaptive network characterization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.137-142, January 27-30, 2004, Yokohama, Japan
	Mike Hutton , David Karchmer , Bryan Archell , Jason Govig, Efficient static timing analysis and applications using edge masks, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	Tony F. Chan , Jason Cong , Michalis Romesis , Joseph R. Shinnerl , Kenton Sze , Min Xie, mPL6: a robust multilevel mixed-size placement engine, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	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
	Gang Chen , Jason Cong, Simultaneous placement with clustering and duplication, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.740-772, July 2006
	Kristofer Vorwerk , Andrew Kennings , Doris T. Chen , Laleh Behjat, Floorplan repair using dynamic whitespace management, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	Yue Zhuo , Hao Li , Qiang Zhou , Yici Cai , Xianlong Hong, New timing and routability driven placement algorithms for FPGA synthesis, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	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
	Jason Cong , Michail Romesis , Min Xie, Optimality and Stability Study of Timing-Driven Placement Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.472, November 09-13, 2003
	Tony F. Chan , Jason Cong , Tim Kong , Joseph R. Shinnerl , Kenton Sze, An Enhanced Multilevel Algorithm for Circuit Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.299, November 09-13, 2003
	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
	Christophe Alexandre , Hugo Clement , Jean-Paul Chaput , Marek Sroka , Christian Masson , Remy Escassut, TSUNAMI: An Integrated Timing-Driven Place And Route Research Platform, Proceedings of the conference on Design, Automation and Test in Europe, p.920-921, March 07-11, 2005
	Wing On Fung , Tughrul Arslan, A power-aware algorithm for the design of reconfigurable hardware during high level placement, International Journal of Knowledge-based and Intelligent Engineering Systems, v.12 n.3, p.237-244, August 2008
	Andrew B. Kahng , Chul-Hong Park , Puneet Sharma , Qinke Wang, Lens aberration aware placement for timing yield, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-26, January 2009
	Hao Li , Yue Zhuo, Criticality history guided FPGA placement algorithm for timing optimization, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
	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
	Weixiang Shen , Yici Cai , Xianlong Hong , Jiang Hu, Low Power Gated Clock Tree Driven Placement, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.2, p.595-603, February 2008