Statistical static timing analysis (SSTA) involves computation of maximum (max) and minimum (min) of Gaussian random variables. Typically, the max or min of a set of Gaussians is performed iteratively in a pair-wise fashion, wherein the result of each pair-wise max or min operation is approximated to a Gaussian by matching moments of the true result obtained using Clark's approach [1]. The approximation error in the final result is thus a function of the order in which the pair-wise operations are performed.

Although order statistics have been studied for several decades, most of the results are based on the assumption of independent and identically distributed (i.i.d.) random variables. In the literature, how to compute the m th order statistics of n correlated random variables is still a problem. This article proposes a recursive algorithm based on statistical min/max operations to compute order statistics for general correlated and not necessarily identically distributed random variables. The algorithm has an O( mn ) time complexity and O( m + n ) space complexity. A binary tree-based data structure is further developed to allow selective update of the order statistics with O( nm 2 ) time. As a vehicle to demonstrate the algorithm, we apply it to the path selection algorithm in at-speed testing. A novel metric multilayer process space coverage metric is proposed to quantitatively gauge the quality of path selection. We then show that such a metric is directly linked to the order statistics, and our recursive algorithm can thus be applied. By employing a branch-and-bound path selection algorithm with these techniques, this article shows that selecting an optimal set of paths for a multimillion-gate design can be performed efficiently. Compared to the state of the art, experimental results show both the efficiency of our algorithms and better quality of our path selection.

The increasing significance of variability in modern sub-micron manufacturing process has led to the development and use of statistical techniques for chip timing analysis and optimization. Statistical timing involves fundamental operations like statistical-add, sub, max and min to propagate timing information (modeled as random variables with known probability distributions) through a timing graph model of a chip design. Although incremental timing during optimization updates timing information of only certain parts of the timing-graph, lack of established reversible statistical max or min techniques forces more-than-required computations.

Statistical static timing analysis (SSTA) is ideal for random variations but is not suitable for environmental variations like Vdd and temperature. SSTA uses statistical approximation, according to which circuit timing is predicted accurately only for highly probable combinations of variational parameters. SSTA is not able to handle accurately deterministic sources of variation like supply voltage. This paper presents a novel technique for modeling nonseparable deterministic and statistical variations in single timing run.

To enable statistical static timing analysis, for each cell in a digital library, a timing model that considers variations must be characterized. In this paper, we propose a dynamic method to accurately and efficiently characterize a cell's delay and output slew as a function of random mismatch variations. Based on a tight error bound for characterization using partial devices, our method sequentially performs simulations based on decreasing importance of devices and stops when the error requirement is met. Results on an industrial 32nm library demonstrate that the proposed method achieves significantly better accuracy-efficiency trade-off compared to other partial finite differencing approaches.

Process variation continues to increase with new technologies. With the advent of statistical static timing analysis (SSTA), multiple independent sources of variation can be modeled. This paper proposes a novel technique to reduce variability of metal process variation in SSTA. This novel method maximizes sensitivity cancellation to minimize variability. The developed methodology is simulated with SSTA in 65-nm technology and shows a reduction in variability.

Transistor sizing is a classic Computer-Aided Design problem that has received much attention in the literature. Due to the increasing importance of process variations in deep sub-micron circuits, nominal circuit tuning is not sufficient, and the sizing problem warrants revisiting. This paper addresses the sizing problem statistically in which transistor sizes are automatically adjusted to maximize parametric yield at a given timing performance, or maximize performance at a required parametric yield. Specifically, we describe an implementation of a statistical tuner using interior point nonlinear optimization with an objective function that is directly dependent on statistical process variation. Our results show that for process variation sensitive circuits, consisting of thousands of independently tunable devices, a statistically aware tuner can give more robust, higher yield solutions when compared to deterministic circuit tuning and is thus an attractive alternative to the Monte Carlo methods that are typically used to size devices in such circuits. To the best of our knowledge, this is the first publication of a working system to optimize device sizes in custom circuits using a process variation aware tuner.

Process variations make at-speed testing significantly more difficult. They cause subtle delay changes that are distributed in contrast to the localized nature of a traditional fault model. Due to parametric variations, different paths can be critical in different parts of the process space, and the union of such paths must be tested to obtain good process space coverage. This paper proposes an integrated at-speed structural testing methodology, and develops a novel branch-and-bound algorithm that elegantly and efficiently solves the hitherto open problem of statistical path tracing. The resulting paths are used for at-speed structural testing. A new test quality metric is proposed, and paths which maximize this metric are selected. After chip timing has been performed, the path selection procedure is extremely efficient. Path selection for a multimillion gate chip design can be completed in a matter of seconds.

