On-chip decoupling capacitor budgeting by sequence of linear programming

Excessive power supply noise increases propagation delay of switching gates and reduces noise margin of the circuit. Adding on-chip decoupling capacitors (decaps) is an effective way to reduce voltage noise in a on-chip power delivery system. In this paper, we propose an efficient and novel algorithm to allocate decaps in an area efficient way. The new algorithm applies the sequence of linear programming based approach to searching the minimum decap area to reduce voltage drop below user specified threshold. We show existing sensitivity based decap allocation algorithms tend to over estimate the decap areas due to nonlinear sensitivity dependence on decap values. Experimental results show that the proposed algorithm uses significantly less decap area than the existing conjugate gradient based approach but with similar CPU runtimes