Improved lagrangian relaxation-based gate size and V T assignment for very large circuits

The 2013 International Symposium of Physical Design (ISPD) contest for discrete (library-based) gate sizing with wire loads has led to improved algorithms for gate (cell) size optimization and threshold voltage (VT) optimization. However, it was noted that the best of the prior published algorithms fall well short of optimal for very large circuits, on the order of one million cells or larger. In order to get substantially better results for very large circuits, several critical extensions to the standard Lagrangian Relaxation (LR) based sizing formulation were added. First, we developed the first LR extension that explicitly treats wire delays in the formulation. Also, we enhanced the LR formulation to include the depth of the cell in the logic network during the LR λ propagation scheme, thereby controlling the effects of λ accumulation for gates nearer the primary inputs. Thirdly, we propose the first global heuristics for the recovery of slack and excess leakage during the LR iterations. Indeed, the new LR formulation achieves a significant 50% lower leakage for the benchmark designs on the order of one million cells. For small benchmarks around 100k cells or smaller, we believe that the prior published results are near optimal, and indeed our new approach yields similar results.