|
Warning: The download time has expired please click on the item to try again.
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
P. G. Doyle and J. L. Snell, "Random walks and electric networks", 1984. http://front.math.ucdavis.edu/math.PR/0001057
|
| |
2
|
|
| |
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
|
|
| |
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.
|
CITED BY 35
|
|
Jin Shi , Yici Cai , Sheldon X.-D. Tan , Xianlong Hong, High accurate pattern based precondition method for extremely large power/ground grid analysis, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
Hang Li , Zhenyu Qi , Sheldon X.-D. Tan , Lifeng Wu , Yici Cai , Xianlong Hong, Partitioning-based approach to fast on-chip decap budgeting and minimization, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Praveen Ghanta , Sarma Vrudhula , Sarvesh Bhardwaj , Rajendran Panda, Stochastic variational analysis of large power grids considering intra-die correlations, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
|
|
|
|
|
|
Jeffrey Fan , Sheldon X. -D. Tan , Yici Cai , Xianlong Hong, Partitioning-based decoupling capacitor budgeting via sequence of linear programming, Integration, the VLSI Journal, v.40 n.4, p.516-524, July, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yici Cai , Jin Shi , Zhu Pan , Xianlong Hong , Sheldon X. -D. Tan, Large scale P/G grid transient simulation using hierarchical relaxed approach, Integration, the VLSI Journal, v.41 n.1, p.153-160, January, 2008
|
|
|
Srinivasan Murali , Almir Mutapcic , David Atienza , Rajesh Gupta , Stephen Boyd , Giovanni De Micheli, Temperature-aware processor frequency assignment for MPSoCs using convex optimization, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jin Shi , Yici Cai , Wenting Hou , Liwei Ma , Sheldon X.-D. Tan , Pei-Hsin Ho , Xiaoyi Wang, GPU friendly fast Poisson solver for structured power grid network analysis, Proceedings of the 46th Annual Design Automation Conference, July 26-31, 2009, San Francisco, California
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
B.7