Simulation and Optimization of On-Chip Power Delivery Networks and Clock Networks

Principle Investigators: 

Dr. Sheldon Tan  (PI),  UCR

Graduate Students:

Duo Li, Xue-Xin Liu,  Zao Liu 

Collaborators:

Prof. Xianglong Hong,  Department of Computer Science and Technology, Tsinghua University

Prof. Yici Cai,    Department of Computer Science and Technology, Tsinghua University

Prof. Bao Liu,   Department of ECE, University of Taxes, San Antonio, TX

Funding:

We appreciate the following funding agencies for their generous supports of this project. 

• National Science Foundation, “CAREER: Career Development Plan: Behavioral Modeling, Simulation and Optimization for Mixed-Signal System in a Chip”, (CCF-0448534, CCF-0529754 and CCF-0731962, CCF- 0830304, for REU supplements),  6/1/2005-5/31/2011. PI: Sheldon Tan.
• Cadence Design Systems, Research Grant , “Fast On-Chip Transistor Level Power/Ground Dynamic Grid Analysis”, 10/1/2003-9/20/2004,  PI: Sheldon Tan
• UC MICRO Program (via Cadence Corporation) (#04-088), “Fast Decap Budgeting for Robust On-Chip Power Delivery Networks”, 9/1/2004 to8/30/2005, PI: Sheldon Tan
• National Science Foundation, “U.S.-China Planning Visit: Development of Computer-Aided Design (CAD) Tools for Physical Design and Verification of Low Power Nanometer VLSI Design”, OISE-0451688, 5/1/2005-4/30/2007, PI: Sheldon Tan
• National Science Foundation, “IRES: Development of Global Scientists by Research Collaborations on Simulation and Optimization of Nanometer Integrated Systems”, OISE-0623038, 9/1/06/8/31/09. PI: Sheldon Tan

Project Descriptions

The power distribution network distributes power and ground voltages from pad locations to all devices in a chip. Shrinking device dimensions, faster switching frequencies and increasing power consumption in deep sub-micrometer technologies cause large switching currents to flow in the on-chip power and ground networks which degrade performance and reliability. A robust power distribution network is essential to ensure reliable operation of circuits on a chip. Power supply integrity verification is a critical concern in high-performance VLSI designs. The fundamental problem is that the on-chip power distribution networks can’t no longer behaviors like ideal conductive networks due to many increasing physicals effects like resistive and inductive voltage drops/fluctuations, metal breakdown (due to electromigration) etc. Those effects can cause malfunctions or even early failures of chips. As a result, accurate verification of power deliver integrity or power integrity and optimization of power grid networks to reduce the voltage degradation (due to voltage drops and ground bounces) are vital for the reliability and timing of the nanometer VLSI chips.

The PI’s group (along with our collaborators) has been working on the analysis, verification and optimization of on-chip power distribution networks or power grid (p/g) in the past several years and we have made a number of contributions in this field. The highlights include the Best-Paper-Award wining power grid sizing techniques based on sequence of linear programming techniques [J1,J2,C1C2], the sensitivity-based de-capacitance allocation strategies to reduce on-chip voltage drop [J4, C4],  statistical power grid analysis based on stochastic spectral method [J14J15C21C22].

Recently, we proposed efficient reduction based power grid analysis techniques called “Extended Truncated Balanced Realization, or ETBR techniques[J16, C26]. ETBR overcomes the Krylov subspace based EKS/IEKS based method where explicit, yet error-prone moment representation of input power signals will be required.  Instead, it uses spectrum representation in frequency domain for input signals by fast Fourier transformation. The proposed method is very amenable for threading-based parallel computing, as the response Gramian is computed in a Monte-Carlo-like sampling style and each sampling can be computed in parallel. This contrasts with all the Krylov subspace based methods like the EKS method, where moments have to be computed in a sequential order. ETBR is also more flexible for different types of input sources and can better capture the high frequency contents than EKS, and this leads to more accurate results especially for fast changing input signals. Experimental results on a number of large networks (up to one million nodes) show that, given the same order of the reduced model, ETBR is indeed more accurate than the EKS method especially for input sources rich in high-frequency components. If parallel computing is explored, ETBR can be an order of magnitude faster than the EKS/IEKS method.  ETBR can perform easy accuracy-performance trade-off to make it suitable for both early and fast power grid verification to later stage accurate and detailed analysis for power integrity sign-off.

ETBR can also be extended to perform variation and statistical power grid analysis [C30]. A more efficient error-controlled power grid analysis based on ETBR was also proposed in [C35]. ETBR program, which can perform parallel analysis on multi-core machines (based POSIX pthreads),  can be downloaded for free evaluation (see below software download).

Invited Presentations

• Cadence Design Systems, Inc. San Jose, CA,  “Efficient Area Optimization of VLSI Power/Ground (P/G) networks”, July 16, 2002
• Fudan Univ. Shanghai, China, “Area Optimization of VLSI Power/Ground Networks”, Jan. 21, 2003.
• The 5^th International Conference on ASIC, Beijing, China,  “Circuit level alternating-direction-implicit approach to transient analysis of power distribution networks”, Oct, 21, 2003.
• Tsinghua University, Beijing, China, “Fast power/ground network analysis and optimization”, Oct. 2003.
• Cadence Design Systems Inc., San Jose, CA, “Robust VLSI  Power Delivery, a Verification perspective”,  May 05, 2004.
• Cadence Design Systems Inc., San Jose, CA, “Efficient Decap Budgeting Algorithm for Large On-Chip Power Delivery Networks”, Oct. 10, 2004.
• International on System-on-a-chip Workshop (ICSOC’05), Chengdu, China, “Efficient Decap Budgeting and Optimization”, Aug. 16, 2005.
• Tsinghua University, Beijing, China, “Statistical On-Chip Power Delivery Network Analysis ”, Aug. 22, 2006.
• Cadence Design Systems Inc, San Jose, CA, “Robust VLSI on-chip power delivery: challenges and solutions”, January 14, 2008.
• Cadence Design Systems Inc, San Jose, CA, “Parallel analysis of power grid networks on Chip-Multiprocessors”, March 21, 2008.
• Cadence Design Systems Inc, San Jose, CA, “Partitioning-based reduction method for large linear network analysis”, June 18, 2008.
• IBM Watson Research Center, Yorktown Height, NY, “Variational Analysis for Large Power Delivery Networks and Full-Chip Leakage Powers of Nanometer VLSI Systems”, Nov. 5, 2008.
• College of Engineering Seminar (CUDA Talk), UC Riverside, CA “Parallel computing method for on-chip power grid analysis based on the multi-core computing platforms”, June 2, 2009.

Software Download

The ETBR, Extended Truncated Balanced Realization (EBTR) power grid solver,  perform parallel analysis on multi-core machines (based POSIX pthreads), for transient analysis of  large on-chip power grid network works can be downloaded here.

Relevant Publications

Books and book chapters

B1. Zhanhai Qin, Sheldon X.-D. Tan and Chung-Kuan Cheng, Symbolic Analysis and Reduction of VLSI Circuits, Springer Publisher, 2005, ISBN: 0-387-23904-9; e-ISBN: 0-387-23905-7.

Journal publications

J1. S. X.-D. Tan and C.-J. Shi.  “Efficient vary large scale integration power/ground network sizing based on equivalent circuit modeling.”  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 3, pp.277-284,  2003. 

J2. X.-D. Tan, C.-J. Shi and F. J.-C. Lee. “Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programmings.”,  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.  vol. 22, no. 12, pp. 1678-1684, Dec. 2003.

J3. W. Guo, S. X-.D. Tan, Z. Luo, X. Hong, “Partial random walks for transient analysis of large power distribution networks”, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science, vol. E87-A, No. 12 pp. 3265-3272, December 2004.

J4. J. Fu, Z. Luo, X. Hong, Y. Cai, S. X.-D. Tan and Z. Pan, “A fast decoupling capacitor budgeting algorithm for robust on-chip power delivery”, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science,  vol. E87-A, No. 12 pp.3273-3280, December 2004.

J5. H. Li, J. Fan, Z. Qi, S. X-D. Tan, L. Wu, Y. Cai, X. Hong, “Partitioning-based approach to fast on-chip decoupling capacitance budgeting and minimization”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 11, pp.2402-2412, Nov. 2006.

J6. Y. Cai, J. Fu, X. Hong, S. X-D. Tan, Y. Luo, “Power/ground network optimization considering decap leakage currents”, IEEE Transaction on Circuit and System  II,  vol. 53, no. 10, pp.1012-1016, Oct. 2006.

J7. J. Fan, S. X-.D. Tan, Y. Cai and X. Hong, “Partitioning-based decap capacitor budgeting via sequence of linear programming”, Integration, The VLSI Journal, vol. 40, no.4, pp. 516-524, 2007.

J8. Y. Cai, Z. Pan, S. X.-D. Tan, X. Hong, J. Fu, “Fast analysis of power/ground networks via circuit reduction”, Chinese Journal of Semiconductors, vol. 26, no. 7, pp.1340-1345, 2005.

J9. J. Shi, Y. Cai, J. Fan, S. X.-D. Tan and X. Hong, “Pattern based iterative method for extreme large power/ground analysis”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 4, pp.680-692, April 2007.

J10. B. Liu, S. X.-D. Tan, “Minimum decoupling capacitor insertion in VLSI power/ground supply networks by semidefinite and linear programs”, IEEE Transactions on Very Large Scale Integrated Systems  (TVLSI), vol. 15, no. 11, pp. 1284-1287, Nov. 2007

J11. Z. Luo, Y. Cai, S. X.-D. Tan, X. Hong, Y. Wang, Z. Pan, J. Fu, “Time-domain analysis methodology for large-scale RLC circuits and its  applications”, Science in China F Series, vol. 49, no. 5, pp. 665-680,  Oct., 2006.

J12. Y. Cai, L. Kang, J. Shi and X. Hong and S. X.-D. Tan, “Random walk guided decap embedding for power/ground network optimization”, IEEE Trans. Circuit and Systems-II (TCAS-II), vol. 55, no. 1, pp.36-40, Jan. 2008.

J13. Y. Cai, J. Shi, Z. Pan, X. Hong and S. X.-D. Tan, “Large scale P/G grid transient simulation using hierarchical relaxed approach”, Integration, the VLSI Journal, vol.41, no.1, pp.153-160,  Jan. 2008. 

J14. N. Mi, J. Fan, S. X.-D. Tan, Y. Cai and X. Hong, “Statistical analysis of on-chip power delivery networks considering lognormal leakage current variations with spatial correlations”, IEEE Transaction on Circuit and System I (TCAS-I), vol. 55, no. 7, pp.2064-2075, August, 2008.

J15. N. Mi, S. X.-D. Tan, Y. Cai and X. Hong, “Fast variational analysis of on-chip power grids by stochastic extended Krylov subspace method”, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 11, pp. 1996-2006, 2008.

J16. D. Li, S. X.-D. Tan, “Fast analysis of on-chip power grid circuits by extended truncated balanced realization method”, IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science,  vol. E92-A, no. 12,  pp.3061-3069, 2009.

Conference publications

C1 X.-D. Tan, C.-J. Shi, D. Lungeanu, J.-C. Lee, and L.-P. Yuan, “ Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programmings,”  Proc. IEEE/ACM 36^th Design Automation Conference (DAC), New Orleans, LA. June 1999,  pp. 78-83. Best Paper Award (< 1%)

C2 X.-D. Tan and C.-J. Shi,  “Fast power ground network optimization based on equivalent circuit modeling,” Proc. 38^th IEEE/ACM Design Automation Conference (DAC’2001),  Las Vegas, NE.  June 2001, pp.550-554.

C3 W. Guo and S. X.-D. Tan, “Circuit level alternating-direction-implicit  approach to transient analysis of power distribution networks”, in Proc. 5th International Conference on ASIC (ASICON’03), Beijing, China, Oct. 2003. pp.246-249, (Invited)

C4 J. Fu, Z. Luo, X. Hong, Y. Cai, S. X.-D. Tan and Z. Pan “A fast decoupling capacitor budgeting algorithm for robust on-chip power delivery”, Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’04), pp.505-510, Yokohama, Japan, Jan. 2004.

