Modern deep sub-micron ultra-large scale integration designs with hundreds of millions of devices require huge grids for power distribution. Such grids, operating with decreasing power supply voltages, are a design limiting factor and accurate analysis of their behavior is of paramount importance as any voltage drops can seriously impact performance or functionality. As power grid models have millions of unknowns, highly optimized special-purpose simulation tools are required to handle the time and memory complexity of solving for their dynamic behavior. In this paper, we propose a hierarchical matrix representation of the power grid model that is both space and time efficient. With this representation, reduced storage matrix factors are efficiently computed and applied in the analysis at every time-step of the simulation. Results show an almost linear complexity growth, namelyO(n loga(n)), for some small constant a, in both space and time, when using this matrix representation. Comparisons of our academic implementation with production-quality code prove this method to be very efficient when dealing with the simulation of large power grid models.

Modern deep sub-micron ULSI designs with hundreds of millions of devices require huge grids for power distribution. Such grids, operating with increasingly low-power voltages, are a design limiting factor and accurate analysis of their behavior is of paramount importance as any voltage drops can seriously impact performance or functionality. As power grid models have millions of unknowns, highly optimized special purpose simulation tools are required to handle the time and memory complexity of solving for their dynamic behavior. In this work, we propose a hierarchical matrix representation of the power grid model that is both space and time efficient. With this representation, reduced storage matrix factors are efficiently computed and applied in the analysis at every time-step of the simulation. Results show an almost linear complexity growth, namely O(n loga(n)), for some small constant a, in both space and time, when using this matrix representation. Comparisons of our academic implementation with production-quality code proves this method to be very efficient when dealing with the simulation of large power grid models.

Reduced order modeling is a well-known methodology for linear system modeling. In the past decade it has risen to prominence in the VLSI electronic design area as the de facto standard set of techniques for interconnect and package modeling. With shrinking technologies and faster operating frequencies, such previously ignored structures can have a first order influence in the behavior of many electronic systems. Reduced order modeling techniques can provide accurate, robust, accuracy-controlled models of linear networks. Unfortunately, most of these techniques have difficulty reducing networks with a large number of ports, such as power grids, substrate models and coupled data buses. In this paper we provide a characterization of this problem and discuss the complexity of several previously proposed techniques for handling this problem. We show that for most of these techniques there is little hope to expect that considerable reduction can be achieved. We also show that a simple, perhaps not obvious, approach can theoretically provide better reduction than most of the other techniques.