8A: Advancement in Power Analysis and Optimization


8A-1
Title Fast Decoupling Capacitor Budgeting for Power/Ground Network Using Random Walk Approach
Author *Le Kang, Yici Cai, Yi Zou, Jin Shi, Xianlong Hong (Tsinghua University, China), Sheldon X.-D. Tan (University of California, Riverside, United States)
Abstract This paper proposes a fast and practical decoupling capacitor (decap) budgeting algorithm to optimize the power ground (P/G) network design. The new method adopts a modified random walk process to partition the circuit. Then, by utilizing the isolation property of decaps, this new method avoids solving the large nonlinear programming problem in traditional decap optimization process. Also, this method integrates leakage currents optimization algorithm using a refined leakage model. Experimental results demonstrate that our proposed method achieves approximate a 10X speed up over the heuristic method based on sensitivity and only about 6% decap area deviation from the optimal budget using the programming method.
Slides (pdf file) 8A-1

8A-2
Title Timing-Aware Decoupling Capacitance Allocation in Power Distribution Networks
Author *Sanjay Pant, David Blaauw (University of Michigan, United States)
Abstract Power supply noise increases the circuit delay, which may lead to performance failure of the design. Decoupling capacitance (decap) addition is effective in reducing the power supply noise, thus making the supply network more robust in presence of large switching currents. Traditionally, decaps have been allocated in order to minimize the worst-case voltage drop in the power grid. In this paper, we propose an approach for timing aware decap allocation which uses global time slacks to drive the decap optimization. Non-critical gates with larger timing slacks can tolerate a relatively higher supply voltage drop as compared to the gates on the critical paths. The decap allocation is formulated as a non-linear optimization problem using Lagrangian relaxation and modified adjoint method is used to efficiently obtain the sensitivities of objective function to decap sizes. A fast path-based heuristic is also implemented and compared with the global optimization formulation. The approaches have been implemented and tested on ISCAS85 benchmark circuits and grids of different sizes. Compared to uniformly allocated decaps, the proposed approach utilizes 35.5% less total decap to meet the same delay target. For the same total decap budget, the proposed approach is shown to improve the circuit delay by 10.1% on an average.
Slides (pdf file) 8A-2

8A-3
Title Fast Placement Optimization of Power Supply Pads
Author Yu Zhong, *Martin D. F. Wong (University of Illinois at Urbana-Champaign, United States)
Abstract Power grid networks in VLSI circuits are required to provide adequate input supply to ensure reliable performance. In this paper, we propose algorithms to find the placement of power pads that minimize not only the worst voltage drop but also the voltage deviation across the power grid. Our algorithm uses simulated annealing to minimize the total cost of voltage drops. The key enabler for efficient optimization is a fast localized node-based iterative method to compute the voltages after each movement of pads. Experimental results show that our algorithm demonstrates good runtime characteristics for power grids with large numbers of pad candidates in multi-million-size circuits. For a 16-million-node power grid with 646 thousand pad candidates, our algorithm took 72 minutes to improve the worst voltage drop from $0.398 V$ to $0.196 V$ and reduce the deviation of voltages on the power grid from $0.134 V$ to $0.024 V$.
Slides (pdf file) 8A-3

8A-4
Title Efficient Second-Order Iterative Methods for IR Drop Analysis in Power Grid
Author Yu Zhong, *Martin D. F. Wong (University of Illinois at Urbana-Champaign, United States)
Abstract Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. It has been shown that first-order iterative algorithms based on node-by-node and row-by-row traversals of the power grid have both accuracy and runtime advantages over the well-known Random-Walk method. In this paper, we propose second-order iterative algorithms that can significantly reduce the runtime. The new algorithms are extremely fast, and we prove that they guarantee converge to the exact solutions. Experimental results show that our algorithms outperform the Random-Walk algorithm and the first-order algorithms. For a 25-million node problem, while the Random-Walk algorithm takes 2 days with maximum error of 6.1 mV, and our second-order row-based algorithm takes 32 minutes to get an exact solution. Moreover, we can get a solution with maximum error 2 mV in 10 minutes.
Slides (pdf file) 8A-4

8A-5
Title A Current-based Method for Short Circuit Power Calculation under Noisy Input Waveforms
Author Hanif Fatemi, Shahin Nazarian, *Massoud Pedram (University of Southern California, United States)
Abstract An accurate model is presented in this paper to calculate the short circuit energy dissipation of logic cells. The short circuit current is highly dependent on the input and output voltage values. Therefore the actual shape of the voltage signal waveforms at the input and output of the cell should be considered in order to precisely calculate the short circuit energy. Previous approaches such as the approximation of the crosstalk induced noisy waveforms with saturated ramps can lead to short circuit energy estimation errors as high as orders of magnitude for a minimum sized inverter. To resolve this shortcoming, a novel current-based logic cell model is utilized, which constructs the output voltage waveform for a given noisy input waveform. The input and output voltage waveforms are then used to calculate the short circuit current, and hence, short circuit energy dissipation. A characterization process is executed for each logic cell in the standard cell library to model the relevant electrical parameters e.g., the parasitic capacitances and nonlinear current sources. Additionally, our model is capable of calculating the short circuit energy dissipation caused by glitches in VLSI circuits, which in some cases can be a key contributor to the total circuit energy dissipation. Experimental results show an average error of about 1% and a maximum error of about 3% compared to SPICE for different types of logic cells under noisy input waveforms including glitches while the runtime speedup is up to 16000.
Slides (pdf file) 8A-5
Last Updated on: January 29, 2007