Abstract---Static timing analysis of VLSI circuits relies on tabular models of logic gates obtained during library characterization. At characterization time logic gates are simulated at the circuit level with a range of input waveforms (e.g., saturated ramps with different slews) and various output loads. At timing analysis time the same gates are driven by input waveforms that differ from the class of characterization waveforms. This paper proposes a method for mapping the waveforms that arise in static timing analysis to members of the class of waveforms used to characterize gate timing performance during library characterization. The method is based on the moments of the input waveform, which describe concisely the salient features of the waveform. The mapping between the input waveform and the effective characterization waveform is accomplished by positing functional relationships between the input waveform’s moments and the parameters of the characterization waveform. The unknown coefficients of this functional relationship are determined by minimizing the worst case error of the output waveform over a representative set of input waveforms and gate loads. The technique requires no change to the library characterization procedure, and minimal change to the static timing tool with little to no additional computational burden on the timer.

Increasingly large process variations make selection of a set of critical paths for at-speed testing essential yet challenging. This paper proposes a novel multilayer process space coverage metric to quantitatively gauge the quality of path selection. To overcome the exponential complexity in computing such a metric, this paper reveals its relationship to a concept called order statistics for a set of correlated random variables, efficient computation of which is a hitherto open problem in the literature. This paper then develops an elegant recursive algorithm to compute the order statistics (or the metric) in provable linear time and space. With a novel data structure, the order statistics can also be incrementally updated. By employing a branch-and-bound path selection algorithm with above techniques, this paper shows that selecting an optimal set of paths for a multi-million-gate design can be performed efficiently. Compared to the state-of-the-art, experimental results show both the efficiency of our algorithms and better quality of our path selection.

Correct ordering of timing quantities is essential for both timing analysis and design optimization in the presence of process variation, because timing quantities are no longer a deterministic value, but a distribution. This paper proposes a novel metric, called tiered criticalities, which guarantees to provide a unique order for a set of correlated timing quantities while properly taking into account full process space coverage. Efficient algorithms are developed to compute this metric, and its effectiveness on path ranking for at-speed testing is also demonstrated.

Path delay testing is becoming increasingly important for high-performance chip testing in the presence of process variation. To guarantee full process space coverage, the ensemble of critical paths of all chips irrespective of their manufacturing process conditions needs to be tested, as different chips may have different critical paths. Existing coverage-based path selection techniques, however, suffer from the loss of coverage after ATPG (automatic test pattern generation), i.e., although the pre-ATPG path selection achieves good coverage, after ATPG, the coverage can be severely reduced as many paths turn out to be unsensitizable. This paper presents a novel path selection algorithm that, without running ATPG, selects a set of n paths to achieve near optimal post-ATPG coverage. Details of the algorithm and its optimality conditions are discussed. Experimental results show that, compared to the state-of-the-art, the proposed algorithm achieves not only superior post-ATPG coverage, but also significant runtime speedup.

Process variation is recognized as a major source of parametric yield loss, which occurs because a fraction of manufactured chips do not satisfy timing or power constraints. On the other hand, both chip performance and chip leakage power depend on supply voltage. This dependence can be used for converting the fraction of too slow or too leaky chips into good ones by adjusting their supply voltage. This technique is called voltage binning [4]. All the manufactured chips are divided into groups (bins) and each group is assigned its individual supply voltage. This paper proposes a statistical technique of yield computation for different voltage binning schemes using results of statistical timing and variational power analysis. The paper formulates and solves the problem of computing optimal supply voltages for a given binning scheme.

Summary form only given, as follows. The complete presentation was not made available for publication as part of the conference proceedings. Process variations complicate at-speed testing enormously. Different paths have different sensitivity signatures, and therefore each chip can potentially have a different critical path depending on the manufacturing parameters of that chip. This presentation will discuss how process variations can systematically be covered by exploiting statistical timing to select paths for at-speed structural test. Simultaneous coverage of process variations and satisfaction of sensitization conditions will be discussed. Due to increasing process variability in modern technologies, selection of optimal test margins is important to reduce pessimism while ensuring quality of shipped chips. Use of binning techniques to increase yield in the face of wide process variations is becoming more prevalent. Timing closure, margining and testing for binned chips can also take advantage of statistical timing to improve yield and quality.

