Provably Fast and Near-Optimum Gate Sizing.

We present a new approach for the cell selection problem based on a resource sharing formulation, which is a specialization of Lagrangian relaxation with multiplicative weight updates. For the convex continuous gate sizing problem, we can prove fast polynomial running times. This theoretical result also gives some justification to previous heuristic multiplicative weight update methods. For the discrete cell selection problem, where voltage thresholds can also be chosen, we employ the new algorithm heuristically and achieve superior results on industrial benchmarks compared with one of the previously best known algorithms, and competitive results on the ISPD 2013 benchmarks. Finally, we demonstrate how the approach can be parallelized effectively achieving speed-ups of up to 16. [ABSTRACT FROM AUTHOR]