TY - GEN
T1 - Negotiation-based layer assignment for via count and via overflow minimization
AU - Liu, Wen H.
AU - Li, Yih-Lang
PY - 2011/3/28
Y1 - 2011/3/28
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=79952933977&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2011.5722248
DO - 10.1109/ASPDAC.2011.5722248
M3 - Conference contribution
AN - SCOPUS:79952933977
SN - 9781424475155
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 539
EP - 544
BT - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
T2 - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Y2 - 25 January 2011 through 28 January 2011
ER -