Constrained via minimization for three-layer routing

K. E. Chang; H. F. Jyu; W. S. Feng

doi:10.1016/0010-4485(89)90001-8

Constrained via minimization for three-layer routing

K. E. Chang^*, H. F. Jyu, W. S. Feng

^*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

The constrained via minimization problem for VLSI three-layer 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. This problem has been shown to be NP-complete¹⁵. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.

Original language	English
Pages (from-to)	346-354
Number of pages	9
Journal	Computer-Aided Design
Volume	21
Issue number	6
DOIs	https://doi.org/10.1016/0010-4485(89)90001-8
Publication status	Published - 1989
Externally published	Yes

Keywords

computer-aided design
graph contractibility
layer assignment
via minimization
VLSI design

ASJC Scopus subject areas

Computer Science Applications
Computer Graphics and Computer-Aided Design
Industrial and Manufacturing Engineering

Access to Document

10.1016/0010-4485(89)90001-8

Cite this

@article{ccaab3d332024bf597154b24126f7186,

title = "Constrained via minimization for three-layer routing",

abstract = "The constrained via minimization problem for VLSI three-layer 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. This problem has been shown to be NP-complete15. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.",

keywords = "computer-aided design, graph contractibility, layer assignment, via minimization, VLSI design",

author = "Chang, {K. E.} and Jyu, {H. F.} and Feng, {W. S.}",

year = "1989",

doi = "10.1016/0010-4485(89)90001-8",

language = "English",

volume = "21",

pages = "346--354",

journal = "Computer-Aided Design",

issn = "0010-4485",

publisher = "Elsevier Limited",

number = "6",

}

TY - JOUR

T1 - Constrained via minimization for three-layer routing

AU - Chang, K. E.

AU - Jyu, H. F.

AU - Feng, W. S.

PY - 1989

Y1 - 1989

N2 - The constrained via minimization problem for VLSI three-layer 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. This problem has been shown to be NP-complete15. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.

AB - The constrained via minimization problem for VLSI three-layer 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. This problem has been shown to be NP-complete15. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.

KW - computer-aided design

KW - graph contractibility

KW - layer assignment

KW - via minimization

KW - VLSI design

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

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

U2 - 10.1016/0010-4485(89)90001-8

DO - 10.1016/0010-4485(89)90001-8

M3 - Article

AN - SCOPUS:0024700860

SN - 0010-4485

VL - 21

SP - 346

EP - 354

JO - Computer-Aided Design

JF - Computer-Aided Design

IS - 6

ER -

Constrained via minimization for three-layer routing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this