Accelerating Gate Sizing Using Graphics Processing Units

In this paper, we investigate the gate sizing problem and develop techniques for improving the runtime by effectively exploiting the graphics processing unit (GPU) resources. Theoretically, we investigate a randomized cutting plane-based convex optimization technique which is highly parallelizable and can effectively exploit the single instruction multiple data structure imposed by GPUs. In order to further improve the runtime, we also develop GPU-oriented implementation guidelines that exploit the specific structure that convex gate sizing formulations impose. We implemented our method on NVIDIA Tesla 10 GPU and obtain 21× to 400× speedup compared to the MOSEK optimization tool implemented on conventional CPU. The quality of solution of our method is very close to that achieved by MOSEK, since both are optimal.