Fast decap allocation algorithm for robust on-chip power delivery

Adding on-chip decoupling capacitors (decaps) is an effective way to reduce voltage noise in power/ground networks and ensure robust power delivery. We present a fast decap allocation algorithm, which is able to confine voltage fluctuations below a user specified threshold by adding decaps in an area efficient way. The new algorithm adopts the recently proposed time-domain adjoint network method for sensitivity calculation. To avoid the time consuming line search at each iteration in the conjugate gradient method, we propose a simple, yet efficient, search step computation method to accelerate the optimization process. The experimental results show that the proposed algorithm is at least 10 times faster than the fastest conjugate gradient method reported so far with similar optimization results.