Efficient Via Shifting Algorithms in Channel Compaction

Yang Cai; D. F. Wong

doi:10.1109/43.251148

Efficient Via Shifting Algorithms in Channel Compaction

Yang Cai, D. F. Wong

Office of the Provost

Research output: Contribution to journal › Journal article › peer-review

1 Citation (Scopus)

Abstract

We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_c, w_cbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be h_c = Av_c + Bw_c + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let H_s= max_ch_cbe the expected height of the critical column(s) of S. H_sis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize H_scan be solved optimally in polynomial time.

Original language	English
Pages (from-to)	1848-1857
Number of pages	10
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	12
Issue number	12
DOIs	https://doi.org/10.1109/43.251148
Publication status	Published - Dec 1993

Scopus Subject Areas

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

Access to Document

10.1109/43.251148

Cite this

@article{31bfe2653d4c4e4ba21d24fc088d5261,

title = "Efficient Via Shifting Algorithms in Channel Compaction",

abstract = "We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc, wcbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be hc = Avc + Bwc + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let Hs= maxchcbe the expected height of the critical column(s) of S. Hsis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize Hscan be solved optimally in polynomial time.",

author = "Yang Cai and Wong, {D. F.}",

note = "Funding Information: This work was supported in part by the National Science Foundation under Grant MIP-8909586, by an IBM Faculty Development Award, and by an ACM SIGDA Scholarship. Publisher Copyright: {\textcopyright} 1993 IEEE",

year = "1993",

month = dec,

doi = "10.1109/43.251148",

language = "English",

volume = "12",

pages = "1848--1857",

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

issn = "0278-0070",

publisher = "IEEE",

number = "12",

}

TY - JOUR

T1 - Efficient Via Shifting Algorithms in Channel Compaction

AU - Cai, Yang

AU - Wong, D. F.

N1 - Funding Information: This work was supported in part by the National Science Foundation under Grant MIP-8909586, by an IBM Faculty Development Award, and by an ACM SIGDA Scholarship. Publisher Copyright: © 1993 IEEE

PY - 1993/12

Y1 - 1993/12

N2 - We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc, wcbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be hc = Avc + Bwc + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let Hs= maxchcbe the expected height of the critical column(s) of S. Hsis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize Hscan be solved optimally in polynomial time.

AB - We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc, wcbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be hc = Avc + Bwc + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let Hs= maxchcbe the expected height of the critical column(s) of S. Hsis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize Hscan be solved optimally in polynomial time.

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

U2 - 10.1109/43.251148

DO - 10.1109/43.251148

M3 - Journal article

AN - SCOPUS:0027840910

SN - 0278-0070

VL - 12

SP - 1848

EP - 1857

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 - 12

ER -

Efficient Via Shifting Algorithms in Channel Compaction

Abstract

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this