Power Grid Analysis And Optimization In VLSI Circuit Design

As the VLSI technology enters ultra-deep sub-micron regime, the on-chip power integrity has become a limiting factor for the chip's overall performance. A poorly designed power grid may easily lead to extra logic delays, signal integrity problems and even functional failures. To ensure the robustness of the power grid, multiple power grid simulations and optimizations need to be performed. However, due to the tremendous size of the power grid, using general-purpose simulator is no longer feasible in terms of both execution time and memory.The paper presents a class of power grid analysis and optimization techniques, all of which are based on the algebraic multigrid (AMG) method. The general idea behind our approaches is: we first use an AMG-based reduction strategy to reduce the circuit size. And then we simulate or optimize on the coarsest grid. After that we map the simulation or optimization result back to the original circuit. The contributions of our work include:(1) We propose an improved AMG-based reduction strategy to reduce the large size of the power grid. A dynamic threshold scheme is also used in the strategy to help speed up the grid reduction while useful information is retained.(2) Based upon the reduction strategy above, a fast transient analysis method is developed. By combining with the conjugate gradient method, the AMG-based method is extended to the AMG preconditioned conjugate gradient method, which works as an accurate solver. After that, the scope of this method is further broadened for handling the analysis of the modified grid with the interpolation operator refinement scheme.(3) Finally, a fast decap allocation method based on AMG is suggested. This method can be applied to either regular or irregular power grids and is more flexible for optimization on large-scale circuits.The experiments are carried out on PC with Pentium IV 2.6G CPU, 1G memory and Windows operating system. Experimental results show that these techniques not only achieve significant speed-up over reported industrial methods, but also enhance the quality of solutions. By using the proposed techniques, transient analysis with 200 time steps on a 1.6M-node power grid can be completed in less than 5 minutes; DC analysis on the same circuit can reach an accuracy of 1e-6 in about 141 seconds. Our decap allocation can process a circuit with up to 1 million nodes in 674 seconds.