A sum-over-paths impulse-response moment-extraction algorithm for massively coupled RLCM IC-interconnect networks

As the integrated circuit (IC) industry moves from one technology node to the next, the percentage of the design cycle spent on designing and analyzing interconnects has increased considerably. Accurate and speedy CAD algorithms for interconnect analysis are in high demand. The structure and the complexity of the current IC interconnects only worsens the situation. CAD algorithms for interconnect analysis fundamentally solve Maxwell equations using either a "One-Step" or "Two-Step" approach. The One-Step approach directly solves the Maxwell equations while the Two-Step approach extracts the equivalent linear parasitic circuit components and then solves a system of circuit equations. We have chosen to proceed in this work with the Two-Step approach which conveniently separates the physics of the circuit element extraction from the mathematics of the circuit-equation solution. Speedy and accurate solution of the circuit-equation solution is our primary focus. We will assume that massively coupled RLCM circuits that best model the current interconnect structures are available. We believe that low-order impulse-response (IR) moments for the RLCM circuits are, themselves, simple design metrics for IC designers. In this work we provide an algorithm based on a "Feynman" sum-over-paths (SoP) postulate that we have discovered to provide stochastic estimates for the first-three IR moments without employing any sparsification techniques used by most present-day deterministic CAD algorithms. Our SoP algorithm begins by representing s-domain circuit nodal equations as a transition diagram. Then, using the SoP postulate we obtain simpler reduced circuits whose moments can be summed to get the moments for the massively complex full circuit. To efficiently provide IR-moment estimates for high-complexity RLCM circuit topologies, we randomly sample a set of the reduced circuits. In addition, the SoP algorithm is inherently parallel, therefore allowing further computational speed up. We tested and confirmed our algorithm with simple circuits by comparing SoP results with exact moment values obtained analytically. Moreover, we tested the algorithm on a medium-complexity interconnect structure with close to a million reactive couplings. The SoP results were then compared with an independent, deterministic, popularly accepted CAD tool. Finally, a structure with over one-billion reactive couplings was analyzed using our SoP algorithm. We believe there is no current CAD algorithm that can efficiently and accurately solve an interconnect structure of this magnitude. Our algorithm provided record results with second-order or less IR-moment values within 10% in only 252s, using an IBM T22-Thinkpad(TM) with a 896MHz Pentium III(TM) processor.