In this paper, we propose a stratification+hybrid quasi Monte Carlo (SH-QMC) approach to improve the efficiency of Monte Carlo-based statistical static timing analysis (SSTA) using sample size reduction. Sample size reduction techniques proposed in the literature exhibit a tradeoff between accuracy of the Monte Carlo estimate with fewer samples and their ability to handle large number of variables in multidimensional space. This paper proposes to target several such techniques to different sets of process variation variables by using information about the importance of these variables to the circuit delay, and the capability of the techniques to handle multiple dimensions. Simulations on benchmark circuits up to 90 K gates show that the proposed method requires up to 224 samples for varying levels of process variation to achieve accurate timing estimates. Results also show that when SH-QMC is performed with multiple parallel threads on a quad-core processor, the approach is faster than traditional SSTA with comparable accuracy. When the proposed SH-QMC technique is supplemented with a graph pruning method the runtime is further reduced by 46-48% on average. The technique is also extended to include an incremental approach to recompute a percentile delay metric after engineering change order.

Gate oxide breakdown (OBD) is a key factor limiting the useful lifetime of an integrated circuit. Unfortunately, the conventional approach for full chip OBD reliability analysis assumes a uniform oxide thickness and worst-case temperature for all devices. In practice, however, gate oxide thickness varies from die-to-die and within-die and hence may cause different reliability for different devices even chips. Moreover, due to the increased across-die temperature variation, such difference may be exacerbated. Thus, as the precision of variation control worsens, an alternative reliability analysis approach is needed. In this paper, we propose a statistical framework for chip-level gate OBD reliability analysis while considering both die-to-die and within-die components of thickness variations as well as the across-die temperature variation. The thickness of each device is modeled as a distinct random variable and thus the full chip reliability estimation problem is defined on a huge sample space of several million devices. We observe that the chip-level OBD reliability function is independent of the relative location of the individual devices. This enables us to transform the problem such that the resulting representation can be expressed in terms of much fewer random variables. Using this transformation, we present a computationally efficient and accurate approach for estimating the full chip reliability while considering spatial correlations of gate oxide thickness as well as temperature variation. We show that, compared to Monte Carlo simulation, the proposed method incurs an error of only around 1% while improving the runtime by more than three orders of magnitude.

Modeling the effect of coupling-noise on circuit delay is a key issue in static timing analysis and involves thevictim-aggressor alignmentproblem. As delay-noise strongly depends on the skew between the victim-aggressor driver input transitions, it is not possiblea prioriidentify the victim-driver input transition that results in the worst-case delay-noise. Several approaches have been proposed in literature which heuristically search for the worst-case victim-aggressor alignment. This paper presents an analytical result that obviates the need to search for theoptimalvictim-driver input transition, thereby simplifying the victim-aggressor alignment problem significantly. Using the properties of standard nonlinear complementary metal-oxide semiconductor drivers, it is shown that for monotonic input transitions the worst-case victim-driver input transition is the one that switches at thelatestpoint in its timing window. Similarly, the victim-driver input alignment at the earliest point in the timing window is optimal for early-mode analysis. Although this result has been empirically observed in the industry, to the best of our knowledge this is the first paper which provides a rigorous analysis and shows that the above result holds for both linear and nonlinear drivers. It is also shown that the latest alignment of the victim-driver input transition results in the latest victimreceiver outputarrival time even for the cases where the victim is coupled tomultipleaggressors. Finally, experimental results show that limiting the alignment of the victim to only the latest victim-driver input transition can significantly reduce the runtime of existing approaches with no loss of accuracy.

SSTA has received a considerable amount of attention in recent years. However, it is a general rule that any approach can only be as accurate as the underlying models. Thus, variation models are an important research topic, in addition to the development of statistical timing tools. These models attempt to predict fluctuations in parameters like doping concentration, critical dimension (CD), and ILD thickness, as well as their spatial correlations. Modeling CD variation is a difficult problem because it contains a systematic component that is context dependent as well as a probabilistic component that is caused by exposure and defocus variation. Since these variations are dependent on topology, modern-day designs can potentially contain thousands of unique CD distributions. To capture all of the individual CD distributions within statistical timing, a transistor-specific model is required. However, statistical CD models used in industry today do not distinguish between transistors contained within different standard cell types (at the same location in a die), nor do they distinguish between transistors contained within the same standard cell. In this work we verify that the current methodology is error-prone using a 90 nm industrial library and lithography recipe (with industrial OPC) and propose a new SSTA delay model that on average reduces error of standard deviation from 11.8% to 4.1% when the total variation (sigma/mu) is 4.9% - a 2.9X reduction. Our model is compatible with existing SSTA techniques and can easily incorporate other sources of variation such as random dopant fluctuation and line-edge roughness.

