More Web Proxy on the site http://driver.im/

research-article

Cut-demand based routing resource allocation and consolidation for routability enhancement

Authors:

Fong-Yuan Chang,

Sheng-Hsiung Chen,

Wai-Kei MakAuthors Info & Claims

ASPDAC '11: Proceedings of the 16th Asia and South Pacific Design Automation Conference

Pages 533 - 538

Published: 25 January 2011 Publication History

Abstract

To successfully route a design, one essential requirement is to allocate sufficient routing resources. In this paper, we show that allocating routing resources based on horizontal and vertical (H/V) cut-demands can greatly improve routability especially for designs with thin areas. We then derive methods to predict the maximum H/V cut-demands and propose two cut-demand based approaches, one is to allocate routing resources considering the maximum H/V cut-demands and the other is to consolidate fragmented metal-1 routing resources for effective resource utilization. Experimental results demonstrate that the resource allocation method can precisely determine design areas and the resource consolidation method can significantly improve routability. With better routability, the routing time is about 5 times faster on average and the design area can be further reduced by 2--15%.

References

[1]

Andrew B. Kahug, Stefanus Mantik and Dirk Stroobandt. "Requirements for Models of Achievable Routing," ISPD, Pages 4--11, 2000.

Digital Library

[2]

Jinan Lou, Shankar Krishnamoorthy and Henry S. Sheng. "Estimating Routing Congestion using Probabilistic Analysis," ISPD, Pages 112--117, 2001.

Digital Library

[3]

Louis Scheffer, Luciano Lavagno and Grant Martin. "EDA for IC Implementation, Circuit Design, and Process Technology," CRC Process, Taylor & Francis Group, 2006.

[4]

B. Landman and R. Russo. "On A Pin Versus Block Relationship for Partitions of Logic Graphs." IEEE Transactions on Computers, C20(12):1469--79, 1971.

Digital Library

[5]

P. Christie and D. Stroobandt. "The Interpretation and Application of Rent's Rule," IEEE Transactions on VLSI Systems, Pages 639--648, 2000.

Digital Library

[6]

C. Sechen. "Average Interconnection Length Estimation for Random and Optimized Placements," ICCAD, Pages 190--193, 1987.

[7]

Shankar Balachandran and Dinesh Bhatia. "A-Priori Wirelength and Interconnect Estimation Based on Circuit Characteristic," SLIP, Pages 77--84, 2003.

Digital Library

[8]

S. Bodapati and F. Najm. "Prelayout Estimation of Individual Wire Lengths," IEEE Transactions on VLSI, 9(6):943--58, 2001.

Digital Library

[9]

Bahareh Fathi, Laleh Behjat and Logan M. Rakai. "A pre-placement net length estimation technique for mixed-size circuits," SLIP, Pages 45--52, 2009.

Digital Library

[10]

Tsung-Hsien Lee and Ting-Chi Wang. "Robust Layer Assignment for Via Optimization in Multi-layer Global Routing," ISPD, Pages 159--166, 2009.

Digital Library

[11]

Hai Zhou. "Efficient Steiner tree construction based on spanning graphs," ISPD, Page 152--157, 2003.

Digital Library

[12]

Min Pan and Chris Chu. "FastRoute: A Step to Integrate Global Routing into Placement," ICCAD, Pages 464--471, 2006.

Digital Library

[13]

M. Wang, X. Yang, M. Sarrafzadeh. "Dragon2000: standard-cell placement tool for large industry circuits," ICCAD, Pages 260--263, 200.

Digital Library

[14]

C. Li, M. Xie, C.-K. Koh, J. Cong, and P. H. Madden. "Routability-driven placement and white space allocation," ICCAD, Pages 394--401, 2004.

Digital Library

[15]

Z.-W. Jiang, B.-Y. Su, and Y.-W. Chang. "Routability-Driven Analytical Placement by Net Overlapping Removal for Large-Scale Mixed-Size Designs," DAC, Pages 167--172 2008.

Digital Library

[16]

J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert and I. L. Markov. "CRISP: Congestion Reduction by Iterated Spreading during Placement," ICCAD, Pages 357--362, 2009.

Digital Library

[17]

Yanheng Zhang and Chris Chu. "CROP: Fast and Effective Congestion Refinement of Placement," ICCAD, Pages 344--350, 2009.

Digital Library

[18]

Minsik Cho and David Z. Pan. "BoxRouter: a new global router based on box expansion and progressive ILP," DAC, 373--378, 2006.

Digital Library

[19]

Sadiq M Sait and Habib Youssef. "VLSI Physical Design Automation: Theory and Practice," Baker & Taylor Books, 1999.

Digital Library

[20]

P. Chong and R. K. Brayton. "Estimating and Optimizing Routing Utilization in DSM Design," In International Workshop on System-Level Interconnect Prediction. ACM, April 1999.

[21]

H. B. Bakoglu. "Circuits, Interconnections, and Packaging for VLSI," Addison-Wesley, 1990.

[22]

http://docs.google.com/leaf?id=0BzieVrl9EJV6YjlhODUyNmYtYjk5Ny00MTg4LWFjYTItZDc4YmQ4YmYxM2Iz&hl=en

[23]

http://www.springsoft.com/news-events/news/product-news/laker-placeandroute-03152010

Cited By

Liu WChien TWang TFettweis GNebel W(2014)Metal layer planning for silicon interposers with consideration of routability and manufacturing costProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2617112(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2617112
Alpert CLi ZNam GSze CViswanathan NWard SHu A(2012)PlacementProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429442(283-290)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429442
Tsay RChang YHu J(2011)From academic ideas to practical physical design toolsProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960403(9-12)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960403

Index Terms

Cut-demand based routing resource allocation and consolidation for routability enhancement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Hardware validation

Recommendations

Routability driven white space allocation for fixed-die standard-cell placement
ISPD '02: Proceedings of the 2002 international symposium on Physical design

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 ...
Resource reconstruction algorithms for on-demand allocation in virtual computing resource pool

Resource reconstruction algorithms are studied in this paper to solve the problem of resource on-demand allocation and improve the efficiency of resource utilization in virtual computing resource pool. Based on the idea of resource virtualization and ...
Fast and accurate routing demand estimation for efficient routability-driven placement
DATE '07: Proceedings of the conference on Design, automation and test in Europe

This paper presents a fast and accurate routing demand estimation called RUDY and its efficient integration in a force-directed quadratic placer to optimize placements for routability.

RUDY is based on a Rectangular Uniform wire DensitY per net and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPDAC '11: Proceedings of the 16th Asia and South Pacific Design Automation Conference

January 2011

841 pages

ISBN:9781424475162

Sponsors

IEEE
IPSJ
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEICE

Publisher

IEEE Press

Publication History

Published: 25 January 2011

Check for updates

Qualifiers

Research-article

Conference

ASPDAC '11

Sponsor:

SIGDA
IEICE ESS

ASPDAC '11: 16th Asia and South Pacific Design Automation Conference

January 25 - 28, 2011

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
106
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu WChien TWang TFettweis GNebel W(2014)Metal layer planning for silicon interposers with consideration of routability and manufacturing costProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2617112(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2617112
Alpert CLi ZNam GSze CViswanathan NWard SHu A(2012)PlacementProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429442(283-290)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429442
Tsay RChang YHu J(2011)From academic ideas to practical physical design toolsProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960403(9-12)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960403

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents