Optimal via-shifting in channel compaction

Yang Cai; D. F. Wong

doi:10.1109/EDAC.1990.136642

Optimal via-shifting in channel compaction

Yang Cai, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

3 Citations (Scopus)

Abstract

The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_c be the number of grid points on column c that are occupied by vias. Let w_c be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity h_c=Av_c+Bw_c+C, where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let H_S be the height of the critical column(s) in S. In general, H_S is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize H_S can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log²(V+L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively.

Original language	English
Title of host publication	Proceedings of the European Design Automation Conference, EDAC 1990
Publisher	IEEE
Pages	186-190
Number of pages	5
ISBN (Print)	0818620242, 9780818620249
DOIs	https://doi.org/10.1109/EDAC.1990.136642
Publication status	Published - Mar 1990
Event	1990 European Design Automation Conference, EDAC 1990 - Glasgow, United Kingdom Duration: 12 Mar 1990 → 15 Mar 1990 https://ieeexplore.ieee.org/xpl/conhome/273/proceeding

Publication series

Name	Proceedings of the European Design Automation Conference, EDAC

Conference

Conference	1990 European Design Automation Conference, EDAC 1990
Country/Territory	United Kingdom
City	Glasgow
Period	12/03/90 → 15/03/90
Internet address	https://ieeexplore.ieee.org/xpl/conhome/273/proceeding

Scopus Subject Areas

Hardware and Architecture
Electrical and Electronic Engineering
Control and Optimization
Modelling and Simulation

Access to Document

10.1109/EDAC.1990.136642

Cite this

@inproceedings{66fb9b0d6bab4ee1932719da45f57e28,

title = "Optimal via-shifting in channel compaction",

abstract = "The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc be the number of grid points on column c that are occupied by vias. Let wc be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity hc=Avc+Bwc+C, where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let HS be the height of the critical column(s) in S. In general, HS is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize HS can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log2(V+L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively.",

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

note = "Funding information: This work was partially supported by the Texas Advanced Research Program under grant 4096, by the National Science Foundation under grant MIP-8909586, and by an IBM Faculty Development Award. Publisher Copyright: {\textcopyright} 1990 IEEE.; 1990 European Design Automation Conference, EDAC 1990 ; Conference date: 12-03-1990 Through 15-03-1990",

year = "1990",

month = mar,

doi = "10.1109/EDAC.1990.136642",

language = "English",

isbn = "0818620242",

series = "Proceedings of the European Design Automation Conference, EDAC",

publisher = "IEEE",

pages = "186--190",

booktitle = "Proceedings of the European Design Automation Conference, EDAC 1990",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/273/proceeding",

}

TY - GEN

T1 - Optimal via-shifting in channel compaction

AU - Cai, Yang

AU - Wong, D. F.

N1 - Funding information: This work was partially supported by the Texas Advanced Research Program under grant 4096, by the National Science Foundation under grant MIP-8909586, and by an IBM Faculty Development Award. Publisher Copyright: © 1990 IEEE.

PY - 1990/3

Y1 - 1990/3

N2 - The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc be the number of grid points on column c that are occupied by vias. Let wc be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity hc=Avc+Bwc+C, where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let HS be the height of the critical column(s) in S. In general, HS is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize HS can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log2(V+L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively.

AB - The authors study the problem of shifting vias to obtain more compactable two-layer channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc be the number of grid points on column c that are occupied by vias. Let wc be the number of grid points on column c that are occupied by horizontal wires. They define the height of a column c to be the quantity hc=Avc+Bwc+C, where A, B, C are some design rule dependent constants. A column is said to be critical if it is a column with maximum height. Let HS be the height of the critical column(s) in S. In general, HS is a good measure of the channel height after compaction. They show that the problem of shifting vias to minimize HS can be solved optimally in polynomial time. The complexity of the optimal via-shifting algorithm is O(WL(V+L)log2(V+L)) where W, L, and V are the number of tracks in S, the number of columns in S, and the number of vias in S, respectively.

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

U2 - 10.1109/EDAC.1990.136642

DO - 10.1109/EDAC.1990.136642

M3 - Conference proceeding

AN - SCOPUS:67650192796

SN - 0818620242

SN - 9780818620249

T3 - Proceedings of the European Design Automation Conference, EDAC

SP - 186

EP - 190

BT - Proceedings of the European Design Automation Conference, EDAC 1990

PB - IEEE

T2 - 1990 European Design Automation Conference, EDAC 1990

Y2 - 12 March 1990 through 15 March 1990

ER -

Optimal via-shifting in channel compaction

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this