IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF …

1 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 34, NO. 3, MARCH 2015 409. Efficient Transient analysis of power delivery network With Clock/ power Gating by Sparse Approximation Hengliang Zhu, Member, IEEE, Yuanzhe Wang, Frank Liu, Senior Member, IEEE, Xin Li, Senior Member, IEEE, Xuan Zeng, Member, IEEE, and Peter Feldmann, Fellow, IEEE. Abstract Transient analysis of large-scale power delivery net- For this reason, appropriate DESIGN and verification of on-chip work (PDN) is a critical task to ensure the functional correctness PDNs is an extremely important task for today's system-on- and desired performance of today's integrated circuits (ICs), chip.

2 Especially if significant transient noises are induced by clock and/or power gating due to the utilization of extensive power During the past decade, a large number of COMPUTER-AIDED management. In this paper, we propose an efficient algorithm DESIGN (CAD) algorithms have been developed for efficient for PDN transient analysis based on sparse approximation. The PDN analysis [4] [20]. These existing techniques can be key idea is to exploit the fact that the transient response caused classified into several broad categories: 1) Krylov subspace by clock/ power gating is often localized and the voltages at many method [9], [10]; 2) hierarchical analysis [11]; 3) multigrid other inactive nodes are almost unchanged, thereby rendering a unique sparse structure.

3 By taking advantage of the underlying solver [12] [16]; 4) randomized algorithm [17]; and 5) vec- sparsity of the solution structure, a modified conjugate gradient torless analysis [18] [20]. Most of them focus on DC analysis algorithm is developed and tuned to efficiently solve the PDN in order to predict the IR drops which play an important role analysis problem with low computational cost. Our numerical in both signal integrity ( , increased gate delay) and circuit experiments based on standard benchmarks demonstrate that reliability ( , electromigration for metal wires). For transient the proposed transient analysis with sparse approximation offers up to runtime speedup over other traditional methods, while analysis of PDNs, the existing approaches can be further cate- simultaneously achieving similar accuracy.

4 Gorized as: 1) implicit numerical integration ( , back Euler method, trapezoidal method, two-step backward differentiation Index Terms Conjugate gradient (CG), orthogonal match- ing pursuit (OMP), power delivery network (PDN), sparse method, etc.) and 2) explicit numerical integration ( , matrix approximation, transient analysis . exponential method [10]). These algorithms have been suc- cessfully applied to a large number of practical PDN problems. While PDN analysis has been extensively studied in the I. I NTRODUCTION literature, the aggressive scaling of IC technologies brings N-CHIP power delivery network (PDN) is a complex O 3-D interconnect circuit that connects off-chip power sources with on-chip circuit blocks [1] [3].

5 When a large several recent trends that suggest a need to revisit this topic. 1) Clock and/or power Gating: In order to achieve low- power operation for today's digital ICs, clock and/or amount of currents flow through the PDN, large voltage power gating techniques are commonly used to dynam- fluctuations due to IR drops and/or di/dt noises are often ically turn on/off one or more functional blocks on observed. These noises posed by PDN significantly impact the same chip [21] [23]. When these blocks are simul- the functionality and performance of integrated circuits (ICs). taneously switched on/off, large transient noises ( , overshooting) are often observed in the PDN due to its Manuscript received June 27, 2014; revised October 5, 2014; accepted underdamped nature.

6 In this case, transient analysis over December 18, 2014. Date of publication January 23, 2015; date of cur- rent version February 17, 2015. This work was supported in part by the a long time period, instead of DC analysis , is required National Natural Science Foundation of China Research Project under Grant to accurately capture these transient noises that die out 91330201, Grant 61106032, Grant 61125401, Grant 61376040, and Grant slowly. 61228401, in part by the National Basic Research Program of China under Grant 2011CB309701, in part by the National Major Science and Technology 2) Increased PDN Size: With technology scaling, the com- Special Project of China under Grant 2014ZX02301002-002, and in part by the plexity of PDN continuously increases.

7 The PDN of Shanghai Science and Technology Committee Project under 13XD1401100. a state-of-the-art high-performance microprocessor con- This paper was recommended by Associate Editor A. Demir. H. Zhu and X. Zeng are with the State Key Laboratory of ASIC & System, sists of hundreds of millions of internal nodes. Hence, Microelectronics Department, Fudan University, Shanghai 201203, China. PDN analysis must be scalable to extremely large Y. Wang and X. Li are with the Department of Electrical and Computer problem size to meet today's DESIGN reality. Engineering, Carnegie Mellon University, Pittsburgh, PA 15123 USA (e-mail: The combination of the aforementioned two trends makes F.)

8 Liu is with the IBM Austin Research Laboratory, Austin, TX 78758 USA. most traditional techniques ill-equipped to perform large-scale P. Feldmann is with the D. E. Shaw Research, New York, NY 10036 USA. transient analysis for PDNs. On one hand, direct linear solvers Color versions of one or more of the figures in this paper are available online at ( , LU decomposition, Cholesky decomposition, etc.) can Digital Object Identifier be extremely efficient for transient analysis of small- and 0278-0070 c 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See for more information. 410 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL.

9 34, NO. 3, MARCH 2015. medium-scale PDNs, especially if a constant time step is used II. BACKGROUND. and, hence, only a single matrix factorization is required [10]. A. Transient analysis of PDN. However, these direct linear solvers are not applicable to A PDN is typically modeled as an RLC network with ideal large-scale PDN analysis problems due to their high compu- voltage and current sources. Without loss of generality, we tational complexity and memory usage. On the other hand, mathematically represent a PDN by the following modified iterative linear solvers ( , multigrid method) are not effi- nodal analysis (MNA) equation [25]: cient either, if they must be repeatedly applied to solve.

10 Large-scale linear equations at a large number of time points C0 v (t) G ATL v(t) iS (t). during transient analysis . The fundamental question here + = (1). 0 L i (t) AL 0 i(t) vS (t). is how to make transient analysis computationally feasi- ble for large-scale PDNs with consideration of clock/ power where v(t) RM is a vector containing all node voltages, gating. i(t) RN is a vector containing all branch currents asso- In this paper, we propose a novel algorithm for PDN ciated with inductors, iS (t) RM is a vector containing all transient analysis based on sparse approximation. We par- input current sources, vS (t) RN is a vector containing all ticularly focus on the challenging problem of PDN analysis input voltage sources, and C RM M , L RN N , G.