A HIERARCHY PRESERVING HIERARCHICAL BOTTOM-UP 2-LAYER WIRING ALGORITHM WITH RESPECT TO VIA MINIMIZATION

Here, the following hierarchical constrained via minimization problem (HCVM) is examined: ''Let Q be a circuit with a given layout hierarchy . Find a 2-layer wiring of Q which needs a number of vias minimal with respect to the preservation of hierarchy, i.e., on condition that the description of the result is (nearly) as short as the description of Q before the 2-layer wiring''. The problem arises in connection with h ierarchical physical synthesis, which is not highly developed yet alth ough absolutely essential for the design of ULSI circuits. The computa tional complexity of HCVM is NP-complete [33]. This paper presents a h ierarchical bottom-up algorithm to (a variant of) this problem which i s locally optimal, i.e., given the 2-layer wirings of the subcircuits of level i, it computes the optimal (partially induced by the wirings of the subcircuits) 2-layer wiring of the circuits of level i + 1. The algorithm running time is less than 0(n3) where n is the size of the hierarchical description of Q.