SPICE-accurate iterative methods for efficient time-domain simulation of VLSI circuits with strong parasitic couplings

Parasitic coupling effects are becoming more and more important for deep-submicron VLSI circuit design. The behavior of deep submicron VLSI circuits needs to be verified together with a massive amount of parasitic elements arising from the common substrate, power/ground networks, interconnect lines, etc. Recently, there has also been interest in coupled circuit-electromagnetic simulation and thermal-aware VLSI circuit analysis. For such types of circuits, the number of linear elements is much larger than the number of nonlinear devices. Further, the circuit matrix structure becomes denser with parasitic couplings. Consequently, LU factorization is becoming the dominant per-iteration cost factor during time-domain simulation. New robust, accurate and efficient approaches are required.; In this dissertation, we recognize the robustness and accuracy of LU factorization based direct methods as in SPICE. To speed up time-domain simulation of VLSI circuits with parasitic couplings and preserve SPICE-like robustness and accuracy, the first strategy is to reduce the number of LU factorization during transient simulation. Two SPICE-accurate iterative methods have been presented---quasi-Newton based iterative methods and preconditioned Krylov-subspace based iterative methods. The main contributions are: (1) Fixed leading coefficient numerical integration formulae that have been derived, analyzed and implemented for quasi-Newton based iterative methods. (2) Piecewise weakly nonlinear definition of nonlinear devices. (3) Efficient preconditioning schemes that are developed for Krylov-subspace based iterative methods. (4) The relationship between these two iterative methods is characterized. The second strategy is to exploit different advantages of direct methods and iterative methods---robust direct methods for nonlinear circuits and efficient iterative methods for linear circuits.; Experimental results on nonlinear circuits with substrate and power/ground networks have demonstrated that the proposed methods preserve SPICE-like robustness and accuracy. Orders of magnitude speedup over SPICE3 in terms of both the cost of LU factorization and the overall CPU time has been observed for circuits with tens of thousands of devices. The efficiency is expected to increase further with the size of a circuit. Therefore, the proposed methods are suitable for robust, accurate and efficient time-domain simulation of VLSI circuits with parasitic couplings, where the number of linear elements dominates the number of nonlinear devices.