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 contribution

Abstract

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 (US)
Title of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Pages1148-1151
Number of pages4
StatePublished - Dec 1 2005
Event2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Shanghai, China
Duration: Jan 18 2005Jan 21 2005

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume2

Other

Other2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005
CountryChina
CityShanghai
Period1/18/051/21/05

    Fingerprint

ASJC Scopus subject areas

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

Cite this

Xu, G., Huang, L. D., Pan, D. Z., & Wong, M. D. F. (2005). Redundant-via enhanced maze routing for yield improvement. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005 (pp. 1148-1151). [1466544] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2).