Lagrangian Relaxation for Gate Implementation Selection Yi-Le Huang Department of ECE Texas A&M University College Station, TX 77843 [email protected] Jiang Hu Department of ECE Texas A&M University College Station, TX 77843 [email protected] Weiping Shi Department of ECE Texas A&M University College Station, TX 77843 [email protected] ABSTRACT 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. 1 Categories and Subject Descriptors B.7 [Integrated Circuits]: Design Aids General Terms Algorithms, Design Keywords Gate sizing, Lagrangian relaxation, Optimization, Low power, Threshold voltage 1. INTRODUCTION In deep sub-micron technologies, minimization of leakage power becomes a main concern as we try to combat the increase in the overall circuit power consumption. In addition, power consumption directly relates to battery life, reliability, packaging and heat removal cost. Therefore, how to efficiently handle trade-off between circuit performance and power consumption becomes a big issue in current design flow. Gate sizing [1] has been one of the most popular methods for circuit optimization, such as area/timing and area/power/timing, for long time. Besides, in recent years people start to pay attention to leakage power and try This work is partially supported by Intel. to manage leakage power by using different threshold voltage (Vt) levels [2-4]. Gates with higher Vt level are used on non-critical paths to reduce leakage power and those on critical paths work under lower Vt level for retaining desired performance. There are many similarities between discrete gate sizing and Vt assignment, and hence they can be easily combined with each other for combinational circuit optimization [5-10]. Most of simultaneous gate sizing and Vt assignment methods are either sensitivity-based heuristics [2,8] or mathematical programming methods [3,9,11]. In sensitivity-based heuristics, people use sensitivity functions to choose gate size and Vt level. Usually, the sensitivity function only considers local information, like the efficiency of trading power for performance for single gate. However, the greedy nature makes sensitivity-based methods easily to fall into local optima. In [1], continuous gate/transistor sizing is formulated as geometric programming. In [11,12], Lagrangian relaxation (LR) is used to solving the sizing problem and proved to converge and guarantee optimality. Nowadays, circuits are implemented by gates in standard cell library provided by foundries or library companies. Sizes and Vt options of logic gates are limited and discretely specified in the standard cell library. In [13, 14], continuous solutions are rounded to the nearest discrete options in a library but the rounding may result in large rounding errors if options in standard cell library are highly discrete [15]. In [16], simultaneous discrete gate sizing and Vt assignment is solved by Lagrangian relaxation along with a dynamic programming (DP)-like method without rounding. In general, LR is effective on handling multiple conflicting objectives or complex constraints. The effectiveness is obtained by transforming the original optimization into a Lagrangian sub-problem and a Lagrangian dual problem. The efficiency of LR is successfully demonstrated in continuous gate sizing [11, 12, 17]. The work of [16] employs LR for solving simultaneous discrete gate sizing and Vt assignment. It mainly focuses on the algorithm of solving the Lagrangian sub-problem, and solves the dual problem using sub-gradient method like in continuous gate sizing [11,12]. For discrete cases, the Lagrangian dual problem is no longer convex like in many continuous cases. Therefore, the conventional sub-gradient method becomes inefficient. In this work, we attempt to solve the problem of gate implementation selection. A gate implementation means specific gate size, Vt level, etc. according to a cell library. We also adopt the LR approach to handle power-performance tradeoff. Our focus is on new techniques for solving the Lagrangian dual problem. We propose a projection-based descent method and a new technique of Lagrangian multiplier distribution. Compared to the conventional sub-gradient method, our algorithm leads to not only Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ISPD’11, March 27–30, 2011, Santa Barbara, California, USA. Copyright 2011 ACM 978-1-4503-0550-1/11/03...$10.00. 167considerably better solution quality but also faster convergence. Our algorithm can satisfy tight timing constraints for which sub-gradient method fails. When timing constraints are loose, our algorithm results in about 33% power reduction than sub-gradient method. The rest of this paper is organized as follows. In Section II, we introduce some notations and terminology used in this paper. The detailed problem formulation is also given. In