Lagrangian relaxation for gate implementation selection Conference Paper uri icon


  • In a typical circuit optimization flow, one essential decision is to select the implementation for each gate according to a cell library. An implementation implies specific gate size, threshold voltage, etc. The selection normally needs to handle multiple and often conflicting objectives. An effective approach for multi-objective optimization is Lagrangian relaxation (LR), which has been adopted in continuous gate sizing. When LR is applied to the gate implementation selection, the Lagrangian dual problem is no longer convex like in continuous gate sizing, and conventional sub-gradient method becomes inefficient. In this paper, we propose a projection-based descent method and a new technique of Lagrangian multiplier distribution for solving the Lagrangian dual problem in discrete space. Experimental results demonstrate that our approach leads to significantly better solution quality and faster convergence compared to the sub-gradient method. 2011 ACM.

name of conference

  • the 2011 international symposium

published proceedings

  • Proceedings of the 2011 international symposium on Physical design - ISPD '11

author list (cited authors)

  • Huang, Y., Hu, J., & Shi, W.

citation count

  • 9

complete list of authors

  • Huang, Yi-Le||Hu, Jiang||Shi, Weiping

publication date

  • January 2011