Haifeng Qian
Sachin S. Sapatnekar
ABSTRACT
This paper presents a power grid analyzer based on a random walk technique. A linear-time algorithm is first demonstrated for DC analysis, and is then extended to perform transient analysis. The method has the desirable property of localizing computation, so that it shows massive benefits over conventional methods when only a small part of the grid is to be analyzed (for example, when the effects of small changes to the grid are to be examined). Even for the full analysis of the grid, experimental results show that the method is faster than existing approaches and has an acceptable error margin. This method has been applied to test circuits of up to 2.3M nodes. For example, for a circuit with 70K nodes, the solution time for a single node was 0.42 sec and the complete solution was obtained in 17.6 sec.
- P. G. Doyle and J. L. Snell, "Random walks and electric networks", 1984. http://front.math.ucdavis.edu/math.PR/0001057Google Scholar
- L. Hagen and A. B. Kahng, "A new approach to effective circuit clustering," Digest of Technical Papers, IEEE/ACM International Conference on Computer-Aided Design, pp. 422--427, 1992. Google ScholarDigital Library
- C. Ho, A. E. Ruehli, and P. Brennan, "The modified nodal approach to network analysis," IEEE Transactions on Circuits and Systems, vol. CAS-22, no. 6, pp.504--509, 1975.Google Scholar
- J. Kozhaya, S. R. Nassif, and F. N. Najm, "A multigrid-like technique for power grid analysis," IEEE Transactions on Computer-Aided Design, vol. 21, no. 10, pp.1148--1160, 2002. Google ScholarDigital Library
- A. Kuehlmann, K. L. McMillan, and R. K. Brayton, "Probabilistic state space search," Digest of Technical Papers, IEEE/ACM International Conference on Computer-Aided Design, pp. 574--579, 1999. Google ScholarDigital Library
- Y. L. Le Coz and R. B. Iverson, "A stochastic algorithm for high speed capacitance extraction in integrated circuits," Solid-State Electronics, vol.35, no. 7, pp. 1005--1012, 1992.Google ScholarCross Ref
- SPEC CPU2000 Results, available at http://www.specbench.org/cpu2000/results/cpu2000.htmlGoogle Scholar
- R. D. Yates and D. J. Goodman, Probability and Stochastic Processes: A Friendly Introduction for Electrical and Computer Engineers, John Wiley and Sons, New York, 1999.Google Scholar
- J. Zagajac, "A fast method for estimating discrete field values in early engineering design," IEEE Transactions on Visualization and Computer Graphics, vol. 2, no. 1, pp. 35--43, 1996. Google ScholarDigital Library
- M. Zhao, R. V. Panda, S. S. Sapatnekar, and D. Blaauw, "Hierarchical analysis of power distribution networks," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 2, pp. 159--168, Feb. 2002. Google ScholarDigital Library
Index Terms
- Random walks in a supply network
Recommendations
Diffusivity of a random walk on random walks
We consider a random walk Zn1,',ZnK+1∈ï K+1 with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor ï K2=2K+2 with respect to the ...
How slow, or fast, are standard random walks?: analysis of hitting and cover times on trees
CATS '11: Proceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 119Random walk is a powerful tool, not only for modeling, but also for practical use such as the Internet crawlers. Standard random walks on graphs have been well studied; It is well-known that both hitting time and cover time of a standard random walk are ...
How slow, or fast, are standard random walks?: analysis of hitting and cover times on trees
CATS 2011: Proceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 119Random walk is a powerful tool, not only for modeling, but also for practical use such as the Internet crawlers. Standard random walks on graphs have been well studied; It is well-known that both hitting time and cover time of a standard random walk are ...
Comments