Via minimization by layout modification

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

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

13 Citations (Scopus)


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 languageEnglish
Title of host publication26th ACM/IEEE Design Automation Conference - Proceedings 1989
PublisherAssociation for Computing Machinery (ACM)
Number of pages4
ISBN (Print)9780897913102, 0897913108
Publication statusPublished - 1 Jun 1989
Event26th ACM/IEEE Design Automation Conference, DAC 1989 - Las Vegas, United States
Duration: 25 Jun 198929 Jun 1989

Publication series

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


Conference26th ACM/IEEE Design Automation Conference, DAC 1989
Country/TerritoryUnited States
CityLas Vegas
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Control and Systems Engineering

Cite this