Gate oxide breakdown is a key factor limiting the useful lifetime of an integrated circuit. Unfortunately, the conventional approach for full chip oxide reliability analysis assumes a uniform oxide-thickness for all devices. In practice, however, gate-oxide thickness varies from die-to-die and within-die and as the precision of process control worsens an alternative reliability analysis approach is needed. In this work, we propose a statistical framework for chip level gate oxide reliability analysis while considering both die-to-die and within-die components of thickness variation. The thickness of each device is modeled as a distinct random variable and thus the full chip reliability estimation problem is defined on a huge sample space of several million devices. We observe that the full chip oxide reliability is independent of the relative location of the individual devices. This enables us to transform the problem such that the resulting representation can be expressed in terms of only two distinct random variables. Using this transformation we present a computationally efficient and accurate approach for estimating the full chip reliability while considering spatial correlations of gateoxide thickness. We show that, compared to Monte Carlo simulation, the proposed method incurs an error of only 1∼6% while improving the runtime by around three orders.

Static-timing analysis (STA) has been one of the most pervasive and successful analysis engines in the design of digital circuits for the last 20 years. However, in recent years, the increased loss of predictability in semiconductor devices has raised concern over the ability of STA to effectively model statistical variations. This has resulted in extensive research in the so-called statistical STA (SSTA), which marks a significant departure from the traditional STA framework. In this paper, we review the recent developments in SSTA. We first discuss its underlying models and assumptions, then survey the major approaches, and close by discussing its remaining key challenges.

Increasing levels of process variation in current technologies have a major impact on power and performance and result in parametric yield loss. In this paper, we develop an efficient gate-level approach to accurately estimate and optimize the parametric yield, defined by leakage power and delay limits, by finding their joint probability distribution function. We consider inter-die variations, as well as intra-die variations, with correlated and random components. The correlation between power and performance arises due to their dependence on common process parameters and is shown to have a significant impact on the yield, particularly in high-frequency bins. We then propose a new heuristic approach to incrementally compute the gradient of yield with respect to gate sizing and gate-length biasing in the circuit with high efficiency and accuracy. We show how this gradient information can be effectively used by a nonlinear optimizer to perform yield optimization. The proposed yield-analysis approach is compared with Monte Carlo simulations and shows high accuracy, with the yield estimates achieving an average error of 2%. The proposed optimization approach is implemented and tested, and we demonstrate an average yield increase of 40% using gate sizing (as compared to a deterministically optimized circuit). Even higher improvements are demonstrated when both gate sizing and gate-length-biasing techniques are used.

We present, in this paper, novel algorithms to compute the set of "top-k" aggressors in a design. We show that the computation of the set of top-k aggressors is non-trivial, since we must consider all permutations of aggressors that are coupled to a critical path. Also, different sets of aggressors contribute different amounts of noise to each critical path and a brute-force enumeration to obtain the set of top-k aggressors has impractical runtime. Our proposed approach uses two key techniques to reduce the runtime complexity: Firstly, we model the delay noise propagated from a victim net to its fanout net by a so-called pseudo aggressor, which simplifies our problem formulation significantly. Secondly, we define a dominance property for aggressor sets, which imposes a partial ordering on the aggressor sets and allows us to efficiently prune the enumeration space. We then demonstrate the effectiveness of our proposed algorithm on benehmark circuits.

Modeling the effect of coupling noise on circuit delay is a key issue in static timing analysis (STA) and involves the “victimaggressor alignment” problem. As delay-noise depends strongly on the skew between the victim-aggressor input transitions’, it is not possible to apriori identify the victim input transition that results in the latest arrival time at the victim. Several approaches that heuristically search for the worst-case victim-aggressor alignment have been proposed in literature. In this paper we present an analytical result that obviates the need to search for the worst-case victim input transition, thereby simplifying the victim-aggressor alignment problem significantly. Using the properties of standard nonlinear CMOS drivers, we show that regardless of the switching of the aggressors, the worst-case victim input transition is the one that switches at the latest point in its timing window. Although this result has been empirically observed in the industry, to the best of our knowledge, this is the first work that provides a rigorous analysis and shows that the result holds for both linear and non-linear drivers. We also show that limiting the alignment of the victim to only the latest victim input transition can significantly reduce the runtime of existing heuristic techniques with no loss of accuracy.

Soft errors have emerged as an important reliability challenge for nanoscale very large scale integration designs. In this paper, we present a fast and efficient soft error rate (SER) analysis methodology for combinational circuits. We first present a novel parametric waveform model based on the Weibull function to represent particle strikes at individual nodes in the circuit. We then describe the construction of the descriptor object that efficiently captures the correlation between the transient waveforms and their associated rate distribution functions. The proposed algorithm consists of operations to inject, propagate, and merge these descriptors while traversing forward along the gates in a circuit. The parameterized waveforms enable an efficient static approach to calculate the SER of a circuit. We exercise the proposed approach on a wide variety of combinational circuits and observe that our algorithm has linear runtime with the size of the circuit. The runtimes for soft error estimation were observed to be in the order of about 1 s, compared to several minutes or even hours for previously proposed methods.

