Minimum Decoupling Capacitor Insertion in VLSI Power/Ground Supply Networks by Semidefinite and Linear Programs

Nanometer-scale VLSI design demands reliable on-chip power/ground (P/G) supply. Decoupling capacitors effectively reduce P/G supply fluctuation at the cost of leakage increase and yield loss. Existing P/G supply network decoupling capacitor insertion techniques are based on sensitivity analysis and greedy optimization. In this paper, we propose a semidefinite program and a linear program for minimum decoupling capacitor insertion in a P/G supply network, which are global optimizations with theoretically guaranteed supply voltage degradation bounds. We also propose scalability improvement schemes which enable application of the proposed semidefinite and linear programs to practical industry designs. Our experimental results on industry designs verify that the proposed semidefinite program guarantees supply voltage degradation bound for all possible supply current sources, while the proposed linear program achieves the most accurate supply voltage degradation control for a given set of supply current sources.