In-depth Experimental Study of Power Grid Network Analysis Using Random Walks Algorithm

In this paper, in-depth experimental study was conducted on random walk approach for DC analysis of P/G network, and we also extended the random walk approach for RLC networks by Norton companion without any adjustment for the algorithm. Our experimental results suggest that the CPU times of solving several nodes by the algorithm is about one order of magnitude speedup over PCG, and the speedup may be higher if the circuits contain more VDD nodes. We also show how accuracy-runtime tradeoff of random walk algorithm could be made through adjusting the parameters of the algorithm. Our extended method works pretty well on both DC analysis and transient analysis comparing with direct method