Mentor Graphics Corporation

Analysis of VLSI designs and circuits often requires the construction of a small-signal equivalent impedance representation between prescribed node pairs. Examples include IR-drop calculation, electrical overstress verification, ESD protection, di/dt current rush analysis, electro-migration checks, thermal analysis and model order reduction. VLSI designs consisting of hundreds of millions (10e11) of linear circuit elements are now commonplace and thus any method which requires compute intensive calculations is difficult to apply for all the elements of the circuit. By definition, given a circuit with $n$ elements, conventional analysis techniques have a $\Omega(n^2)$ lower-bound to exhaustively enumerate all node-pairs which meet a constraint criteria. We present the first $O( n \lg n + k )$ algorithm for answering queries of the form: \[ \exists (x,y) : ((x,y) \in n\times n) \wedge (Z_{eff}(x,y) < \mathbb{Z}) \]where $Z_{eff}(x,y)$ is the equivalent impedance between nodes $x$ and $y$, and $k$ node-pairs meet the constraint. Calculating all node pairs for which these constraints are met is compute intensive using existing techniques, even using heuristic methods. In this paper a new technique based on method of projection using ellipsoidal norms is presented. Our proposed method employs recently discovered techniques from theoretical computer science to compute an $\epsilon$-approximate embedding matrix from which effective impedance of all node pairs can be estimated as easily as taking the Euclidean norm of column differences. Using computational geometry methods, existence queries can then be answered in logarithmic time.The method works for general circuits containing resistances, capacitances, and inductances.