Power grid simulation via efficient sampling-based sensitivity analysis and hierarchical symbolic relaxation

On-chip supply networks are playing an increasingly important role for modern nanometer-scale designs. However, the ever growing sizes of power grids make the analysis problem extremely difficult thereby introducing severe challenges in design and optimization. The inherent analysis complexity calls for innovations in simulation techniques that must provide appropriate accuracy, efficiency as well as the tradeoff thereof to aid design verification and optimization. In this paper, we first present a sampling-based sensitivity analysis by employing the notation of importance sampling in a Monte Carlo based circuit simulation framework. This technique allows the extraction of multi-parameter sensitivities for the node voltages of interest in the same Monte Carlo runs that are used for computing the nominal voltage values. For more efficient nonstructured whole-grid solution approaches, we further introduce a new direct solution method by embedding symbolic relaxation steps in a hierarchical fashion. As a direct method, the proposed hierarchical symbolic relaxation is suitable to both dc and transient analyses. Circuit examples are included to demonstrate the efficacy of the proposed techniques