In this paper, we consider the problem of identifying a feasible set of aggressor nets that would induce maximum crosstalk noise or delay pushout on a coupled victim net, under given logical constraints. We present a novel mathematical formulation of this problem and propose a Lagrangian relaxation-based approach for solving it efficiently and optimally. Experimental results show that the proposed approach is run-time efficient by a factor of up to 800 times in comparison to an exhaustive search approach and reduces timing pessimism by up to 36%. We also formulate and solve this problem while considering the noise susceptibility of the victim's receiving gate.

In the face of increased process variations, at-speed manufacturing test is necessary to detect subtle delay defects. This procedure necessarily tests chips at a slightly higher speed than the target frequency required in the field. The additional performance required on the tester is calledtestmargin. There are many good reasons for margin, including voltage and temperature requirements, incomplete test coverage, aging effects, coupling effects, and accounting for modeling inaccuracies. By taking advantage of statistical timing, this paper proposes an optimal method of test margin determination to maximize yield while staying within a prescribed shipped product quality loss limit. If process information is available from the wafer testing of scribe-line structures or on-chip process monitoring circuitry, this information can be leveraged to determine aper-chiptestmarginwhich can further improve yield.

Existing static timing methodologies apply various techniques to address increasingly larger process variations. The techniques include multi-corner timing, on-chip variation (OCV) derating coefficients, and path-based common path pessimism removal (CPPR) procedures. These techniques, however, destroy the benefits of linear run-time and incrementality possessed by classical static timing. The major contribution of this work is an efficient statistical timing methodology with comprehensive modeling of process variations, while at the same time retaining those key benefits. Our methodology is compatible with existing characterization methods and scales well to large chip designs. To achieve this goal, three techniques are developed: (1) building the statistical delay model based on existing multi-corner library characterization; (2) modeling spatial correlation in a scalable manner; and (3) avoiding the time-consuming CPPR procedure by removing common path pessimism in the clock network by an incremental block-based technique. Experimental results on industrial 90 nm ASIC designs show that the proposed timing methodology correctly handles all types of process variation, achieves high correlation with traditional multi-corner timing with more than 4 × speedup, and is a vehicle for pessimism reduction.

Criticality and yield gradients are two crucial diagnostic metrics obtained from statistical static timing analysis (SSTA). They provide valuable information to guide timing optimization and timing- driven physical synthesis. Existing work in the literature, however, computes both metrics in a non-incremental manner, i.e., after one or more changes are made in a previously-timed circuit, both metrics need to be recomputed from scratch, which is obviously undesirable for optimizing large circuits. The major contribution of this paper is to propose two novel techniques to compute both criticality and yield gradients efficiently and incrementally. In addition, while node and edge criticalities are addressed in the literature, this paper for the first time describes a technique to compute path criticalities. To further improve algorithmic efficiency, this paper also proposes a novel technique to update "chip slack" incrementally. Numerical results show our methods to be over two orders of magnitude faster than previous work.

In the face of increased process variations, at-speed manufacturing test is necessary to detect subtle delay defects. This procedure necessarily tests chips at a slightly higher speed than the target frequency required in the field. The additional performance required on the tester is called test margin. There are many good reasons for margin including voltage and temperature requirements, incomplete test coverage, aging effects, coupling effects and accounting for modeling inaccuracies. By taking advantage of statistical timing, this paper proposes an optimal method of test margin determination to maximize yield while staying within a prescribed shipped product quality loss (SPQL) limit. If process information is available from wafer testing of scribe line structures or on-chip process monitoring circuitry, this information can be leveraged to determine a per- chip test margin which can further improve yield.

Process variations make at-speed testing significantly more difficult. They cause subtle delay changes that are distributed rather than the localized nature of a traditional fault model. Due to parametric variations, different paths can be critical in different parts of the process space, and the union of such paths must be tested to obtain good process space coverage. This paper proposes a novel branch-and-bound algorithm that elegantly and efficiently solves the hitherto open problem of statistical path tracing. The resulting paths are used for at-speed structural testing. A new Test Quality Metric (TQM) is proposed and paths which maximize this metric are selected. After chip timing has been performed, the path selection procedure is extremely efficient. Path selection for a multi-million gate chip design can be completed in a matter of seconds.

