Hierarchical extraction of 3D interconnect capacitances in large regular VLSI structures

For submicron integrated circuits, 3D numerical techniques are required to accurately compute the values of the interconnect capacitances. In this paper, we describe an hierarchical capacitance extraction method that efficiently extracts 3D interconnect capacitances of large regular layout structures such as RAMs and array multipliers. The method is based on a 3D capacitance extraction method that uses a boundary-element technique and approximate matrix inversion to efficiently compute 3D interconnect capacitances for flat layout descriptions. The latter method has a computational complexity O(Z), where Z is the size of the layout. In the worst case, the hierarchical extraction method has computational complexity O(B+U), where B is the total size of the boundary area between all circuit parts in which the circuit is decomposed, and U is the total size of the parts of the circuit that are unique. The method has been implemented in the layout-to-circuit extractor SPACE that uses as input a hierarchical layout description of the circuit. It produces as output a netlist containing transistors, resistances, ground capacitances, and coupling capacitances between conductor parts that are near to each other.