A scaled random walk solver for fast power grid analysis

Baktash Boghrati, Sachin S Sapatnekar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Pages38-43
Number of pages6
StatePublished - May 31 2011
Event14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011 - Grenoble, France
Duration: Mar 14 2011Mar 18 2011

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
ISSN (Print)1530-1591

Other

Other14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
CountryFrance
CityGrenoble
Period3/14/113/18/11

Fingerprint Dive into the research topics of 'A scaled random walk solver for fast power grid analysis'. Together they form a unique fingerprint.

Cite this