capacitance between metal wires of supply lines, device capacitance of the non-switching devices, and capacitance between N-well and substrate, occur as implicit decoupling capacitance in a power distribution network. Unfortunately, this implicit decoupling capacitance is sometimes not enough to constrain the voltage drop within safe bounds and designers often have to add intentional explicit decoupling capacitance structures on the die at strategic locations. These explicitly added decoupling capacitances are not free and increase the area and leakage power consumption of the chip. Parasitic interconnect resistance, decoupling capacitance and package/interconnect inductance form a complex RLC circuit which has its own resonance frequency. If the resonance frequency lies close to the operating frequency of the design, large voltage drops can develop in the grid. The crux of the problem in designing a power grid is that there are many unknowns until the very end of the design cycle. Nevertheless, decisions about the structure, size and layout of the power grid have to be made at very early stages when a large part of the chip design has not even begun. Unfortunately, most commercial tools focus on post-layout verification of the power grid when the entire chip design is complete and detailed information about the parasitics of the power and ground lines and the currents drawn by the transistors are known. Power grid problems revealed at this stage are usually very difficult or expensive to fix, so the preferred methodologies help to design an initial power grid and refine it progressively at various design stages. Due to the growth in power consumption and switching speeds of modern high performance microprocessors, the di/dt effects are becoming a growing concern in high speed designs. Clock gating, which is a preferred scheme for power management of high performance designs, can cause rapid surges in current demands of macro-blocks and increase di/dt effects. Designers rely on the on-chip parasitic capacitances and intentionally added decoupling capacitors to counteract the di/dt variations in the voltage. But it is necessary to model accurately the inductance and capacitance of the package and chip and analyze the grid with such models, as otherwise the amount of decoupling to be added might be underestimated or overestimated. Also it is necessary to maintain the efficiency of the analysis even when including these detailed models. Analysis A critical issue in the analysis of power grids is the large size of the network (typically millions of