Robust Gate Sizing via Mean Excess Delay MinimizationJason Cong1,2, John Lee3and Lieven Vandenberghe31Department of Computer Science2California NanoSystems Institute3Department of Electrical EngineeringUniversity of California at Los [email protected], {lee, vandenbe}@ee.ucla.eduABSTRACTWe introduce mean excess delay as a statistical measure ofcircuit delay in the presence of parameter variations. Theβ-mean excess delay is defined as the expected delay of thecircuits that exceed the β-quantile of the delay, so it is alwaysan upper boun d on th e β- quantile. However, in contrast tothe β-quantile, it preserves the convexity properties of theunderlying delay distribution. We apply the β-mean excessdelay to the circuit sizing problem, and use it to minimizethe delay quantile over the gate sizes. We use the AnalyticCentering Cutting Plane Method to perform the minimiza-tion and apply this sizing to the ISCAS ‘85 benchmarks.Depending on the structure of the circuit, it can make sig-nificant improvements on the 95%-quantile.Categories and Subject DescriptorsG.3 [Probability and Statistics]: Probabilistic algorithms;B.8 [Performance and Reliability]: GeneralGeneral TermsAlgorithms, DesignKeywordsrobust gate sizing, process variation, geometric program-ming, conditional value-at-risk1. INTRODUCTIONAs transistors become smaller, the increasing effect of pro-cess variations may cause many circuits to fail [16]. Therandom variations in the gate lengths, oxide thicknesses anddoping will increase the variations in the delay to a size toolarge to be ignored. In this context it becomes necessary tomake designs with robustness in mind.To increase robustness of the design, the gate sizes, thresh-old voltages and other circuit parameters can be strategicallyassigned to improve the distribution of the circuit delay, sub-ject to power and area constraints. After the main design isThis is the author’s version of the work. It is posted here by permission ofACM for your personal use. Not for redistribution. The definitive versionwas published in the Proceedings of the 2008 International Symposium onPhysical Design, http://doi.acm.org/10.1145/1353629.1353634ISPD’08 April 13–16, 2008, Portland, Oregon, USA.Copyright 2008 ACM 978-1-60558-048-7/08/04.completed, redundancy and regularity can also be added toimprove the yield of the circuit [7].In this paper we use circuit sizing to improve the t imingrobustness of a design. This is not a new area, and severalapproaches to this problem already exist. In [6] the bin-yield loss function, defined as the expected loss or penaltyfor circuits that exceed a given delay threshold, is minimizedusing stochastic optimization. Other groups have used slackredistribution to reallocate the statistical slack of each of thepaths [15]. The most popular method in literature estimatesa worst-case scenario for each gate, and then sizes t he circuitaccording to this estimate [9, 14, 11]. These methods add a“padding” that is proportional to the standard deviation ofthe gate delay. For the sake of simplicity, these methods willbe referred t o as “padded delay methods.” The deficiencyof the padded delay methods is that it uses a conservativeestimate and it cannot distinguish between correlated anduncorrelated variations.In this paper we propose the Mean Excess Delay (MED)as a statistical measure of the delay in the presence of p aram-eter variations. This measure is used in the finance industryto minimize the risk associated with the value of an invest-ment portfolio [13]. In the context of circuits, we show thatMED is a convex function of the logarithm of the gate sizes,and therefore well-suited for minimization. We also discussa numerical algorithm for mean excess d elay gate sizing, andpresent some encouraging numerical results.In summary there are two main contributions in the paper:1. The introduction of the Mean Excess Delay as a statis-tical measure of circuit delay. The mean excess d elaypreserves the convexity of the underlying delay model,and is therefore well-suited for minimization.2. Numerical results that compare the padded d elay methodwith the mean-excess delay method for gate sizing.The remainder of the paper is organized as follows. Sec-tion II gives a background on the circuit sizing problem inits nominal and statistical forms. In Section III we introducethe Mean Ex cess Delay function, and explain its mathemat-ical properties. Section IV briefly outlines the minimizationalgorithm we use. Results are shown in S ection V.2. CIRCUIT SIZING WITH VARIATIONSIn the circuit sizing problem, the sizes of each gate areselected to minimize the delay of a circuit with constraintson the power and area.2.1 The Nominal CaseIn the nominal case, th e variations in delay are ignored,resulting in the following problemminimize Tnom(x)subject to A(x) ≤ AmaxP (x) ≤ Pmaxx ≥ 0.(1)Here, the optimization variable x is a vector of the log-gatesizes (or more accurately, the log of the normalized gatescaling factors). The functions Tnom(x), A(x) and P (x) rep-resent the nominal delay, area and power of the circuit asa function of the log of the gate sizes x. We assume thefunctions A(x), P (x) and Tnom(x) are posynomials in con-vex form [3]. This problem has been studied extensively,and can be solved efficiently via geometric programming [5,8]. For a good tutorial on circuit optimization via geometricprogramming, see [2].2.2 The Statistical DelayThe effects of the process variations on the delay are oftenmodeled as follows [6]:dk(x, v) = (1 + vk) dnomk(x). (2)In the above, dnomk(x) is the nominal delay, dk(x, v) is thegate delay with the process variations, and v is a vector ofzero-mean random variables with the same dimension as x(vkdenotes the kthelement of the vector v). The randomvariables viare not restricted to be independent or Gaus-sian, and may have correlations that are “gate by gate”, “die-to-die”, or by location. This model preserves convexity ofdnomk(x). That is, if dnomk(x) is convex, then dk(x, v) will beconvex as well for fixed v.Note that the distribution and the correlations of the ran-dom variable are unrestricted, making this model generalenough to handle a large class of variations. For example,correlations between the gate length or doping can be in-cluded in the random variable vi. The only restriction isthat the effect on the delay is multiplicative, and the stan-dard deviation of the variations is indep endent of the size