Gibbs sampling in power grid analysis

Power grid plays an important role in determining circuit performance, and the accuracy and efficiency of power grid analysis algorithm has become critical in timing, power and noise estimation of modern integrated circuits. In this paper a stochastic algorithm based on Gibbs sampling is proposed to solve the problem of power grid analysis, and the test results shows that it reaches a good accuracy with linear complexity. The method has incremental property of localizing computation, a desirable property favoring in modern CAD. Therefore it can be embedded at all the design and verification levels of integrated circuits.