Meeting the tight performance specifications mandated by the customer is critical for contract manufactured ASICs. To address this, at speed test has been employed to detect subtle delay failures in manufacturing. However, the increasing process spread in advanced nanometer ASICs poses considerable challenges to predicting hardware performance from timing models. Performance verification in the pres- ence of process variation is difficult because the critical path is no longer unique. Different paths become frequency limiting in different process corners. In this paper, we present a novel variation-aware method based on statistical timing to select critical paths for structural test. Node criticalities are computed to determine the probabilities of different circuit nodes being on the critical path across process variation.Moreover, path delays are projected into different process corners using their linear delay function forms. Experimental results for three multimillion gate ASICs demonstrate the effectiveness of our methods.

In ultra-deep sub-micron technologies, modeling waveform shapes correctly is essential for accurate timing and noise analysis. Due to process and environmental variations, there is a need for a variational waveform model that is compact, efficient and accurate. The mode) should capture correlations due to common dependence on process parameters. This paper proposes a waveform model derived from basic transformations of a nominal waveform in the absence of variations. The transformations are parameterized by variational quantities that capture the sensitivity of the waveform to process parameters. The resulting waveform model works well with current-source models for static timing analysis. Numerical results are presented to demonstrate the accuracy of the model both in capturing variational waveforms and in propagating waveforms through logic gates.

Statistics will provide the answer to our fear over the increasing uncertainty in chip performance. Our "confidence" in the correct operation of our integrated circuits will take on a new probabilistic meaning. This presentation will make the case for statistical optimization of integrated circuits in order to ensure high performance, yield and robustness. Today's discrete and continuous optimization techniques are not up to the task. New metrics will be required to allow physical synthesis tools to target these new optimization criteria. This presentation will describe the form that such metrics will take, and predict a phased introduction of statistical criteria in the optimization and automated fix-up process.

Chips manufactured in 90 nm technology have shown large parametric variations, and a worsening trend is predicted. These parametric variations make circuit optimization difficult since different paths are frequency-limiting in different parts of the multi-dimensional process space. Therefore, it is desirable to have a new diagnostic metric for robust circuit optimization. This paper presents a novel algorithm to compute the criticality probability of every edge in the timing graph of a design with linear complexity in the circuit size. Using industrial benchmarks, we verify the correctness of our criticality computation via Monte Carlo simulation. We also show that for large industrial designs with 442,000 gates, our algorithm computes all edge criticalities in less than 160 seconds.

Variability of process parameters makes prediction of digital circuit timing characteristics an important and challenging problem in modern chip design. Recently, statistical static timing analysis (statistical STA) has been proposed as a solution. Unfortunately, the existing approaches either do not consider explicit gate delay dependence on process parameters [3] - [6] or restrict analysis to linear Gaussian parameters only [1, [2]. Here we extend the capabilities of parameterized block-based statistical STA [1] to handle nonlinear function of delays and non-Gaussian parameters, while retaining maximum efficiency of processing linear Gaussian parameters. Our novel technique improves accuracy in predicting circuit timing characteristics and retains such benefits of parameterized block-based statistical STA as an incremental mode of operation, computation of criticality probabilities and sensitivities to process parameter variations. We implemented our technique in an industrial statistical timing analysis tool. Our experiments with large digital blocks showed both efficiency and accuracy of the proposed technique.

As technology scales into the sub-90 nm domain, manufacturing variations become an increasingly significant portion of circuit delay. As a result, delays must be modeled as statistical distributions during both analysis and optimization. This paper uses incremental, parametric statistical static timing analysis (SSTA) to perform gate sizing with a required yield target. Both correlated and uncorrelated process parameters are considered by using a first-order linear delay model with fitted process sensitivities. The fitted sensitivities are verified to be accurate with circuit simulations. Statistical information in the form of criticality probabilities are used to actively guide the optimization process which reduces run-time and improves area and performance. The gate sizing results show a significant improvement in worst slack at 99.86% yield over deterministic optimization.

In the way they cope with variability, present-day methodologies are onerous, pessimistic and risky, all at the same time! Dealing with variability is an increasingly important aspect of high-performance digital integrated circuit design, and indispensable for first-time-right hardware and cutting-edge performance. This invited paper discusses the methodology, analysis, synthesis and modeling aspects of this problem. These aspects of the problem are compared and contrasted in the ASIC and custom (microprocessor) domains. This paper pays particular attention to statistical timing analysis and enumerates desirable attributes that would render such an analysis capability practical and accurate.