Power network verication and optimization at planning stages

Power integrity has become a critical issue in nano-scale VLSI design. With technology scaling, the circuit integration density grows rapidly. However, the number of IO's dedicated for power does not scale up accordingly due to limited advancement in packaging technology. The increase of total current causes large voltage drops in the on-chip power grid, and the increase of clock frequencies results in large Ldi/dt noise due to the inductive effect of the power grid. Voltage drops degrade circuit timing performance while voltage bounces may cause reliability issues. On the other hand, the decrease in supply voltage leads to a smaller noise margin which makes the design of on-chip power grid an even more challenging task. As a result, full-chip power grid verification and optimization have become essential for reliable chip design. In the first part of this thesis, we propose novel methods of generating the worst-case noise for early power distribution system verification. These methods take into account the effect of the transition time of load currents, and thus allow a more realistic worst-case noise prediction. In the case of one current source, we introduce a dynamic programming algorithm on the time- domain impulse response of the power distribution system, and a modified Knuth-Yao Quadrangle Inequality Speedup is developed which reduces the time complexity of the algorithm to O(nmlog n), where n is the number of discretized current values and m is the number of zeros of the system impulse response. In the case of multiple current sources, the dynamic programming algorithm is extended to generate the worst-case noise subject to a set of hierarchical current constraints. We show that the hierarchical constraints can be generalized into submodular polyhedron constraint and our algorithms still work. Furthermore, for other general magnitude and slope constraints of current sources, we propose the solutions by network flow and submodular flow which are more efficient than direct linear programming solution. The second part of the thesis describes a power grid sizing method to minimize the worst voltage drop over all test locations and current source distributions. We reduce the original problem into a convex programming problem whose objective is to minimize the maximum effective resistance between the current entry node and all current exit nodes under the constraint of constant total wire area. In order to solve the convex programming problem efficiently, we adopt a Krylov space method to evaluate the effective resistances simultaneously and deduce a simple formula to update the derivative of effective resistance relative to perturbation of wire widths gradually. The proposed optimization method can also be applied to power grids in the real world, which are required to have small effective resistances among power stations for reducing the power losses during long distance transmission. Finally, we propose a method for dynamic power distribution network verification and optimization at early design stages. This approach predicts and minimizes the worst total voltage violation area for all outputs of a given on-chip power grid with multiple current sources. We assume duty-cycle constraints, group magnitude constraints and transition time constraints on current sources which makes the prediction more realistic. Simultaneously, we minimize the worst violation area through the allocation of decoupling capacitors (Decap) and controlled equivalent series resistors (ESR). Based on the simulation of adjoint network, the sensitivity of the violation area relative to current sources, Decap and ESR can be derived and the sequential quadratic programming method is adopted for optimizatio