Routability driven white space allocation for fixed-die standard-cell placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Routability driven white space allocation for fixed-die standard-cell placement

Full text

Pdf (88 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: Physical Hierarchy table of contents

Pages: 42 - 47

Year of Publication: 2002

ISBN:1-58113-460-6

Authors

Xiaojian Yang	University of California at Los Angeles, Los Angeles, CA
Bo-Kyung Choi	University of California at Los Angeles, Los Angeles, CA
Majid Sarrafzadeh	University of California at Los Angeles, Los Angeles, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 35

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

ABSTRACT

The use of white space in fixed-die standard-cell placement is an effective way to improve routability. In this paper, we present a white space allocation approach that dynamically assigns white space according to the congestion distribution of the placement. In the top-down placement flow, white space is assigned to congested regions using a smooth allocating function. A post allocation optimization step is taken to further improve placement quality. Experimental results show that the proposed allocation approach, combined with a multilevel placement flow, significantly improves placement routability and layout quality.In our experiments, we compared our placement tool with two other fixed-die placers using an industrial place and route flow. Placements created by all three tools have been routed with an industrial router (Warp Route of Cadence). Compared with a leading-edge industrial tool, our placer produces placements with similar or better routability and on average 8.8% shorter routed wirelength. Furthermore, our tool produces placement that runs faster through the Warp Route compared with the industrial tool. Compared with a state-of-the-art academic placement tool (Capo/MetaPlacer), our placer shows ability to produce more routable placements: for 15 out of all 16 benchmarks our placer's outputs are routable while Capo/MetaPlacer only creates 4 routable placements.

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	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	2	Carl Sechen , Alberto Sangiovanni-Vincentelli, TimberWolf3.2: a new standard cell placement and global routing package, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.432-439, July 1986, Las Vegas, Nevada, United States
	3	J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization". IEEE Transactions on Computer Aided Design, 10(3):365--365, 1991.
	4	S. Mayrhofer and U. Lauther. "Congestion-Driven Placement Using a New Multi-partitioning Heuristic". In International Conference on Computer-Aided Design, pages 332--335. IEEE, 1990.
	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	M. Wang, X. Yang, and M. Sarrafzadeh. "Congestion Minimization During Placement". IEEE Transactions on Computer Aided Design, 19(10):1140--1148, 2000.
	7	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]
	8	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]
	9	Majid Sarrafzadeh , Maogang Wang, NRG: global and detailed placement, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.532-537, November 09-13, 1997, San Jose, California, United States
	10	Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	11	Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion estimation during top-down placement, Proceedings of the 2001 international symposium on Physical design, p.164-169, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369761]
	12	Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
	13	Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion estimation during top-down placement, Proceedings of the 2001 international symposium on Physical design, p.164-169, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369761]
	14	George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
	15	NuCAD. "IBM-PLACE benchmark". http://www.ece.nwu.edu/nucad/ibm-place.html.

CITED BY 35

	Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Jarrod A. Roy , James F. Lu , Igor L. Markov, Seeing the forest and the trees: Steiner wirelength optimization in placemen, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	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
	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
	Qinghua Liu , Malgorzata Marek-Sadowska, A study of netlist structure and placement efficiency, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Andrew B. Kahng , Qinke Wang, Implementation and extensibility of an analytic placer, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi , Maogang Wang , Majid Sarrafzadeh, Dragon2006: blockage-aware congestion-controlling mixed-size placer, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Andrew B. Kahng , Sherief Reda, Placement feedback: a concept and method for better min-cut placements, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Andrew B. Kahng , Igor L. Markov , Sherief Reda, On legalization of row-based placements, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	David A. Papa , Saurabh N. Adya , Igor L. Markov, Constructive benchmarking for placement, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Shamik Das , Anantha P. Chandrakasan , Rafael Reif, Calibration of rent's rule models for three-dimensional integrated circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.4, p.359-366, April 2004
	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
	Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Bruce Winter , Mehmet Yildiz, The ISPD2005 placement contest and benchmark suite, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California
	Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi, Dragon2005: large-scale mixed-size placement tool, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, 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
	Xiaoping Tang , Ruiqi Tian , Martin D. F. Wong, Optimal redistribution of white space for wire length minimization, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Pradeep Ramachandaran , Ameya R. Agnihotri , Satoshi Ono , Purushothaman Damodaran , Krishnaswami Srihari , Patrick H. Madden, Optimal placement by branch-and-price, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Yongseok Cheon , Martin D. F. Wong, Crowdedness-balanced multilevel partitioning for uniform resource utilization, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On whitespace and stability in physical synthesis, Integration, the VLSI Journal, v.39 n.4, p.340-362, July 2006
	Peter Spindler , Ulf Schlichtmann , Frank M. Johannes, Abacus: fast legalization of standard cell circuits with minimal movement, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Taraneh Taghavi , Foad Dabiri , Ani Nahapetian , Majid Sarrafzadeh, Tutorial on congestion prediction, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Taraneh Taghavi , Foad Dabiri , Ani Nahapetian , Majid Sarrafzadeh, Tutorial on congestion prediction, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	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
	Bo Hu , M. Marek-Sadowska, Multilevel expansion-based VLSI placement with blockages, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.558-564, November 07-11, 2004
	D. Jariwala , J. Lillis, On interactions between routing and detailed placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.387-393, November 07-11, 2004
	Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003
	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003
	Maogang Wang , Abhishek Ranjan , Salil Raje, Multi-Million Gate FPGA Physical Design Challenges, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.891, November 09-13, 2003
	Min Pan , Chris Chu, IPR: an integrated placement and routing algorithm, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Zhe-Wei Jiang , Bor-Yiing Su , Yao-Wen Chang, Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Tung-Chieh Chen , Minsik Cho , David Z. Pan , Yao-Wen Chang, Metal-density driven placement for cmp variation and routability, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA