Negotiation-based layer assignment for via count and via overflow minimization

Wen H. Liu*, Yih-Lang Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

Abstract

Layer assignment determines on which layer the wires or vias should be placed; and the assignment results influence the circuit's delay, crosstalk, and via counts. How to minimize via count and via overflow during layer assignment has received considerable attention in recent years. Traditional layer assignment to minimize via count tends to produce varying qualities of assignment results using different net orderings. This work develops a negotiation-based via count minimization algorithm (NVM) that can achieve lower via counts than in previous works, and experimental results indicate that net assignment ordering only slightly influences the quality of NVM's results. As for via overflow minimization, we observe via overflow can be well minimized if via overflow minimization is performed following stacked via minimization. The stacked via minimization adopts the proposed NVM, while via overflow minimization adopts a modified NVM by replacing via cost with via overflow cost. Experimental results reveal that the proposed NVM yields a lower additional via cost than [1] and [2] by 10.8%, 2.5%, respectively, in the via count minimization problem. As for via overflow minimization, the proposed two-stage algorithm improves via overflow by 11.5% and lowers the via cost by 6.5% than the one-stage algorithm [3].

Original languageEnglish
Title of host publication2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Pages539-544
Number of pages6
DOIs
StatePublished - 28 Mar 2011
Event2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011 - Yokohama, Japan
Duration: 25 Jan 201128 Jan 2011

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
CountryJapan
CityYokohama
Period25/01/1128/01/11

Fingerprint Dive into the research topics of 'Negotiation-based layer assignment for via count and via overflow minimization'. Together they form a unique fingerprint.

Cite this