Efficient Via Shifting Algorithms in Channel Compaction

Yang Cai; D. F. Wong

doi:10.1109/43.251148

Efficient Via Shifting Algorithms in Channel Compaction

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

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 (US)
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
State	Published - Dec 1993
Externally published	Yes

ASJC Scopus subject areas

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

Online availability

10.1109/43.251148

Library availability

Discover UIUC Full Text

Cite this

@article{c85657cb92494dbabd0ff5e49139f670,

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: Manuscript received February 10, 1993; revised June 9, 1993. 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. Previous versions of this paper have appeared in Proceedings of the First European Design Automation Conference, and Proceedings of the I991 International Symposium on Circuits and Systems. This paper was recommended by Editor M. Marek-Sadowska. Y. Cai was with the Department of Computer Sciences, University of Texas, Austin, TX. He is now with ArcSys, Inc., Sunnyvale, CA 94086. D. F. Wong is with the Department of Computer Sciences, University of Texas, Austin, TX 78712. IEEE Log Number 9212350.",

year = "1993",

month = dec,

doi = "10.1109/43.251148",

language = "English (US)",

volume = "12",

pages = "1848--1857",

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

issn = "0278-0070",

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

number = "12",

}

TY - JOUR

T1 - Efficient Via Shifting Algorithms in Channel Compaction

AU - Cai, Yang

AU - Wong, D. F.

N1 - Funding Information: Manuscript received February 10, 1993; revised June 9, 1993. 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. Previous versions of this paper have appeared in Proceedings of the First European Design Automation Conference, and Proceedings of the I991 International Symposium on Circuits and Systems. This paper was recommended by Editor M. Marek-Sadowska. Y. Cai was with the Department of Computer Sciences, University of Texas, Austin, TX. He is now with ArcSys, Inc., Sunnyvale, CA 94086. D. F. Wong is with the Department of Computer Sciences, University of Texas, Austin, TX 78712. IEEE Log Number 9212350.

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

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

U2 - 10.1109/43.251148

DO - 10.1109/43.251148

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

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this