Random walks in a supply network

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.

REFERENCES

• 1: P. G. Doyle and J. L. Snell, "Random walks and electric networks", 1984. http://front.math.ucdavis.edu/math.PR/0001057
• 2: Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
• 3: 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.
• 4: 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.
• 5: Andreas Kuehlmann , Kenneth L. McMillan , Robert K. Brayton, Probabilistic state space search, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.574-579, November 07-11, 1999, San Jose, California, United States
• 6: 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.
• 7: SPEC CPU2000 Results, available at http://www.specbench.org/cpu2000/results/cpu2000.html
• 8: 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.
• 9: Jovan Zagajac, A Fast Method for Estimating Discrete Field Values in Early Engineering Design, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.35-43, March 1996 [doi>10.1109/2945.489385]
• 10: 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.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

General Terms:
Algorithms, Reliability, Verification

Keywords:
power grid, random walk