Soft errors have emerged as an important reliability challenge for nanoscale VLSI designs. In this paper, we present a fast and efficient soft error rate (SER) computation algorithm for combinational circuits. We first present a novel parametric waveform model based on the Weibull function to represent particle strikes at individual nodes in the circuit. We then describe the construction of the SET descriptor that efficiently captures the correlation between the transient waveforms and their associated rate distribution functions. The proposed algorithm consists of operations to inject, propagate and merge SET descriptors while traversing forward along the gates in a circuit. The parameterized waveforms enable an efficient static approach to calculate the SER of a circuit. We exercise the proposed approach on a wide variety of combinational circuits and observe that our algorithm has linear runtime with the size of the circuit. The runtimes for soft error estimation were observed to be in the order of about one second, compared to several minutes or even hours for previously proposed methods

Statistical static timing analysis (SSTA) is emerging as a solution for predicting the timing characteristics of digital circuits under process variability. For computing the statistical max of two arrival time probability distributions, existing analytical SSTA approaches use the results given by Clark in [8]. These analytical results are exact when the two operand arrival time distributions have jointly Gaussian distributions. Due to the nonlinear max operation, arrival time distributions are typically skewed. Furthermore, nonlinear dependence of gate delays and non-gaussian process parameters also make the arrival time distributions asymmetric. Therefore, for computing the max accurately, a new approach is required that accounts for the inherent skewness in arrival time distributions. In this work, we present analytical solution for computing the statistical max operation.1 First, the skewness in arrival time distribution is modeled by matching its first three moments to a so-called skewed normal distribution. Then by extending Clark's work to handle skewed normal distributions we derive analytical expressions for computing the moments of the max. We then show using initial simulations results that using a skewness based max operation has a significant potential to improve the accuracy of the statistical max operation in SSTA while retaining its computational efficiency.

Statistical static timing analysis (SSTA) has become a key method for analyzing the effect of process variation in aggressively scaled CMOS technologies. Much research has focused on the modeling of spatial correlation in SSTA. However, the vast majority of these works used artificially generated process data to test the proposed models. Hence, it is difficult to determine the actual effectiveness of these methods, the conditions under which they are necessary, and whether they lead to a significant increase in accuracy that warrants their increased runtime and complexity. In this paper, we study 5 different correlation models and their associated SSTA methods using 35420 critical dimension (CD) measurements that were extracted from 23 reticles on 5 wafers in a 130nm CMOS process. Based on the measured CD data, we analyze the correlation as a function of distance and generate 5 distinct correlation models, ranging from simple models which incorporate one or two variation components to more complex models that utilize principle component analysis and Quad-trees. We then study the accuracy of the different models and compare their SSTA results with the result of running STA directly on the extracted data. We also examine the trade-off between model accuracy and run time, as well as the impact of die size on model accuracy. We show that, especially for small dies (< 6.6mm x 5.7mm), the simple models provide comparable accuracy to that of the more complex ones, while incurring significantly less runtime and implementation difficulty. The results of this study demonstrate that correlation models for SSTA must be carefully tested on actual process data and must be used judiciously.

Static power consumption due to subthreshold, gate, and junction leakages has become a significant component of the total power consumption. For nanoscale circuits, leakage poses one of the most important challenges to the continuation of Moore's law. The leakage of a logic gate varies by an order of magnitude over its Boolean input space. Thus, one way to minimize leakage in a circuit during standby mode is to apply an input vector for which the leakage is at its minimum. Such a set of vectors is called the minimum leakage set (MLS). In this paper, an efficient algorithm for computing the exact MLS is presented. The approach is based on implicit enumeration using integer-valued decision diagrams. Since the search space for MLS is exponential in the number of primary inputs, the enumeration is done with respect to the minimum balanced cut of the digraph representation of the circuit. Next, the problem of the increased switching power, which results from driving all inputs to a given state when entering the standby mode, is addressed. For a given upper bound B on the leakage, the MLS algorithm is extended to identify the maximal input cube with the minimum switching cost from the set of minterms whose maximum leakage is lesB. The switching cost associated with an input is taken to be proportional to the load capacitance of that input. The algorithms have been successfully tested on the ISCAS85 and MCNC91 benchmark circuits