C5 Z. Pan, Y. Cai, S. X.-D. Tan, Z. Luo, X. Hong ,“Transient analysis of on-chip power distribution networks using equivalent circuit modeling”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’04), pp. 63-68, San Jose, CA , March 2004.

C6 W. Guo, S. X.-D. Tan, Z. Luo, X. Hong, “Partial random walk for large linear network analysis”, Proc. IEEE International Symposium on Circuits and Systems (ISCAS), Vancouver, Canada, pp. V173-176, May, 2004.

C7 J. Fu, Z. Luo, X. Hong, Y.  Cai, S. X.-D. Tan and Z. Pan, “Simultaneous wire sizing and decoupling capacitance budgeting for robust on-chip power delivery”, Intl. Workshop Power and Timing Modeling, Optimization and Simulation, (PATMOS’04), pp. 433-441, Greek.

C8 L. Zhang, Z. Luo, X. Hong, Y.  Cai, S. X.-D. Tan, J. Fu, “Optimal wire sizing in the early stage design of on-chip power/ground (P/G) networks”, Int, Conf. Solid State and Integrated Circuit Technology (ICSICT’04), Beijing, China, vol.3, pp.1936-1939, Oct. 2004.

C9 X. Wang, Z. Luo, X. Hong, Y.  Cai, S. X.-D. Tan, “EQUADI: A linear complexity algorithm for transient analysis for power/ground(P/G) networks in ASICs”, Int, Conf. Solid State and Integrated Circuit Technology (ICSICT’04), Beijing, China, vol. 3, pp.1952-1955, Oct. 2004.

