Via Minimization in VLSI Routing with Movable Terminals

Jitender S. Deogun; Bhargab B. Bhattacharya

doi:10.1109/43.31550

Via Minimization in VLSI Routing with Movable Terminals

Jitender S. Deogun, Bhargab B. Bhattacharya

Computer Science and Engineering

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

9 Scopus citations

Abstract

In this paper we develop a unified approach for solving the general problem of minimizing the number of “via holes” in a two-layer VLSI channel and switchbox routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switchbox routing, and (iii) four-sided switchbox routing. To solve the via minimization problem, we introduce the concept of a maximum parallel set of edges in a bipartite graph. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is 0(N log N), in all three cases, where N is the number of pairs of terminals to be connected.

Original language	English (US)
Pages (from-to)	917-920
Number of pages	4
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	8
Issue number	8
DOIs	https://doi.org/10.1109/43.31550
State	Published - Aug 1989

Keywords

Design automation
VLSI channel and switchbox routing
permutation graphs
via-minimization

ASJC Scopus subject areas

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/43.31550

Cite this

@article{da403b1c5f6a4ec08783e03d042f4416,

title = "Via Minimization in VLSI Routing with Movable Terminals",

abstract = "In this paper we develop a unified approach for solving the general problem of minimizing the number of “via holes” in a two-layer VLSI channel and switchbox routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switchbox routing, and (iii) four-sided switchbox routing. To solve the via minimization problem, we introduce the concept of a maximum parallel set of edges in a bipartite graph. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is 0(N log N), in all three cases, where N is the number of pairs of terminals to be connected.",

keywords = "Design automation, VLSI channel and switchbox routing, permutation graphs, via-minimization",

author = "Deogun, {Jitender S.} and Bhattacharya, {Bhargab B.}",

year = "1989",

month = aug,

doi = "10.1109/43.31550",

language = "English (US)",

volume = "8",

pages = "917--920",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "8",

}

TY - JOUR

T1 - Via Minimization in VLSI Routing with Movable Terminals

AU - Deogun, Jitender S.

AU - Bhattacharya, Bhargab B.

PY - 1989/8

Y1 - 1989/8

N2 - In this paper we develop a unified approach for solving the general problem of minimizing the number of “via holes” in a two-layer VLSI channel and switchbox routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switchbox routing, and (iii) four-sided switchbox routing. To solve the via minimization problem, we introduce the concept of a maximum parallel set of edges in a bipartite graph. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is 0(N log N), in all three cases, where N is the number of pairs of terminals to be connected.

AB - In this paper we develop a unified approach for solving the general problem of minimizing the number of “via holes” in a two-layer VLSI channel and switchbox routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switchbox routing, and (iii) four-sided switchbox routing. To solve the via minimization problem, we introduce the concept of a maximum parallel set of edges in a bipartite graph. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is 0(N log N), in all three cases, where N is the number of pairs of terminals to be connected.

KW - Design automation

KW - VLSI channel and switchbox routing

KW - permutation graphs

KW - via-minimization

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

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

U2 - 10.1109/43.31550

DO - 10.1109/43.31550

M3 - Article

AN - SCOPUS:0024716234

SN - 0278-0070

VL - 8

SP - 917

EP - 920

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 8

ER -

Via Minimization in VLSI Routing with Movable Terminals

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this