Redundant-via enhanced maze routing for yield improvement

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

doi:10.1145/1120725.1120927

Redundant-via enhanced maze routing for yield improvement

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

75 Citations (Scopus)

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 language	English
Title of host publication	ASP-DAC '05
Subtitle of host publication	Proceedings of the 2005 Asia and South Pacific Design Automation Conference
Place of Publication	United States
Publisher	Association for Computing Machinery (ACM)
Pages	1148-1151
Number of pages	4
Volume	2
ISBN (Electronic)	9780780387379
ISBN (Print)	0780387368, 9780780387362
DOIs	https://doi.org/10.1145/1120725.1120927
Publication status	Published - Jan 2005
Event	10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Hotel Equatorial, Shanghai, China Duration: 18 Jan 2005 → 21 Jan 2005 https://www.aspdac.com/aspdac2005/ (Conference website)

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference	10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Country/Territory	China
City	Shanghai
Period	18/01/05 → 21/01/05
Internet address	https://www.aspdac.com/aspdac2005/ (Conference website)

Scopus Subject Areas

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

Access to Document

10.1145/1120725.1120927

Cite this

Xu, G., Huang, L. D., Pan, D. Z., & Wong, M. D. F. (2005). Redundant-via enhanced maze routing for yield improvement. In ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference (Vol. 2, pp. 1148-1151). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). Association for Computing Machinery (ACM). https://doi.org/10.1145/1120725.1120927

@inproceedings{15309315f00946dfa4acd82993810d38,

title = "Redundant-via enhanced maze routing for yield improvement",

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.",

author = "Gang Xu and Huang, {Li Da} and Pan, {David Z.} and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-0306244 and IBM Faculty Award. We used computers donated by Intel Corporation. Publisher copyright: {\textcopyright} 2005 ACM; 10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 ; Conference date: 18-01-2005 Through 21-01-2005",

year = "2005",

month = jan,

doi = "10.1145/1120725.1120927",

language = "English",

isbn = "0780387368",

volume = "2",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "Association for Computing Machinery (ACM)",

pages = "1148--1151",

booktitle = "ASP-DAC '05",

address = "United States",

url = "https://www.aspdac.com/aspdac2005/",

}

Xu, G, Huang, LD, Pan, DZ & Wong, MDF 2005, Redundant-via enhanced maze routing for yield improvement. in ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference. vol. 2, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, Association for Computing Machinery (ACM), United States, pp. 1148-1151, 10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005, Shanghai, China, 18/01/05. https://doi.org/10.1145/1120725.1120927

Redundant-via enhanced maze routing for yield improvement. / Xu, Gang; Huang, Li Da; Pan, David Z. et al.
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference. Vol. 2 United States: Association for Computing Machinery (ACM), 2005. p. 1148-1151 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Redundant-via enhanced maze routing for yield improvement

AU - Xu, Gang

AU - Huang, Li Da

AU - Pan, David Z.

AU - Wong, Martin D. F.

N1 - Funding information: This work was partially supported by the National Science Foundation under grant CCR-0306244 and IBM Faculty Award. We used computers donated by Intel Corporation. Publisher copyright: © 2005 ACM

PY - 2005/1

Y1 - 2005/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84861424964&partnerID=8YFLogxK

U2 - 10.1145/1120725.1120927

DO - 10.1145/1120725.1120927

M3 - Conference proceeding

AN - SCOPUS:84861424964

SN - 0780387368

SN - 9780780387362

VL - 2

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 1148

EP - 1151

BT - ASP-DAC '05

PB - Association for Computing Machinery (ACM)

CY - United States

T2 - 10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005

Y2 - 18 January 2005 through 21 January 2005

ER -

Xu G, Huang LD, Pan DZ, Wong MDF. Redundant-via enhanced maze routing for yield improvement. In ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference. Vol. 2. United States: Association for Computing Machinery (ACM). 2005. p. 1148-1151. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). doi: 10.1145/1120725.1120927

Redundant-via enhanced maze routing for yield improvement

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this