Via minimization by layout modification

Khe Sing The; D. F. Wong; Jingsheng Cong

doi:10.1145/74382.74533

Via minimization by layout modification

Khe Sing The^*, D. F. Wong, Jingsheng Cong

^*Corresponding author for this work

Office of the Provost

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

13 Citations (Scopus)

Abstract

We present in this paper a new approach to the two-layer via minimization problem. Our approach is to systematically eliminate vias by modifying the routing layout. We have implemented our algorithm and applied it to benchmark routing layouts published in the literature, and obtained significant reduction in the number of vias without increasing the routing area. The experimental results show that our algorithm is more effective in via reduction and more efficient in running time compared to conventional via minimization algorithms. In particular, for Burstein's 19 track solution to Deutsch's difficult problem, our algorithm obtains 34% reduction in the number of vias, which is more than 11% improvement over the conventional CVM (constrained via minimization) approach. The application of our algorithm to various solutions to the Deutsch's difficult problem produces the fewest numbers of vias ever reported in the literature.

Original language	English
Title of host publication	26th ACM/IEEE Design Automation Conference - Proceedings 1989
Publisher	Association for Computing Machinery (ACM)
Pages	799-802
Number of pages	4
ISBN (Print)	9780897913102, 0897913108
DOIs	https://doi.org/10.1145/74382.74533
Publication status	Published - 1 Jun 1989
Event	26th ACM/IEEE Design Automation Conference, DAC 1989 - Las Vegas, United States Duration: 25 Jun 1989 → 29 Jun 1989 https://dl.acm.org/doi/proceedings/10.1145/74382 https://ieeexplore.ieee.org/xpl/conhome/10574/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	26th ACM/IEEE Design Automation Conference, DAC 1989
Country/Territory	United States
City	Las Vegas
Period	25/06/89 → 29/06/89
Internet address	https://dl.acm.org/doi/proceedings/10.1145/74382 https://ieeexplore.ieee.org/xpl/conhome/10574/proceeding

Scopus Subject Areas

Hardware and Architecture
Control and Systems Engineering

Access to Document

10.1145/74382.74533

Cite this

@inproceedings{8f9b6a8e88d1474596f3bacd45524f30,

title = "Via minimization by layout modification",

abstract = "We present in this paper a new approach to the two-layer via minimization problem. Our approach is to systematically eliminate vias by modifying the routing layout. We have implemented our algorithm and applied it to benchmark routing layouts published in the literature, and obtained significant reduction in the number of vias without increasing the routing area. The experimental results show that our algorithm is more effective in via reduction and more efficient in running time compared to conventional via minimization algorithms. In particular, for Burstein's 19 track solution to Deutsch's difficult problem, our algorithm obtains 34% reduction in the number of vias, which is more than 11% improvement over the conventional CVM (constrained via minimization) approach. The application of our algorithm to various solutions to the Deutsch's difficult problem produces the fewest numbers of vias ever reported in the literature.",

author = "The, {Khe Sing} and Wong, {D. F.} and Jingsheng Cong",

note = "The work of the first two authors was partially supported by the Texas Advanced Research Program under Grant No. 4096. The third author was partially supported by a grant from the Digital Equipment Corporation and by a grant from the General Electric Company.; 26th ACM/IEEE Design Automation Conference, DAC 1989 ; Conference date: 25-06-1989 Through 29-06-1989",

year = "1989",

month = jun,

day = "1",

doi = "10.1145/74382.74533",

language = "English",

isbn = "9780897913102",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "799--802",

booktitle = "26th ACM/IEEE Design Automation Conference - Proceedings 1989",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/74382, https://ieeexplore.ieee.org/xpl/conhome/10574/proceeding",

}

The, KS, Wong, DF & Cong, J 1989, Via minimization by layout modification. in 26th ACM/IEEE Design Automation Conference - Proceedings 1989. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 799-802, 26th ACM/IEEE Design Automation Conference, DAC 1989, Las Vegas, Nevada, United States, 25/06/89. https://doi.org/10.1145/74382.74533

TY - GEN

T1 - Via minimization by layout modification

AU - The, Khe Sing

AU - Wong, D. F.

AU - Cong, Jingsheng

N1 - The work of the first two authors was partially supported by the Texas Advanced Research Program under Grant No. 4096. The third author was partially supported by a grant from the Digital Equipment Corporation and by a grant from the General Electric Company.

PY - 1989/6/1

Y1 - 1989/6/1

N2 - We present in this paper a new approach to the two-layer via minimization problem. Our approach is to systematically eliminate vias by modifying the routing layout. We have implemented our algorithm and applied it to benchmark routing layouts published in the literature, and obtained significant reduction in the number of vias without increasing the routing area. The experimental results show that our algorithm is more effective in via reduction and more efficient in running time compared to conventional via minimization algorithms. In particular, for Burstein's 19 track solution to Deutsch's difficult problem, our algorithm obtains 34% reduction in the number of vias, which is more than 11% improvement over the conventional CVM (constrained via minimization) approach. The application of our algorithm to various solutions to the Deutsch's difficult problem produces the fewest numbers of vias ever reported in the literature.

AB - We present in this paper a new approach to the two-layer via minimization problem. Our approach is to systematically eliminate vias by modifying the routing layout. We have implemented our algorithm and applied it to benchmark routing layouts published in the literature, and obtained significant reduction in the number of vias without increasing the routing area. The experimental results show that our algorithm is more effective in via reduction and more efficient in running time compared to conventional via minimization algorithms. In particular, for Burstein's 19 track solution to Deutsch's difficult problem, our algorithm obtains 34% reduction in the number of vias, which is more than 11% improvement over the conventional CVM (constrained via minimization) approach. The application of our algorithm to various solutions to the Deutsch's difficult problem produces the fewest numbers of vias ever reported in the literature.

UR - https://dl.acm.org/doi/10.1145/74382.74533

UR - https://ieeexplore.ieee.org/document/1586498

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

U2 - 10.1145/74382.74533

DO - 10.1145/74382.74533

M3 - Conference proceeding

AN - SCOPUS:0024891491

SN - 9780897913102

SN - 0897913108

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 799

EP - 802

BT - 26th ACM/IEEE Design Automation Conference - Proceedings 1989

PB - Association for Computing Machinery (ACM)

T2 - 26th ACM/IEEE Design Automation Conference, DAC 1989

Y2 - 25 June 1989 through 29 June 1989

ER -

Via minimization by layout modification

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this