TY - GEN
T1 - A scaled random walk solver for fast power grid analysis
AU - Boghrati, Baktash
AU - Sapatnekar, Sachin S
PY - 2011/5/31
Y1 - 2011/5/31
N2 - The analysis of on-chip power grids requires the solution of large systems of linear algebraic equations with specific properties. Lately, a class of random walk based solvers have been developed that are capable of handling these systems: these are especially useful when only a small part of the original system must be solved. These methods build a probabilistic network that corresponds to the power grid. However, this construction does not fully exploit the properties of the problem and can result in large variances for the random walks, and consequently, large run times. This paper presents an efficient methodology, inspired by the idea of importance sampling, to improve the runtime of random walk based solvers. Experimental results show significant speedups, as compared to naive random walks used by the state-of-the-art random walk solvers.
AB - The analysis of on-chip power grids requires the solution of large systems of linear algebraic equations with specific properties. Lately, a class of random walk based solvers have been developed that are capable of handling these systems: these are especially useful when only a small part of the original system must be solved. These methods build a probabilistic network that corresponds to the power grid. However, this construction does not fully exploit the properties of the problem and can result in large variances for the random walks, and consequently, large run times. This paper presents an efficient methodology, inspired by the idea of importance sampling, to improve the runtime of random walk based solvers. Experimental results show significant speedups, as compared to naive random walks used by the state-of-the-art random walk solvers.
UR - http://www.scopus.com/inward/record.url?scp=79957559247&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79957559247&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:79957559247
SN - 9783981080179
T3 - Proceedings -Design, Automation and Test in Europe, DATE
SP - 38
EP - 43
BT - Proceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
T2 - 14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Y2 - 14 March 2011 through 18 March 2011
ER -