Random walk guided decap embedding for power/ground network optimization

The reliability of Power/Ground networks is becoming significantly important in modern integrated circuits, while decap insertion is a main approach to enhance the power grid safety. In this brief, we propose a fast and efficient decap allocation algorithm, and adequately consider the leakage effect of decap. This approach borrows the idea of random walks to perform circuit partitioning and does subsequent decap insertion based on locality property of partitioned area, which avoids solving a large nonlinear programming problem in traditional decap optimization process. The optimization flow also integrates a refined leakage current model for decaps which makes it more practical. Experimental results show that our proposed method can achieve approximate 15X speed up over the optimal budget method within the acceptable error tolerance. Also this algorithm only causes a few penalty area to compensate the leakage effect.