An interconnect reliability-driven routing technique for electromigration failure avoidance

As VLSI technology enters the nanoscale regime, design reliability is becoming increasingly important. A major design reliability concern arises from electromigration which refers to the transport of material caused by ion movement in interconnects. Since the lifetime of an interconnect drastically depends on the current flowing through it, the electromigration problem aggravates with increasingly growing thinner wires. Further, the current-density-induced interconnect thermal issue becomes much more severe with larger current. To mitigate the electromigration and the current-density- induced thermal effects, interconnect current density needs to be reduced. Assigning wires to thick metals increases wire volume, and thus, reduces the current density. However, overstretching thick-metal assignment may hurt routability. Thus, it is highly desirable to minimize the thick-metal usage, or total wire cost, subject to the reliability constraint. In this paper, the minimum cost reliability-driven routing, which consists of Steiner tree construction and layer assignment, is considered. The problem is proven to be NP-hard and a highly effective iterative rounding-based integer linear programming algorithm is proposed. In addition, a unified routing technique is proposed to directly handle multiple current levels, which is critical in analog VLSI design. Further, the new algorithm is extended to handle blockage. Our experiments on 450 nets demonstrate that the new algorithm significantly outperforms the state-of-the-art work [CHECK END OF SENTENCE] with up to 14.7 percent wire reduction. In addition, the new algorithm can save 11.4 percent wires over a heuristic algorithm for handling multiple currents. © 2012 IEEE