C10 J. Fu, Z. Luo, X. Hong, Y. Cai, S. X.-D. Tan and Z. Pan, “VLSI on-chip power / ground network optimization considering decap leakage currents”, Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’05), pp.735-738, Shanghai, China, Jan. 2005.

C11 Z. Pan, Y. Cai, Z. Luo, X. Hong, S. X.-D. Tan, W.  Hou,  L. Wu, “Relaxed hierarchical power/ground grid analysis”, Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’05), pp.1090-1093, Shanghai, China, Jan. 2005.

C12 Z. Qi, and H. Li, S. X.-D. Tan,  L. Wu, Y. Cai,  X. Hong ,“Fast decap allocation algorithm for robust on-chip power delivery”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’05), pp. 542-547, San Jose, CA, March 2005.

C13 H. Li, Z. Qi, S. X-D. Tan, L. Wu, Y. Cai, X. Hong, “Partitioning-based approach to fast on-chip decap budgeting and minimization”, Proc. IEEE/ACM Design Automation Conference (DAC’2005), pp. 170-175, CA, 2005. Best Paper Award Nomination (16 out of 735 submission, 2%)

C14 J. Shi, Y. Cai, X. Hong, S. X-D. Tan, “Efficient simulation of power/ground networks with packages and vias”, Intl. Workshop Power and Timing Modeling, Optimization and Simulation (PATMOS’05), pp.257-266, Leuven, Belgium, Sep. 2005.

