Layer assignment for multi-layer PCB and VLSI routing

Kuo En Chang; Sung Chuan Fang

doi:10.1080/02533839.1991.9677348

Layer assignment for multi-layer PCB and VLSI routing

Kuo En Chang^*, Sung Chuan Fang

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

Original language	English
Pages (from-to)	373-382
Number of pages	10
Journal	Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume	14
Issue number	4
DOIs	https://doi.org/10.1080/02533839.1991.9677348
Publication status	Published - 1991 Jun

Keywords

Graph contractability
Layer assignment
NP-compIete
Via minimization

ASJC Scopus subject areas

General Engineering

Access to Document

10.1080/02533839.1991.9677348

Cite this

@article{27675e2011cf4c26953c85f1f6ca0a71,

title = "Layer assignment for multi-layer PCB and VLSI routing",

abstract = "The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch{\textquoteright}s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.",

keywords = "Graph contractability, Layer assignment, NP-compIete, Via minimization",

author = "Chang, {Kuo En} and Fang, {Sung Chuan}",

year = "1991",

month = jun,

doi = "10.1080/02533839.1991.9677348",

language = "English",

volume = "14",

pages = "373--382",

journal = "Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an",

issn = "0253-3839",

publisher = "Chinese Institute of Engineers",

number = "4",

}

TY - JOUR

T1 - Layer assignment for multi-layer PCB and VLSI routing

AU - Chang, Kuo En

AU - Fang, Sung Chuan

PY - 1991/6

Y1 - 1991/6

N2 - The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

AB - The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

KW - Graph contractability

KW - Layer assignment

KW - NP-compIete

KW - Via minimization

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

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

U2 - 10.1080/02533839.1991.9677348

DO - 10.1080/02533839.1991.9677348

M3 - Article

AN - SCOPUS:0026190657

SN - 0253-3839

VL - 14

SP - 373

EP - 382

JO - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

JF - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

IS - 4

ER -

Layer assignment for multi-layer PCB and VLSI routing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this