Loading...
Please wait, while we are loading the content...
Similar Documents
Static Timing Analysis Based on Partial and Distribution-Free Probabilistic Descriptions of Delay Uncertainty
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wang, Wei-Shen Kreinovich, Vladik |
| Copyright Year | 2005 |
| Abstract | The existing approaches to timing analysis under uncertainty are based on fundamentally restrictive assumptions. Statistical STA techniques assume that the full probabilistic distribution of timing uncertainty is available. In reality, the complete probabilistic distribution information is often unavailable. The existing alternative of treating uncertainty as interval-based, or affine, is also limited since it cannot handle probabilistic information in principle. In this paper, a fundamentally new paradigm for timing uncertainty description is proposed as a way to consistently and rigorously handle partially available descriptions of timing uncertainty. The paradigm is based on a formal theory of interval probabilistic models that permit handling parameter uncertainty that is described in a distribution-free mode just via the range, the mean, and the variance. This permits effectively handling multiple real-life challenges, including imprecise and limited information about the distributions of process parameters, parameters coming from different populations, and the sources of uncertainty that are too difficult to handle via full probabilistic measures (e.g. on-chip supply voltage variation). Specifically, analytical techniques for bounding the distributions of probabilistic interval variables are proposed. Also, a provably correct strategy for fast Monte Carlo simulation based on probabilistic interval variables is introduced. A path-based timing algorithm implementing the novel modeling paradigm, as well as handling the traditional variability descriptions, has been developed. The results indicate the proposed techniques can improve the upper bound of the 95-percentile circuit delay, on average, by 9.2% and 4.8% across the ISCAS’85 benchmark circuits, compared to the worst-case timing analysis that uses only the interval information of the partially specified parameters. 1. Need for New Models of Uncertainty: Probabilistic Interval Analysis The area of statistical timing analysis (SSTA) has recently made substantial progress in terms of algorithmic and modeling advances. Efficient block-based and incremental computation techniques based on the first-order delay model are now well developed [1][2]. Extensions of the basic framework of SSTA to higher-order models have been recently investigated to capture non-linear effects and non-Gaussian process parameter distributions [3][4][5]. Statistical delay computation for interconnect based on affine interval arithmetic has been studied in [6]. These developments in the theory of SSTA came in response to the increased variability in the process parameters, the inadequacy of the corner models, and the need to use explicit probabilistic descriptions of key process parameters. The fundamental assumption behind all of the above techniques is that the probabilistic descriptions are readily available. In all the algorithms for SSTA [1-5], the complete knowledge about the distributions of process and environmental parameters is given, e.g. it is assumed that the process parameters are normally distributed, with the known mean and variance. Then, first-order models link delay variability with process parameters, allowing delay to be normally distributed as well [1][2]. If linear delay models are not sufficiently accurate, higher-order models can be used, at the cost of the resulting non-Gaussian distribution of delay. The nonGaussianality of process parameters or timing can be handled by numerical processing leading to a substantial (3-10X) increase in the run-time of the algorithm [4]. In this paper we argue that in a practical setting of cutting-edge IC design the full probabilistic information about parameter uncertainty is not available. The process characterization data is often incomplete and of limited nature, especially at the ramp-up phase of the industrial manufacturing. With limited number of measurements and characterization lots, there may be a large uncertainty in the statistic metrics (the mean and the variance) of the process parameters. Some sources of on-chip uncertainty cannot be described probabilistically: supply voltage (Vdd), temperature, and systematic variation sources with the unit of repeatability larger than a single chip (e.g. aberration-caused Lgate variation). Interval and affine methods, which tremendously improve on the conservatism of the traditional interval techniques, can be used [6]. However, in many instances, some but not full probabilistic information is available. For example, variation of supply voltage in time depends on the input vectors applied to the chip. Because of the difficulty of performing temporal input-dependent analysis, the uncertainty about supply voltage is most typically represented by the range information [7], however, the mean and, possibly, the variance of the distribution can be estimated more easily. For example, the supply voltage may vary between 90-100% of the nominal value, with the mean equal to 97% of the nominal value. The distribution is unknown because its characterization is too expensive [8]. Statistical STA cannot meaningfully handle such a realistic scenario. The affine methods are fundamentally nonprobabilistic and their extensions to handling statistics are heuristic in nature [6]. Thus, in addition to the existing techniques, a new way of treating uncertain variables with partial probabilistic information is needed to enable practical design under uncertainty. This paper develops a solution of timing analysis under uncertainty based on the principles of probabilistic interval models. These models have been developed over the last decade in the field of robust statistics, reliable computing, and computer science [9]. They are based on the generalization of classical random variables to variables described by families of distributions. Conceptually, the most general description of an uncertain variable is an interval, e.g. [ , ] x x x ∈ . Such descriptions form the basis of interval arithmetic and its enhancement in terms of affine arithmetic [10][11]. An interval description does not permit making statements about which values of the variable are more likely. Thus, if in addition to the range, the statistic metrics, such as mean and variance, are known the interval methods are incapable of utilizing this additional information in computing the arithmetic operations (+, -, *, /, max, min). Probabilistic interval analysis is a natural synergy of pure interval arithmetic and probabilistic analysis. It permits the use of partial statistic information (e.g. range, mean, and variance) to quantify the likelihood of the variable in the range. The estimates are guaranteed to be conservative regardless of the precise form of the distribution. For the fully specified random variable (e.g. Gaussian) the most general representation is its cumulative distribution function (cdf) [12]. For a partially-specified random variable, the most general representation is a set of cumulative distribution functions, which can be represented as bounds on the cdf, forming a so-called probability box. Following the above philosophy, this paper develops timing analysis techniques that produce reliable timing estimates even if the characterization data is incomplete. The essential contribution of this paper is in handling incomplete and imprecise uncertainty description. Compared to affine methods, the developed techniques can handle both the interval and probabilistic descriptions consistently and formally. The paper describes in detail how the probability boxes can be computed effectively. Importantly, the proposed techniques are compatible with the existing SSTA tools and can handle both full and partial probabilistic descriptions simultaneously. This paper is organized as follows. Section 2 describes the paradigm of modeling non-probabilistic uncertainty based on probabilistic interval analysis, which enables us to use partial statistic metrics for timing analysis. The computation of path delay due to Gaussian variables and probabilistic interval variables is derived. Besides, statistical techniques of robustly estimating circuit delay distribution are proposed. The experimental results are presented in Section 3. 2. Timing Analysis with Partial Probabilistic Information In this section, an application of the new probabilistic interval techniques to timing analysis is introduced. First, the construction of the path-delay probability box is described. Second, the bound of the circuit delay distribution is constructed. Finally, a method to combine the results of the traditional SSTA with the above derivations is described. 2.1 Path Delay Computation The timing model used in this work is based on the additive delay model containing both the uncertainty due to classical random variables and the newly introduced probabilistic interval variables. The probabilistic interval variables (as opposed to random variables) are variables for which only partial statistic metrics, mean and variance, are available in addition to the known range, or interval. The delay model can be expressed as: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cs.utep.edu/vladik/2006/tr06-05a.pdf |
| Alternate Webpage(s) | http://www.cs.utep.edu/vladik/2006/tr06-05a.pdf |
| Alternate Webpage(s) | https://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1132&context=cs_techrep&httpsredir=1&referer= |
| Alternate Webpage(s) | http://www.cs.trinity.edu/~mlewis/CSCI1321-S05/Lectures/Lect8.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