C15 Z. Qi, J. Fan, H. Li, S. X.-D. Tan, Y. Cai, X. Hong, “On-chip decoupling capacitor budgeting by sequence of linear programming”, in Proc. 6th International Conference on ASIC (ASICON), pp.98-101, Beijing China, Oct. 2005. (Invited).

C16 J. Shi, Y. Cai, S. X.-D. Tan, X. Hong, “ Efficient early stage resonance estimation techniques for C4 package”, Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’06),  pp.826-831, Yokohama City, Japan, Jan. 2006.

C17 J. Fan, I. Liao, S. X.-D. Tan, Y. Cai, X. Hong, “Localized on-chip power delivery network optimization via sequence of linear programming”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’06), pp.272-277, San Jose, CA, March 2006.

C18 A. Kahng, B. Liu,  S. X.-D. Tan, ”SMM: Scalable analysis of power delivery networks by stochastic moment matching”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’06), pp.638-643, San Jose, CA, March 2006.

C19 J. Shi, Y. Cai, X. Hong, S. X.-D. Tan, “High accurate pattern based precondition method for extremely large power/ground grid analysis”, ACM Symposium on Physical Design (ISPD’06), pp.108-113, San Jose, CA, April 2006.

C20 A. Kahng, B. Liu, S. X.-D. Tan, “Efficient decoupling capacitor planning via convex programming methods”, ACM Symposium on Physical Design (ISPD’06), pp.102-107, San Jose, CA, April 2006.

