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.

This paper describes a waveform compression technique suitable for the efficient utilization, storage and interchange of the emerging current source model (CSM) based cell libraries. The technique is based on pre-processing of a collection of voltage/current waveforms for the cells in the library and then, constructing an orthogonal time-voltage/time-current waveform basis using singular-value decomposition. Compression is achieved by representing all waveforms as linear combination coefficients of adaptive subset of the basis waveforms. Experimental results indicate that adaptive waveform representation results in higher compression ratios than the waveform representation as a function of fixed set of basis functions. Interpolation and further compression are obtained by representing the coefficients as simple functions of various parameters, e.g., input slew, load capacitance, supply voltage, and temperature. The methods introduced in this paper are tested and validated on several industrial strength libraries, with spectacular compression results.

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.

Timing, noise, and power analysis have historically relied on high level, black-box, non-physical logic library models. Moreover, these models were of a look-up type, i.e. precharacterized for practically all the possible environments in which they would be eventually used. The evolution of the VLSI technology towards nanometer sized features made this characterization methodology impractical. Increasingly, the space of all possible environments grew too rich to be fully covered during characterization. In the past decade, the so-called effective capacitance was introduced to provide some analysis capability to gate models, i.e., the ability to evaluate in the presence of RC loads, although characterized with capacitive loads only. In current and future VLSI technologies, such simple extensions no longer provide the required accuracy. Increasingly, models of logic gates must retain elements of the electrical behavior of the circuit in order to provide accurate timing, noise, and power information. This poses a new challenge on the analysis algorithms, now required to handle an enhanced level of detail in modeling without significantly degrading the overall efficiency of the application.

This paper introduces an accurate and efficient electrical analysis of logic gates modeled as Multiple Voltage Threshold Models (MVTM) loaded by the associated interconnect. MVTMs formalize a class of gate models which include the existing industry standards, such as CCS and ECSM driver models as special cases. The analysis technique relies on primary MVTM characterization data and does not require explicit instantiation of controlled current source models. Therefore, the method is more accurate, efficient, and general than traditional transient analysis. The theoretical results are validated by detailed simulations and use within full chip timing analysis.

In this paper, we consider the problem of selecting a set of aggressor nets that maximize crosstalk induced noise or delay pushout on a coupled victim net, under given logical constraints. We formulate the problem mathematically, and propose efficient Lagrangian Relaxation and network flow based approaches that guarantee an optimal solution. We also formulate and solve this problem while considering the noise susceptibility of the victimpsilas receiving gate. Experimental results show that the proposed approaches are run-time efficient by factors of up to 800times in comparison to an exhaustive search approach, and reduce timing pessimism by up to 36%.

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.

As technology scales down, timing verification of digital integrated circuits becomes an extremely difficult task due to the gate and wire variability. Therefore, statistical timing analysis (denoted by sigmaTA) is becoming unavoidable. In this paper, two new approaches for doing variational gate TA for Gaussian and non-Gaussian sources of variation in parameterized sigmaTA are presented. To start, a variational RC-pi load is approximated by using a canonical first-order model. Next, an accurate variational gate TA (VGTA) technique, which accounts for variational RC-pi loads, variational input transitions, and a variation-aware gate library, is introduced. The proposed method relies on static effective-capacitance-calculation method and its variational form. Experimental results demonstrate that VGTA exhibits an average error of 4% for gate delay and output transition time with respect to the Monte Carlo simulation with 104samples. Next, a more efficient VGTA [called Fast VGTA (F-VGTA)] based on a single-iteration variational effective capacitance calculation is presented. Experimental results show that F-VGTA achieves an average error of 7% for gate delay and output transition time with respect to the Monte Carlo simulation with 104samples but with runtimes that are about two times faster than VGTA.

As technology scales down, timing verification of digital integrated circuits becomes an increasingly challenging task due to the gate and wire variability. Therefore, statistical timing analysis (denoted by sigmaTA) is becoming unavoidable. This paper introduces a new framework for performing statistical gate timing analysis for non-Gaussian sources of variation in block-based sigmaTA. First, an approach is described to approximate a variational RC-pi load by using a canonical first-order model. Next, an accurate variation-aware gate timing analysis based on statistical input transition, statistical gate timing library, and statistical RC-pi load is presented. Finally, to achieve the aforementioned objective, a statistical effective capacitance calculation method is presented. Experimental results show an average error of 6% for gate delay and output transition time with respect to the Monte Carlo simulation with 104samples while the runtime is nearly two orders of magnitude shorter

This paper focuses on statistical interconnect timing analysis in a parameterized block-based statistical static timing analysis tool. In particular, a framework for performing timing analysis of RLC networks with step inputs, under both Gaussian and non-Gaussian sources of variation, is presented. In this framework, resistance, inductance, and capacitance of the RLC line are modeled in a canonical first order form and used to produce the corresponding propagation delay and slew (time) in the canonical first-order form. To accomplish this step, mean, variance, and skewness of delay and slew distributions are obtained in an efficient, yet accurate, manner. The proposed framework can be extended to consider higher order terms of the various sources of variation. Experimental results show average errors of less than 2% for the mean, variance and skewness of interconnect delay and slew while achieving orders of magnitude speedup with respect to a Monte Carlo simulation with 104samples

