Redundant-via enhanced maze routing for yield improvement

Gang Xu, Li Da Huang, David Z. Pan, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

74 Citations (Scopus)


Redundant via insertion is a good solution to reduce the yield loss by via failure. However, the existing methods are all post-layout optimizations that insert redundant via after detailed routing. In this paper, we propose the first routing algorithm that considers feasibility of redundant via insertion in the detailed routing stage. Our routing problem is formulated as maze routing with redundant via constraints. The problem is transformed to a multiple constraint shortest path problem, and solved by Lagrangian relaxation technique. Experimental results show that our algorithm can find routing layout with much higher rate of redundant via than conventional maze routing.

Original languageEnglish
Title of host publicationASP-DAC '05
Subtitle of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Number of pages4
ISBN (Electronic)9780780387379
Publication statusPublished - Jan 2005
Event10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Hotel Equatorial, Shanghai, China
Duration: 18 Jan 200521 Jan 2005 (Conference website)


Conference10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Redundant-via enhanced maze routing for yield improvement'. Together they form a unique fingerprint.

Cite this