A new congestion-driven placement algorithm based on cell inflation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new congestion-driven placement algorithm based on cell inflation

Full text

Pdf (183 KB)

Source

Asia and South Pacific Design Automation Conference archive
Proceedings of the 2001 Asia and South Pacific Design Automation Conference table of contents

Yokohama, Japan

Pages: 605 - 608

Year of Publication: 2001

ISBN:0-7803-6634-4

Authors

Wenting Hou	Dept. Of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Hong Yu	Dept. Of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Xianlong Hong	Dept. Of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Yici Cai	Dept. Of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Weimin Wu	Dept. Of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Jun Gu	Dept. Of Computer Science and Technology, Hong Kong University, Hong Kong
William H. Kao	Arcadia Design System Inc., San Jose, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IPSJ : Information Processing Society of Japan
IEEE HK CAS : IEEE HK CAS and Comm. Joint Chapter
IEICE : Inst of Electronics, Info & Communication Engineers

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

In this paper, we describe a new congestion-driven placement based on cell inflation. In our approach, we have used the method of probability- estimation to evaluate the routing of nets. We also take use of the strategy of cell inflation to eliminate the routing congestion. Further reduction in congestion is obtained by the scheme of cell moving. We have tested our algorithm on a set of sample circuits from American industry and the results obtained have shown great improvement of routability.

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	[1] S. Mayrhofer and U. Lauther. "Congestion-Driven Placement Using a New Multi-Partitioning Heuristic", International Conference on Computer-Aided Design, pages 332-335. IEEE/ACM, November 1990.
	2	Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300044]
	3	Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
	4	Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
	5	Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
	6	[6] Hong Yu, Xianlong Hong, Changge. Qiao, Yici Cai, "CASH: A novel quadratic placement algorithm for very large standard cell layout design based on clustering", Proceedings of the 5th International Conference on Solid-State and Integrated Circuit Technology, 1998, pp. 496-501.
	7	[7] B. Yao, W. T. Hou, X. L. Hong and Y. C. Cai, "FAME: A Fast Detailed Placement Algorithm for Standard-Cell Layout Based on Mixed Mincut and Enumberation", Proc. Int. Conf. On CAD/CG, Shanghai, pp. 616-621, 1999.

CITED BY 13

	Bo Hu , Malgorzata Marek-Sadowska, Congestion minimization during placement without estimation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.739-745, November 10-14, 2002, San Jose, California
	Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Mehdi Saeedi , Morteza Saheb Zamani , Ali Jahanian, Prediction and reduction of routing congestion, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Zion Cien Shen , Chris C. N. Chu, Accurate and efficient flow based congestion estimation in floorplanning, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.671-676, January 27-30, 2004, Yokohama, Japan
	Zhuoyuan Li , Weimin Wu , Xianlong Hong, Congestion driven incremental placement algorithm for standard cell layout, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Navaratnasothie Selvakkumaran , Phiroze N. Parakh , George Karypis, Perimeter-degree: a priori metric for directly measuring and homogenizing interconnection complexity in multilevel placement, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Qinghua Liu , Malgorzata Marek-Sadowska, A congestion-driven placement framework with local congestion prediction, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Mehdi Saeedi , Morteza Saheb Zamani , Ali Jahanian, Evaluation, prediction and reduction of routing congestion, Microelectronics Journal, v.38 n.8-9, p.942-958, August, 2007
	Peter Spindler , Frank M. Johannes, Fast and accurate routing demand estimation for efficient routability-driven placement, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: architecture and implementation of a hybrid and robust global router, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Kalliopi Tsota , Cheng-Kok Koh , Venkataramanan Balakrishnan, Guiding global placement with wire density, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-21, March 2009