0 0 10 views

**Unformatted text preview:**

Robust Gate Sizing via Mean Excess Delay Minimization Jason Cong1 2 John Lee3 and Lieven Vandenberghe3 1 Department of Computer Science California NanoSystems Institute 3 Department of Electrical Engineering University of California at Los Angeles 2 cong cs ucla edu lee vandenbe ee ucla edu ABSTRACT We introduce mean excess delay as a statistical measure of circuit delay in the presence of parameter variations The mean excess delay is defined as the expected delay of the circuits that exceed the quantile of the delay so it is always an upper bound on the quantile However in contrast to the quantile it preserves the convexity properties of the underlying delay distribution We apply the mean excess delay to the circuit sizing problem and use it to minimize the delay quantile over the gate sizes We use the Analytic Centering Cutting Plane Method to perform the minimization and apply this sizing to the ISCAS 85 benchmarks Depending on the structure of the circuit it can make significant improvements on the 95 quantile Categories and Subject Descriptors G 3 Probability and Statistics Probabilistic algorithms B 8 Performance and Reliability General General Terms Algorithms Design Keywords robust gate sizing process variation geometric programming conditional value at risk 1 INTRODUCTION As transistors become smaller the increasing effect of process variations may cause many circuits to fail 16 The random variations in the gate lengths oxide thicknesses and doping will increase the variations in the delay to a size too large to be ignored In this context it becomes necessary to make designs with robustness in mind To increase robustness of the design the gate sizes threshold voltages and other circuit parameters can be strategically assigned to improve the distribution of the circuit delay subject to power and area constraints After the main design is This is the author s version of the work It is posted here by permission of ACM for your personal use Not for redistribution The definitive version was published in the Proceedings of the 2008 International Symposium on Physical Design http doi acm org 10 1145 1353629 1353634 ISPD 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 to improve the yield of the circuit 7 In this paper we use circuit sizing to improve the timing robustness of a design This is not a new area and several approaches to this problem already exist In 6 the binyield loss function defined as the expected loss or penalty for circuits that exceed a given delay threshold is minimized using stochastic optimization Other groups have used slack redistribution to reallocate the statistical slack of each of the paths 15 The most popular method in literature estimates a worst case scenario for each gate and then sizes the circuit according to this estimate 9 14 11 These methods add a padding that is proportional to the standard deviation of the gate delay For the sake of simplicity these methods will be referred to as padded delay methods The deficiency of the padded delay methods is that it uses a conservative estimate and it cannot distinguish between correlated and uncorrelated variations In this paper we propose the Mean Excess Delay MED as a statistical measure of the delay in the presence of parameter variations This measure is used in the finance industry to minimize the risk associated with the value of an investment portfolio 13 In the context of circuits we show that MED is a convex function of the logarithm of the gate sizes and therefore well suited for minimization We also discuss a numerical algorithm for mean excess delay gate sizing and present some encouraging numerical results In summary there are two main contributions in the paper 1 The introduction of the Mean Excess Delay as a statistical measure of circuit delay The mean excess delay preserves the convexity of the underlying delay model and is therefore well suited for minimization 2 Numerical results that compare the padded delay method with the mean excess delay method for gate sizing The remainder of the paper is organized as follows Section II gives a background on the circuit sizing problem in its nominal and statistical forms In Section III we introduce the Mean Excess Delay function and explain its mathematical properties Section IV briefly outlines the minimization algorithm we use Results are shown in Section V 2 CIRCUIT SIZING WITH VARIATIONS In the circuit sizing problem the sizes of each gate are selected to minimize the delay of a circuit with constraints on the power and area 2 1 The Nominal Case 2 3 The Statistical Sizing Problem In the nominal case the variations in delay are ignored resulting in the following problem To convert the nominal problem 1 into one that minimizes the statistical delay we need to decide what it means to minimize a random variable One obvious definition is to focus on the quantile q x defined as minimize T nom x subject to A x Amax P x Pmax x 0 1 Here the optimization variable x is a vector of the log gate sizes or more accurately the log of the normalized gate scaling factors The functions T nom x A x and P x represent the nominal delay area and power of the circuit as a function of the log of the gate sizes x We assume the functions A x P x and T nom x are posynomials in convex 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 geometric programming see 2 2 2 The Statistical Delay The effects of the process variations on the delay are often modeled as follows 6 dk x v 1 vk dnom x k 2 x is the nominal delay dk x v is the In the above dnom k gate delay with the process variations and v is a vector of zero mean random variables with the same dimension as x vk denotes the kth element of the vector v The random variables vi are not restricted to be independent or Gaussian and may have correlations that are gate by gate dieto die or by location This model preserves convexity of dnom x That is if dnom x is convex then dk x v will be k k convex as well for fixed v Note that the distribution and the correlations of the random variable are unrestricted making this model general enough to handle a large class of variations For example correlations between the gate length or doping can be included in the random variable vi The only restriction is that the effect on the delay is