Title: A hierarchy preserving hierarchical bottom-up 2-layer wiring algorithm with respect to via minimization
Abstract: 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 hierarchical physical synthesis, which is not highly developed yet although absolutely essential for the design of ULSI circuits. The computational complexity of HCVM is NP-complete [33]. This paper presents a hierarchical bottom-up algorithm to (a variant of) this problem which is 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 O(n3) where n is the sixe of the hierarchical description of Q.
Publication Year: 1993
Publication Date: 1993-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot