Statistical analysis of on-chip power grid networks by variational extended truncated balanced realization method

ABSTRACT

In this paper, we present a novel statistical analysis approach for large power grid network analysis under process variations. The new algorithm is very efficient and scalable for huge networks with a large number of variational variables. This approach, called varETBR for variational extended truncated balanced realization, is based on model order reduction techniques to reduce the circuit matrices before the variational simulation. It performs the parameterized reduction on the original system using variation-bearing subspaces. varETBR calculates variational response Gramians by Monte-Carlo based numerical integration considering both system and input source variations for generating the projection subspace. varETBR is very scalable for the number of variables and is flexible for different variational distributions and ranges as demonstrated in experimental results. After the reduction, Monte-Carlo based statistical simulation is performed on the reduced system and the statistical responses of the original system are obtained thereafter. Experimental results, on a number of IBM benchmark circuits [15] up to 1.6 million nodes, show that the varETBR can be 4500X faster than the Monte-Carlo method and is much more scalable than one of the recently proposed approaches.

REFERENCES

• 1: Umfpack. http://www.cise.ufl.edu/research/sparse/umfpack/.
• 2: A. B. Kahng. DFM tools and methodologies for 65nm and below. In Proc. Asia South Pacific Design Automation Conf. (ASPDAC), 2006. Tutorial.
• 3: C. Chiang and J. Kawa. Design for Manufacturability. Springer, 2007.
• 4: L. Daniel, O. C. Siong, L. S. Chay, K. H. Lee, and J. White. Multi-parameter moment-matching model-reduction approach for generating geometrically parameterized interconnect performance models. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 23(5):678--693, May 2004.
• 5: Imad A. Ferzli , Farid N. Najm, Statistical estimation of leakage-induced power grid voltage drop considering within-die process variations, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776047]
• 6: Imad A. Ferzli , Farid N. Najm, Statistical Verification of Power Grids Considering Process-Induced Leakage Current Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.770, November 09-13, 2003
• 7: 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 [doi>10.1145/1146909.1146966]
• 8: Praveen Ghanta , Sarma Vrudhula , Rajendran Panda , Janet Wang, Stochastic Power Grid Analysis Considering Process Variations, Proceedings of the conference on Design, Automation and Test in Europe, p.964-969, March 07-11, 2005 [doi>10.1109/DATE.2005.282]
• 9: Y. Lee, Y. Cao, T. Chen, J. Wang, and C. Chen. HiPRIME: Hierarchical and passivity preserved interconnect macromodeling engine for rlkc power delivery. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 24(6):797--806, 2005.
• 10: Duo Li , Sheldon X.-D. Tan , Bruce McGaughy, ETBR: extended truncated balanced realization method for on-chip power grid network analysis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403479]
• 11: Ying Liu , Lawrence T. Pileggi , Andrzej J. Strojwas, Model order-reduction of RC(L) interconnect including variational analysis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.201-206, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309914]
• 12: Ning Mi , Sheldon X.-D. Tan , Pu Liu , Jian Cui , Yici Cai , Xianlong Hong, Stochastic extended Krylov subspace method for variational analysis of on-chip power grid networks, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 13: B. Moore. Principle component analysis in linear systems: Controllability, and observability, and model reduction. IEEE Trans. Automat. Contr., 26(1):17--32, 1981.
• 14: S. Nassif. Delay variability: sources, impact and trends. In Proc. IEEE Int. Solid-State Circuits Conf., pages 368--369, San Francisco, CA, Feb 2000.
• 15: Sani R. Nassif, Power grid analysis benchmarks, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 16: A. Odabasioglu, M. Celik, and L. Pileggi. PRIMA: Passive reduced-order interconnect macromodeling algorithm. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pages 645--654, 1998.
• 17: Sanjay Pant , David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Rajendran Panda, A stochastic approach To power grid analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996616]
• 18: J. R. Phillips, Variational interconnect analysis via PMTBR, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.872-879, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382697]
• 19: Joel Phillips , L. Miguel Silveira, Poor Man's TBR: A Simple Model Reduction Scheme, Proceedings of the conference on Design, automation and test in Europe, p.20938, February 16-20, 2004
• 20: J. R. Phillips and L. M. Silveira. Poor man's TBR: a simple model reduction scheme. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 24(1):43--55, 2005.
• 21: L. T. Pillage, R. A. Rohrer, and C. Visweswariah. Electronic Circuit and System Simulation Methods. McGraw-Hill, New York, 1994.
• 22: R. Rutenbar. Next-generation design and EDA challenges. In Proc. Asia South Pacific Design Automation Conf. (ASPDAC), January 2007. Keynote speech.
• 23: Ashish Srivastava , Robert Bai , David Blaauw , Dennis Sylvester, Modeling and analysis of leakage power considering within-die process variations, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566426]
• 24: 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]
• 25: Zhenhai Zhu , Joel Phillips, Random sampling of moment graph: a stochastic Krylov-reduction algorithm, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France