Constrained via minimization for three-layer routing

Kuo-En Chang, H. F. Jyu, W. S. Feng

Research output: Contribution to journalArticle

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

Original languageEnglish
Pages (from-to)346-354
Number of pages9
JournalComputer-Aided Design
Volume21
Issue number6
DOIs
Publication statusPublished - 1989 Jan 1

Fingerprint

Constrained Minimization
Heuristic algorithms
Routing
Wire
Contractibility
Graph Model
Interconnection
Heuristic algorithm
Minimization Problem
Fast Algorithm
Experimental Results
Graph in graph theory

Keywords

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

ASJC Scopus subject areas

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

Cite this

Constrained via minimization for three-layer routing. / Chang, Kuo-En; Jyu, H. F.; Feng, W. S.

In: Computer-Aided Design, Vol. 21, No. 6, 01.01.1989, p. 346-354.

Research output: Contribution to journalArticle

Chang, Kuo-En ; Jyu, H. F. ; Feng, W. S. / Constrained via minimization for three-layer routing. In: Computer-Aided Design. 1989 ; Vol. 21, No. 6. pp. 346-354.
@article{573d5e6c867240769bcc67a0e429cde6,
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 = "VLSI design, computer-aided design, graph contractibility, layer assignment, via minimization",
author = "Kuo-En Chang and Jyu, {H. F.} and Feng, {W. S.}",
year = "1989",
month = "1",
day = "1",
doi = "10.1016/0010-4485(89)90001-8",
language = "English",
volume = "21",
pages = "346--354",
journal = "CAD Computer Aided Design",
issn = "0010-4485",
publisher = "Elsevier Limited",
number = "6",

}

TY - JOUR

T1 - Constrained via minimization for three-layer routing

AU - Chang, Kuo-En

AU - Jyu, H. F.

AU - Feng, W. S.

PY - 1989/1/1

Y1 - 1989/1/1

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 - VLSI design

KW - computer-aided design

KW - graph contractibility

KW - layer assignment

KW - via minimization

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

VL - 21

SP - 346

EP - 354

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

SN - 0010-4485

IS - 6

ER -