Parallel partitioning based on-chip power distribution network analysis using locality acceleration

Large VLSI on-chip power distribution networks (PDN) are challenging to analyze due to the sheer network complexity. In this paper, a novel parallel partitioning based PDN analysis approach is presented. We use the boundary circuit responses of each partition to divide the full grid simulation problem into a set of independent sub grid simulation problems. Instead of solving exact boundary circuit responses, a more efficient scheme to provide near exact approximation to the boundary circuit responses by exploiting the spatial locality of the flip-chip type power grids is proposed, in which only several small sub power grids need to be solved. This scheme is also used in a block based iterative error reduction process to improve the convergence. Through the analysis of several large power grids, the proposed approach, which can be fully parallelizable, is shown to have great runtime efficiency, fast convergence, and favorable scalability. Our approach can solve a 7.2 million-node power grid in 26 seconds, which is 18 times faster than a state of the art direct solver.