Incremental and on-demand random walk for iterative power distribution network analysis

ABSTRACT

Power distribution networks (PDNs) are designed and analyzed iteratively. Random walk is among the most efficient methods for PDN analysis. We develop in this paper an incremental and on-demand random walk to reduce iterative analysis time. During each iteration, we map the design changes as positive or negative random walks for observed nodes. To update PDN analysis result, we only need to apply these extra positive or negative walks, instead of doing all walks from scratch. We show that different execution orders for these walks do not affect accuracy but do affect the runtime because of the cancellation between positive and negative walks. Considering this cancellation effect, we optimize the walk order by solving a min-energy electromagnetic particles placement problem and, as a result, further reduce the runtime to about 8x compared to the worst order. Experiments show that, compared to random walk from scratch, our algorithm has similar accuracy but reduces the iterative analysis time by up to 18x for on-chip PDN sizing, and by up to 13x for package ball assignment with substrate routing. In addition, our incremental random walk has a linear time complexity with respect to the number of observed nodes and is more suitable for on-demand analysis, compared to random walk from scratch and its big warm-up cost.

REFERENCES

• 1: G. Shi, B. Hu, and C. J. R. Shi, "On symbolic model order reduction," IEEE Trans. on CAD, 2006.
• 2: H. Qian, S. R. Nassif, and S. S. Sapatnekar, "Power Grid Analysis Using Random Walks," IEEE Trans. on CAD, 2005.
• 3: Yuhong Fu , Rajendran Panda , Ben Reschke , Savithri Sundareswaran , Min Zhao, A novel technique for incremental analysis of on-chip power distribution networks, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 4: L. T. Pillage, R. A. Roher, and C. Visweswariah, Electronic circuit and system simulation methods. McGRAW-HILL Publishers, 1994.
• 5: Rubil Ahmadi , Farid N. Najm, Timing Analysis in Presence of Power Supply and Ground Voltage Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.176, November 09-13, 2003 [doi>10.1109/ICCAD.2003.142]
• 6: Yiyu Shi , Jinjun Xiong , Chunchen Liu , Lei He, Efficient decoupling capacitance budgeting considering operation and process variations, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 7: E. Chiprout and T. V. Nguyen, "Power analysis of large interconnect grids with multiple sources using model reduction," in European Conference on Circuit Theory and Design, 1999.
• 8: Janet M. Wang , Tuyen V. Nguyen, Extended Krylov subspace method for reduced order analysis of linear circuits with multiple sources, Proceedings of the 37th conference on Design automation, p.247-252, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337407]
• 9: Tsung-Hao Chen , Charlie Chung-Ping Chen, Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods, Proceedings of the 38th conference on Design automation, p.559-562, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379023]
• 10: Yiyu Shi , Hao Yu , Lei He, SAMSON: a generalized second-order arnoldi method for reducing multiple source linear network with susceptance, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123014]
• 11: Joseph N. Kozhaya , Sani R. Nassif , Farid N. Najm, Multigrid-like technique for power grid analysis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: E. Chiprout, Fast flip-chip power grid analysis via locality and grid shells, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.485-488, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382626]
• 13: J. Singh and S. S. Sapatnekar, "Partition-based algorithm for power grid design using locality," IEEE Trans. on CAD, 2006.
• 14: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 15: in http://ngspice.sourceforge.net.