Can I read Acceleration of Random-walk-based Linear Circuit Analysis Using Importance Sampling on EtoBox?

Acceleration of Random-walk-based Linear Circuit Analysis Using Importance Sampling by Tetsuro Miyakawa; Koh Yamanaga; Hiroshi Tsutsui; Hiroyuki Ochi; Takashi Sato is a scholarly article available to read on EtoBox.

What is Acceleration of Random-walk-based Linear Circuit Analysis Using Importance Sampling about?

This paper proposes an importance sampling (IS) technique based on quasi-zero-variance estimation for accelerating convergence of random-walk-based power grid analysis. In our approach, the alternative probability for IS is incrementally updated after every Mr samples of random walk so that more recent and thus more accurate node voltages are utilized to asymptotically achieve ideal zero-variance estimation. We also propose a method to determine efficient Mr for the r-th probability update; although smaller Mr results more aggressive update of alternative probability, the alternative probability becomes inaccurate if Mr is too small. The estimation error of the proposed method decreases O((M/r) -r/2 ), which breaks O(M -1/2 ), the slow convergence-rate barrier of normal Monte Carlo analysis. Our trial implementation achieved 790x speedup compared with a conventional random-walk-based circuit analysis for analyzing IBM power grid benchmark circuits at 1 mV accuracy.

Author

Tetsuro Miyakawa; Koh Yamanaga; Hiroshi Tsutsui; Hiroyuki Ochi; Takashi Sato

Publisher

ACM

Published

2011

Language

EN