بودجه بندی افتراق خازن مبتنی بر پارتیشن بندی از طریق توالی برنامه ریزی خطی

In this paper, we propose an efficient algorithm to reduce the voltage noises for on-chip power/ground (P/G) networks of VLSI. The new method is based on the sequence of linear programming (SLP) as the optimization engine, and partitioning scheme for dealing with large-sized circuits. We show that by directly optimizing the decoupling capacitor (decap) areas as the objective function and using the time-domain adjoint method, SLP can deliver much better quality in terms of decap budget than existing methods based on the merged time-domain adjoint method. The partitioning strategy further improves the scalability of the proposed algorithm and makes it efficient for larger circuits. The resulting algorithm is general enough for any P/G network. Experimental results demonstrate the advantage of the proposed method over existing state-of-the-art methods in terms of solution quality at a mild computation cost increase.

In modern deep sub-micron and nanometer VLSI technology, signal integrity is among the most important concerns for circuit designers. With reduced noise margins and increased switching frequency, reliable on-chip power supply has become a critical factor for robust circuit performance. Power/ground (P/G) networks are devoted to supplying power to all on-chip modules. Extra design effort is often required to reduce voltage noises in P/G networks, so that the variation in power supply voltage and reference ground voltage is confined within a certain percentage (for example, say 10%10%) of nominal values. Excessive voltage drops and ground bounces not only may degrade noise margins and increase gate delays, but also lead to false logic switching and logic failure. P/G network design and optimization has been studied extensively in previous works [1], [2], [3], [4], [5], [6], [7] and [8]. Besides early stage design techniques, such as topology selection and wire-sizing, adding decoupling capacitance (decaps) has been accepted as an effective and standard approach to remove excessive instantaneous voltage variations induced by IR drops. The modeling of power grid network is shown in Fig. 1. Conceptually thinking, decaps provide a reservoir of current that is instantly available for nearby switching components, thus removing spikes and glitches in the power rail. Intuitively, decaps have a strong local effect and should be placed around logic units that tend to draw large currents. Indeed, in some early P/G designs, decaps were added manually after the current pattern of digital modules was observed. However, on-chip decaps are typically manufactured using MOSFET transistors, and excessive on-chip decaps would not only consume on-chip area, but also cause more leakage power, lower yield, and lower resonant frequency [1]. Therefore, as long as power supply noises are constrained, decaps should be minimized. Note that the main purpose of adding decap is not to save the chip area. Instead, we try to reduce the voltage noises (or IR drops) on the power delivery networks. Also, decaps can help reducing the delay, due to the reduction of voltage drops. At the same time, we want to use as smaller decap as possible as decap will introduce more power consumption and occupy more chip resources (white space, WS). Actually, decaps may induce more leakage currents. Therefore, we should use them economically, which is the main goal of this paper. Full-size image (14 K) Fig. 1. The model of power grid network. Figure options The optimization of decap placement has been extensively studied in the past [2], [4], [5], [6], [7], [8] and [9]. Some earlier works [2] and [9] place decaps according to estimation of noises in the power supply caused by nearby digital modules, while more recent works treat it more mathematically as a nonlinear optimization problem and employ the adjoint method (or its variant) to compute sensitivity first, then adopting different optimization techniques like quadratic programming (QP) [4] or sequential quadratic programming (SQP) [6], conjugate gradient (CG) [5] or CG combined with binary search [7] and [8]. To compute sensitivity, transient simulations of the whole P/G network have to be carried out at every optimization step. Given the fact that the transient simulation of P/G networks with millions of nodes is already an extremely time-consuming task, the CPU time and memory cost of optimization methods that perform transient simulations in internal loops will be prohibitive. To combat this, earlier works [6] and [10] proposed a method to reduce the P/G grid first and then apply standard optimization techniques. For larger circuits, some previous work [8] partitions the circuit into smaller sub-circuits before optimizing them individually. In this paper, we propose an efficient decap allocation algorithm, which explicitly minimizes the decap areas subject to voltage drops and other design rule constraints. We formulate the decap allocation problem as a linear programming problem and solve it by the sequence of linear programming (SLP) method. We only address the decap optimization for voltage drop here. However, the situation of ground bounces can be easily dealt within a similar fashion. To achieve higher efficiency with large circuits, a partition strategy similar to [8] is employed to take advantage of the localized effect of decaps. The new algorithm is especially suitable for P/G grids with a few troubling spots. This is typically the case for a properly designed P/G grid, or when a priori decaps have already been added based on some simple estimation. Experimental results show that the new algorithm yields significantly less decap area than the recently proposed decap allocation algorithm with a mild computation cost increase [8]. The rest of this paper is organized as follows. The next section describes the decap optimization problem and briefly reviews existing sensitivity-based decap budgeting algorithms. Section 3 formulates decap budgeting into an SLP problem. Section 4 introduces the partition strategy and presents the flow of our partitioning-based SLP optimization. Experimental results are presented in Section 5, and Section 6 concludes the paper.

This paper has proposed a localized SLP optimization flow for on-chip decaps allocation [22] and [23]. In our problem formulation, decap budget is explicitly minimized as the objective function. In comparison to existing CG and other nonlinear programming methods, the SLP based method, with the time-domain adjoint method, demonstrates better solution quality. The partitioning strategy improves the scalability of the algorithm and makes it efficient for large circuits. The proposed algorithm is general enough for any P/G network. Experimental results showed that for circuits without too many violation nodes, which is usually the case for well designed P/G grids, the proposed algorithm usually yields much smaller decap area at a mildly larger computation cost than the most recently published decap budgeting algorithms. Moreover, one consideration is that the modeling of PWL current sources as the current sinks may be stochastic in nature. One possible direction of our future researches may include the statistical analysis of the variations in those current sources.