A faster approximation scheme for timing driven minimum cost layer assignment

As VLSI technology moves to the 65nm node and beyond, interconnect delay greatly limits the circuit performance. As a critical component in interconnect synthesis, layer assignment manifests enormous potential in drastically reducing wire delay. This is due the fact that wires on thick metals are much less resistive than those on thin metals. Nevertheless, it is not desired to assign all wires to thick metals and the right strategy is to only use minimal thick-metal routing resources for meeting the timing constraints. This timing driven minimum cost layer assignment problem is NP-Complete, and a fast algorithm with provable approximation bound is highly desired. In this paper, a new fully polynomial time approximation scheme is proposed. It is based on a linear-time dynamic programming algorithm for bounded-cost layer assignment and efficient oracle queries. The proposed algorithm can approximate the optimal layer assignment solution in O(mn2/ε) time within a factor of 1 + ε for any ε \u3e 0, where n is the tree size and m is the number of routing layers. This significantly improves the previous work. The new algorithm is also highly practical. Our experiments on industrial netlists demonstrate that the new algorithm runs up to 6.5 × faster than the optimal dynamic programming with few percent additional wire as guaranteed theoretically. This gives another \u3e 2× speedup over the previous work. Copyright 2009 ACM