In this paper, we propose a new sensitivity based, statistical gate sizing method. Since circuit optimization effects the entire shape of the circuit delay distribution, it is difficult to capture the quality of a distribution with a single metric. Hence, we first introduce a new objective function that provides an effective measure for the quality of a delay distribution for both ASIC and high performance designs. We then propose an efficient and exact sensitivity based pruning algorithm based on a newly proposed theory of perturbation bounds. A heuristic approach for sensitivity computation which relies on efficient computation of statistical slack is then introduced. Finally, we show how the pruning and statistical slack based approaches can be combined to obtain nearly identical results compared with the brute-force approach but with an average run-time improvement of up to 89x. We also compare the optimization results against that of a deterministic optimizer and show an improvement up to 16% in the 99-percentile circuit delay and up to 31% in the standard deviation for the same circuit area.

Process variability greatly affects power and timing of nanometer scale CMOS circuits, leading to parametric yield loss due to both timing and power constraint violations. This parametric yield loss will continue to worsen in future technologies as a result of increasing process variations [1] and the increased importance of leakage power. Hence, statistical techniques are required to maximize parametric yield under given power and frequency constraints. Recently, much progress has been reported in the area of statistical modeling of leakage power [6] and circuit timing [2-5]. These techniques are useful in analyzing the impact of process variations on performance and power in nanometer CMOS designs. In this extended abstract, we outline the need for statistical optimization methods.

The increased dominance of intra-die process variations has motivated the field of statistical static timing analysis (SSTA) and has raised the need for SSTA-based circuit optimization. We propose a new sensitivity based, statistical gate sizing method. Since brute-force computation of the change in circuit delay distribution to gate size change is computationally expensive, we propose an efficient and exact pruning algorithm. The pruning algorithm is based on a novel theory of perturbation bounds which are shown to decrease as they propagate through the circuit. This allows pruning of gate sensitivities without complete propagation of their perturbations. We apply our proposed optimization algorithm to ISCAS benchmark circuits and demonstrate the accuracy and efficiency of the proposed method. Our results show an improvement of up to 10.5% in the 99-percentile circuit delay for the same circuit area, using the proposed statistical optimizer and a run time improvement of up to 56/spl times/ compared to the brute-force approach.

With the increased significance of leakage power and performance variability, the yield of a design is becoming constrained both by power and performance limits, thereby significantly complicating circuit optimization. In this paper, we propose a new optimization method for yield optimization under simultaneous leakage power and performance limits. The optimization approach uses a novel leakage power and performance analysis that is statistical in nature and considers the correlation between leakage power and performance to enable accurate computation of circuit yield under power and delay limits. We then propose a new heuristic approach to incrementally compute the gradient of yield with respect to gate sizes in the circuit with high efficiency and accuracy. We then show how this gradient information can be effectively used by a non-linear optimizer to perform yield optimization. We consider both inter-die and intra-die variations with correlated and random components. The proposed approach is implemented and tested and we demonstrate up to 40% yield improvement compared to a deterministically optimized circuit.

In a CMOS combinational logic circuit, the subthreshold leakage current in the standby state depends on the state of the inputs. In this paper we present a new approach to identify the minimum leakage set of input vectors (MLS). Applying a vector in the MLS is known as Input Vector Control (IVC), and has proven to be very useful in reducing gate oxide leakage and sub-threshold leakage in standby mode of operation. The approach presented here is based on Implicit Enumeration of integer-valued decision diagrams. Since the search space for minimum leakage vector increases exponentially with the number of primary inputs, the enumeration is done with respect to the minimum balanced cut of the digraph representation of the circuit. To reduce the switching power dissipated when the inputs are driven to a given state (during entry into and exit from the standby state), we extend the MLS algorithm to compute a bounded leakage set (BLS). Given a bound of standby leakage, we present an algorithm for computing minimal switching cost partial input vectors such that the leakage of the circuit is always less than the upper bound.

A distributed sensor network (DSN) designed to cover a given region R, is said to be alive if there is at least one subset of sensors that can collectively cover (sense) the region R. When no such subset exists, the network is said to be dead. A key challenge in the design of a DSN is to maximize the operational life of the network. Since sensors are typically powered by batteries, this requires maximizing the battery lifetime. One way to achieve this is to determine the optimal schedule for transitioning sets of sensors between active and inactive states while satisfying user specified performance constraints. This requires identification of feasible subsets (covers) of sensors and a scheme for switching between such subsets. We present an algorithmic solution to compute all the sensor covers in an implicit manner by formulating the problem as unate covering problem (UCP). The representation of all possible sensor sets is extremely efficient and can accommodate very large number of sensor covers. The representation and formulation makes it possible to consider the residual battery charge when switching between covers. We develop algorithms for switching between sensor covers aimed at maximizing the lifetime of the network. The algorithms take into account the transmission/reception costs of sensors, a user specified quality constraint and also utilize a novel battery model that accounts for the rate-dependent capacity effect and charge recovery during idle periods. Our simulation results show that lifetime improvement can be achieved by exploiting the charge recovery process. The work presented here constitutes a framework for battery aware sensor management in which various types of constraints can be incorporated and a range of other communication protocols can be examined.