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

Article

Multilevel approach to full-chip gridless routing

Authors:

Yan ZhangAuthors Info & Claims

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

Pages 396 - 403

Published: 04 November 2001 Publication History

Abstract

This paper presents a novel gridless detailed routing approach based on multilevel optimization. The multilevel framework with recursive coarsening and refinement in a "V-shaped" flow allows efficient scaling of our gridless detailed router to very large designs. The downward pass of recursive coarsening builds the representations of routing regions at different levels, while the upward pass of iterative refinement allows a gradual convergence to a globally optimized solution. The use of a multicommodity flow-based routing algorithm for the initial routing at the coarsest level and a modified maze algorithm for the refinement at each level considerably improves the quality of gridless routing results. Compared with the recently published gridless detailed routing algorithm using wire planning [1], our multilevel gridless routing algorithm is 3× to 75× faster. We also compared our multilevel framework with a recently developed three-level routing approach [1] and a traditional hierarchical routing approach. Our multilevel algorithm generates better detailed routing results with higher completion rates. To our knowledge, this is the first time that multilevel optimization has been applied to IC routing.

References

[1]

J. Cong, J. Fang, and K. Khoo, "DUNE: A multi-layer gridless routing system with wire planning," in Proc. International Symposium on Physical Design, pp. 12-18, Apr. 2000.

Digital Library

[2]

J. Cong, L. He, C.-K. Koh, and P. Madden, "Performance optimization of VLSI interconnect layout," Intergration, the VLSI Journal, vol. 21, no. 1-2, pp. 1-94, 1996.

Digital Library

[3]

S. Akers, "A modification of Lee's path connection algorithm," IEEE Trans. on Computers, vol. EC-16, pp. 97-98, Feb. 1967.

[4]

J. Soukup, "Fast maze router," in Proc. 15th Design Automation Conference, pp. 100-102, 1978.

Digital Library

[5]

K. Mikami and K. Tabuchi, "A computer program for optimal routing of printed ciurcuit connectors," IFIPS Proc, vol. H-47, pp. 1475-1478, 1968.

[6]

D. Hightower, "A solution to line routing problems on the continuous plane," in Proc. IEEE 6th Design Automation Workshop, pp. 1-24, 1969.

Digital Library

[7]

R. Carden, J. Li, and C.-K. Cheng, "A global router with a theoretical bound on the optimal solution," IEEE Trans. Computer-Aided Design, vol. 15, pp. 208-216, Feb. 1996.

Digital Library

[8]

C. Albrecht, "Provably good global routing by a new approximation algorithm for multicommodity flow," in Proc. International Symposium on Physical Design, pp. 19-25, Mar. 2000.

Digital Library

[9]

J. Cong and P. Madden, "Performance driven multi-layer general area routing for PCB/MCM designs," in Proc. 35th Design Automation Conference, pp. 356-361, Jun. 1998.

Digital Library

[10]

J. Heisterman and T. Lengauer, "The efficient solution of integer programs for hierarchical global routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, pp. 748-753, Jun. 1991.

Digital Library

[11]

D. Wang and E. Kuh, "A new timing-driven multilayer mcm/ic routing algorithm," in Proc. IEEE Multi-Chip Module Conference, pp. 89-94, Feb. 1997.

Digital Library

[12]

Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1997.

[13]

J. Cong and D.-Z. Pan, "Interconnect estimation and planning for deep submicron designs," in Proc. 36th Design Automation Conference, pp. 507-510, Jun. 1999.

Digital Library

[14]

H.-P. Tseng, L. Scheffer, and C. Sechen, "Timing and crosstalk driven area routing," in Proc. 35th Design Automation Conference, pp. 378-381, Jun. 1998.

Digital Library

[15]

C. Chang and J. Cong, "Cross talk noise control in gridless general-area routing," in Proc. ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (TAU), pp. 117-122, Mar. 1999.

[16]

C. Chang and J. Cong, "Pseudo pin assignment with crosstalk noise control," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, pp. 598-611, Mar. 2001.

Digital Library

[17]

A. Brandt, "Multi-level adaptive solution to boundary value problems," Mathematics of Computation, vol. 31, no. 138, pp. 333-390, 1977.

[18]

W. Briggs, A Multigrid Tutorial. SIAM, 1987.

[19]

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel hypergraph partitioning: Applications in VLSI domain," IEEE Trans. on Very Large Scale Integration Systems, vol. 7, pp. 69-79, Mar. 1999.

Digital Library

[20]

J. Cong, S. Lim, and C. Wu, "Performance driven multilevel and multiway partitioning with retiming," in Proc. 37th Design Automation Conference, pp. 274-279, Jun. 2000.

Digital Library

[21]

T. Chan, J. Cong, T. Kong, and J. Shinnerl, "Multilevel optimization for large-scale circuit placement," in Proc. IEEE International Conference on Computer Aided Design, pp. 171-176, Nov. 2000.

