Via minimization by layout modification

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

Research output: Contribution to journalConference articlepeer-review


A novel approach to the two-layer via minimization problem that systematically eliminates vias by modifying the routing layout is proposed. The authors have implemented the proposed algorithm, 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 this algorithm is more effective in via reduction and more efficient in running time than conventional via minimization algorithms. In particular, for Burstein's 19-track solution to Deutsch's difficult problem, the proposed algorithm obtains 34% reduction in the number of vias, which is an improvement of more than 11% over the conventional CVM (constrained via minimization) approach. The application of the algorithm to various solutions to Deutsch's difficult problem produces (to the authors' knowledge) the fewest vias ever reported in the literature.

Original languageEnglish (US)
Pages (from-to)799-802
Number of pages4
JournalProceedings - Design Automation Conference
StatePublished - 1989
Externally publishedYes
Event26th ACM/IEEE Design Automation Conference - Las Vegas, NV, USA
Duration: Jun 25 1989Jun 29 1989

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Cite this