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

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].