Digital Library

[22]

J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization," IEEE Trans. on Computer-Aided Design, pp. 356-365, Mar. 1991.

Digital Library

[23]

J. Cong, J. Fang, and K. Khoo, "An implicit connection graph maze routing algorithm for ECO routing," in Proc. International Conference on Computer Aided Design, pp. 163-167, Nov. 1999.

Digital Library

[24]

J. Cong, A. Kahng, and K. Leung, "Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design," IEEE Trans. on Computer-Aided Design, vol. 17, pp. 24-39, Jan. 1999.

Digital Library

[25]

M. Borah, R. Owens, and M. Irwin, "An edge-based heuristic for Steiner routing," IEEE Trans. on Computer-Aided Design, vol. 13, pp. 1563-1568, Dec. 1994.

Digital Library

[26]

J. Cong and X. Yuan, "Routing tree construction under fixed buffer locations," in Proc. 37th Design Automation Conference, pp. 379-384, Jun. 2000.

Digital Library

[27]

N. Garg and J. Konemann, "Faster and simpler algorithms for multicommodity flow and other fractional packing problems," in Proc. Annual Symposium on Foundations of Computer Science, pp. 300-309, Nov. 1998.

Digital Library

[28]

R. Karp, F. Leighton, R. Rivest, C. Thompson, U. Vazirani, and V. V. Vazirani, "Global wire routing in two-dimensional arrays," Algorithmica, vol. 2, pp. 113-129, 1987.

Digital Library

[29]

E. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269-271, 1959.

Digital Library

Cited By

Gester MMüller DNieberg TPanten CSchulte CVygen J(2013)BonnRouteACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210318:2(1-24)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442103
Chaudhry MAsad ZSprintson AHu J(2011)Efficient congestion mitigation using congestion-aware steiner trees and network coding topologiesVLSI Design10.1155/2011/8923102011(1-9)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1155/2011/892310
Lai LChang HLin RAtienza DXie YAyala JStevens K(2011)RoverProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973018(37-42)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973018
Show More Cited By

Index Terms

Multilevel approach to full-chip gridless routing
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Hardware validation
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations

Recommendations

Multilevel Full-Chip Gridless Routing With Applications to Optical-Proximity Correction

To handle modern routing with nanometer effects, we need to consider designs with variable wire/via widths and spacings, for which gridless-routing approaches are desirable due to its great flexibility. In this paper, we introduce a gridless-routing ...
Novel full-chip gridless routing considering double-via insertion
DAC '06: Proceedings of the 43rd annual Design Automation Conference

As the technology node advances into the nanometer era, via-open defects are one of the dominant failures. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by foundries. Traditionally, double-via ...
A novel framework for multilevel full-chip gridless routing
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

November 2001

656 pages

ISBN:0780372492

Conference Chair:
Rolf Ernst
Tech. Univ. of Braunschweig, Braunschweig, Germany

Sponsors

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

Publisher

IEEE Press

Publication History

Published: 04 November 2001

Check for updates

Qualifiers

Article

Conference

ICCAD01

Sponsor:

SIGDA

ICCAD01: International Conference on Computer Aided Design

November 4 - 8, 2001

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
297
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gester MMüller DNieberg TPanten CSchulte CVygen J(2013)BonnRouteACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210318:2(1-24)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442103
Chaudhry MAsad ZSprintson AHu J(2011)Efficient congestion mitigation using congestion-aware steiner trees and network coding topologiesVLSI Design10.1155/2011/8923102011(1-9)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1155/2011/892310
Lai LChang HLin RAtienza DXie YAyala JStevens K(2011)RoverProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973018(37-42)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973018
Chen HChiang MChang YChen LHan BSentovich E(2006)Novel full-chip gridless routing considering double-via insertionProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147101(755-760)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147101
Chen HLin ZScheffer L(2006)NEMOProceedings of the 2006 international symposium on Physical design10.1145/1123008.1123022(64-71)Online publication date: 9-Apr-2006
https://dl.acm.org/doi/10.1145/1123008.1123022
Chen TChang YLin SHirose F(2006)A novel framework for multilevel full-chip gridless routingProceedings of the 2006 Asia and South Pacific Design Automation Conference10.1145/1118299.1118448(636-641)Online publication date: 24-Jan-2006
https://dl.acm.org/doi/10.1145/1118299.1118448
Chen TChang YLin S(2005)IMFProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129626(159-164)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129626
Xiong JHe LTang T(2005)Probabilistic congestion model considering shielding for crosstalk reductionProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1121006(739-742)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1121006
Chen TChang YTang T(2005)Multilevel full-chip gridless routing considering optical proximity correctionProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120930(1160-1163)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120930
Cong JZhang YTang T(2005)Thermal-driven multilevel routing for 3-D ICsProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120787(121-126)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120787
Show More Cited By

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