Layer assignment for VLSI interconnect delay minimization

A formulation of the layer assignment problem for VLSI circuits is presented in which the objective is to minimize the interconnect delay by taking into account the resistance and capacitance of interconnect wires and contacts. For MOS circuits with two layers of interconnections the problem is shown to be equivalent to that of minimizing a weighted resistance of the corresponding RC network. This formulation readily handles wires with preassigned layers, such as power supply lines or module terminals. With user-defined weights assigned to selected nets, this method can be used to minimize critical path delays. The problem is shown to be NP-complete. A polynomial-time approximation algorithm, based on graph partitioning technique, is presented along with some experimental results. The layer assignment algorithm presented in this paper has been implemented in LISP and tested on several design examples with complexity ranging from tens to a few hundred nets. Computational complexity of this algorithm is on the order of O(n²) for building the required data structure, and O(n^1.5) for actual layer assignment, where n is the number of wire segments in the routing