C21 N. Mi, J. Fan, S. X.-D. Tan, “Statistical analysis of power grid networks considering lognormal leakage current variations with spatial correlation”, in Proc. Int. Conf. Computer Design (ICCD), pp.56-62, San Jose, CA 2006.

C22 N. Mi, J. Fan, S. X.-D. Tan, “Simulation of power grid networks considering wires and lognormal leakage current variations”, IEEE International Workshop on Behavioral Modeling and Simulation (BMAS), pp.73-78, San Jose, CA, Sept., 2006.

C23 L. Kang, Y. Cai, X. Hong, S. X.-D. Tan, “Fast decoupling capacitor budgeting for power/ground networks using random walk approach”, Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’07),  pp.751-756, Yokohama City, Japan, Jan. 2007.

C24 N. Mi, S. X.-D. Tan, P. Liu, J. Cui, Y. Cai and X. Hong, “Stochastic extended Krylov subspace method for variational analysis of on-chip power grid networks”, Proc. IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), pp.48-53, San Jose, CA, Nov. 2007.

C25 X. Yuan, J. Fan, B. Liu, S. X.-D. Tan, “Stochastic based extended Krylov subspace method for power/ground network analysis”, in Proc. 7th International Conference on ASIC (ASICON’07), Guilin, China, Oct. 2007. (Invited).

C26 D. Li, S.X.-D. Tan, B. McGaughy, “ETBR: Extended truncated balanced realization method for on-chip power grid network analysis”,  Proc. Design, Automation and Test in Europe (DATE'08), pp.432-437,  Munich, Germany, March 2008. 

C27 Z. Luo, S. X.-D. Tan, “Statistic analysis of power/ground networks using single-node SOR method”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’08), pp. 867-872, San Jose, CA, March 2008.

C28 J. Cui, G. Chen, R. Shen, S. X.-D. Tan, W. Yu, J. Tong, “Variational capacitance modeling using orthogonal polynomial method”, Proc. IEEE/ACM International Great Lakes Symposium on VLSI (GLSVLSI’08), pp. 23-28, Orlando, 2008.

C29 B. Yan,  S. X.-D. Tan, G. Chen, L. Wu, “Modeling and simulation for on-chip power grid networks by locally dominant Krylov subspace method”, Proc. IEEE/ACM International Conf. on Computer-Aided Design (ICCAD),  pp. 744-749, San Jose, CA, Nov. 2008.

C30 D. Li, S. X.-.D. Tan, G. Chen and X. Zeng, “Statistical analysis of on-chip power grid networks by variational extended truncated balanced realization method” Proc. Asia  South Pacific Design Automation Conference (ASP-DAC’09), pp. 272-277, Yokohama, Japan, Jan. 2009.

C31 T. Eguia, N. Mi, S. X.-D. Tan, “Statistical decoupling capacitance allocation by efficient numerical quadrature method”, Proc. Int. Symposium. on Quality Electronic Design (ISQED’09), pp. 309-317, San Jose, CA, March 2009.

C32 X. Wang, Y. Cai, S. X.-D. Tan, X. Hong and J. Relles, “An efficient decoupling capacitance optimization using piecewise polynomial models”, Proc. Design, Automation and Test in Europe (DATE'09), pp.1190--1195, Nice, France, March 2009. 

C33 J. Shi, Y. Cai, W. Hou, L. Ma, S. X.-D. Tan,  P.-H. Ho and X. Wang, “GPU friendly fast Poisson solver for structured power grid network analysis”, Proc. IEEE/ACM Design Automation Conference (DAC’09), pp.178--183,  San Francisco, CA, 2009. (Best Paper Award Nomination (7 out of 682 submissions, 1%))

C34 X. Wang, Y. Cai, Q. Zhou, S. X.-D. Tan and T. Eguia, “Decoupling capacitance efficient placement for reducing transient power supply noise”, Proc. IEEE/ACM International Conf. on Computer-Aided Design (ICCAD),  pp. 745-751, San Jose, CA, Nov. 2009.

C35 D. Li, S. X.-D. Tan, N. Mi and Y. Cai, “Efficient power grid integrity analysis using on-the-fly error check and reduction”, Proc. Asia South Pacific Design Automation Conference (ASP-DAC’10), pp.763-768, Taipei, Taiwan, Jan. 2010.