Process technology and environment-induced variability of gates and wires in VLSI circuits make timing analyses of such circuits a challenging task. Process variation can have a significant impact on both device (front-end of the line) and interconnect (back-end of the line) performance. Statistical static timing analysis techniques are being developed to tackle this important problem. Existing timing analysis tools divide the analysis into interconnect (wire) timing analysis and gate timing analysis. In this paper, we focus on statistical static timing analysis of coupled interconnects where crosstalk noise analysis is unavoidable. We propose a new framework for handling the effect of Gaussian and Non-Gaussian process variations on coupled interconnects. The technique allows for closed-form computation of interconnect delay probability density functions (PDFs) given variations in relevant process parameters such as the line width, metal thickness, and dielectric thickness in the presence of crosstalk noise. To achieve this goal, we express the electrical parameters of the coupled interconnects in a first order (linear) form as function of changes in physical parameters and subsequently use these forms to perform accurate timing and noise analysis to produce the propagation delay and slew in the first-order forms. This work can be easily extended to consider the effect of higher order terms of the sources of variation. Experimental results show that the proposed method is capable of accurately predicting delay variation in a coupled interconnect line.

Static timing analysis is a key step in the physical design optimization of VLSI designs. The lumped capacitance model for gate delay and the Elmore model for wire delay have been shown to be inadequate for wire-dominated designs. Using the effective capacitance model for the gate delay calculation and model-order reduction techniques for wire delay calculation is prohibitively expensive. In this paper, we present sufficiently accurate and highly efficient filtering algorithms for interconnect timing as well as gate timing analysis. The key idea is to partition the circuit into low and high complexity circuits, whereby low complexity circuits are handled with efficient algorithms such as total capacitance algorithm for gate delay and the Elmore metric for wire delay and high complexity circuits are handled with sign-off algorithms. Experimental results on microprocessor designs show accuracies that are quite comparable with sign-off delay calculators with more than of 65% reduction in the computation times

As technology scales down, timing verification of digital integrated circuits becomes an extremely difficult task due to statistical variations in the gate and wire delays. Statistical timing analysis techniques are being developed to tackle this important problem. In this paper, we propose a new framework for handling variation-aware interconnect timing analysis in which the sources of variation may have symmetric or skewed distributions. To achieve this goal, we express the resistance and capacitance of a line in canonical first order forms and then use these to compute the circuit moments. The variational moments are subsequently used to compute the interconnect delay and slew at each node of an RC tree. For this step, we combine known closed-form delay metrics such as Elmore and AWE-based algorithms to take advantage of the efficiency of the first category and the accuracy of the second. Experimental results show an average error of 2% for interconnect delay and slew with respect to SPICE-based Monte Carlo simulations.

As technology scales down, timing verification of digital integrated circuits becomes an extremely difficult task due to gate and wire variability. Therefore, statistical timing analysis is inevitable. Most timing tools divide the analysis into two parts: 1) interconnect (wire) timing analysis and 2) gate timing analysis. Variational interconnect delay calculation for block-based /spl sigma/TA has been recently studied. However, variational gate delay calculation has remained unexplored. In this paper, we propose a new framework to handle the variation-aware gate timing analysis in block-based /spl sigma/TA. First, we present an approach to approximate variational RC-/spl pi/ load by using a canonical first-order model. Next, an efficient variation-aware effective capacitance calculation based on statistical input transition, statistical gate timing library, and statistical RC-/spl pi/ load is presented. In this step, we use a single-iteration C/sub eff/ calculation which is efficient and reasonably accurate. Finally we calculate the statistical gate delay and output slew based on the aforementioned model. Experimental results show an average error of 7% for gate delay and output slew with respect to the HSPICE Monte Carlo simulation while the runtime is about 145 times faster.

This paper describes an efficient threshold-based filtering algorithm (TFA) for calculating the interconnect delay and slew (transition time) in high-speed VLSI circuits. The key idea is to divide the circuit nets into three groups of low, medium and high complexity nets, whereby for low and medium complexity nets either the first moment of the impulse response or the first and second moments are used. For the high-complexity nets, which are encountered infrequently, TFA resorts to the AWE method. The key contribution of the paper is to come up with very effective and efficient way of classifying the nets into these three groups. Experimental results show that on a large industrial circuit using a state-of-the-art commercial timing analysis that incorporates TFA, we were able to achieve delay and slew estimation accuracies that are quite comparable with the full-blown AWE-based calculators at runtimes that were only 14% higher than those of a simple Elmore-delay calculator.

In this paper, we present a new technique for calculating an effective capacitance of an RC interconnect line in very deep submicron design technologies. The calculation scheme guarantees that the effective capacitance model simultaneously matches both the 50% propagation delay and the 0-to-0.8Vdd output transition behavior of a standard cell driving an RC interconnect. Experimental results show that the new technique exhibits high accuracy (less than 5% error) and high efficiency (converges in two or at most three iterations). The paper also includes extensions to handle complex cells as drivers of the RC interconnect.

This paper first presents an accurate and efficient method of estimating the short circuit energy dissipation and the output transition time of CMOS buffers. Next, the paper describes a sizing method for tapered buffer chains. It is shown that the first-order sizing behavior, which considers only the capacitive energy dissipation, can be improved by considering the short-circuit dissipation as well, and that the second-order polynomial expressions for short-circuit energy improves the accuracy over linear expressions. These results are used to derive sizing rules for buffered chains, which optimize the overall energy-delay product.