Partial Random Walk-based Approach for Fast Analyzing Power/Ground(P/G) Grids

In this paper,we propose a partial random walk-based approach for fast solving P/G grids that consists of random walk and SOR methods.The approach divides a large P/G grid into some medium blocks,then uses the improved random walk method to calculate voltages for border nodes of blocks, finally SOR method is applied to efficiently solve internal nodes for blocks.At the same time,we propose a novel block-ordering strategy that solves blocks from convex to diagonal.Meanwhile our method is easily extended from R-only DC P/G grids to RLC transient P/G grids.Experimental data demonstrate that simple random walk method is inefficient for the case where the number of power PADs is small and our method can efficiently overcome this shortcoming of the simple random walk method.As a result,our method is 20times faster than the simple random walk method for solving P/G networks of scarcer power PADs.