Aggregate sensitivity for statistical static timing analysis

A system and a method are disclosed for circuit analysis. A circuit modeling system calculates sensitivities of gates for statistical static timing analysis of a circuit. Timing distribution sensitivities of gates and correlations between the sensitivities are determined. A Monte Carlo simulation is run using the sensitivities to determine timing distribution of paths and determine probabilities of paths being the critical path. Aggregate sensitivities for cells are also determined.

CROSS REFERENCE TO RELATED APPLICATIONS

This application is related to U.S. patent application Ser. No. 11/451,705, filed Jun. 12, 2006, and titled “Filtering Methods for Statistical Timing Analysis,” the contents of which are hereby incorporated by reference.

BACKGROUND

1. Field of Art

The present invention generally relates to the field of electronic design automation, and more specifically, to electronic design automation using statistical static timing analysis.

2. Description of the Related Art

Electronic design automation (EDA) is used extensively in the design of integrated circuits. An electronic circuit under design is evaluated using models of devices and interconnections between the devices. A simulation using these models is then run to test the performance of the circuit.

Statistical static timing analysis (SSTA) is a methodology of electronic design automation for verifying whether the circuit under design meets desired timing criteria using statistical properties of the propagation delays. The probability distributions of the delays increase the complexity and the numbers of calculations run for SSTA.

From the above, there is a need for a system and process to provide an EDA model that reduces the numbers of calculations that are run for the statistical static timing analysis.

SUMMARY

One embodiment of a disclosed system and method includes a method of determining timing characteristics of an electrical element. Sensitivity of the electrical element is determined. Criticality of paths to the electrical element is determined. An aggregate sensitivity of the electrical element is calculated. The aggregate sensitivity may be calculated by multiplying the element sensitivity and the sum of the criticalities of the paths.

DETAILED DESCRIPTION

Generally, the disclosed embodiments describe a system and method for analyzing timing characteristics of a circuit under design by calculating sensitivities of elements and applying statistical analysis for path selection.

FIG. 1is a block diagram illustrating an electronic design automation system100. A computer102executes a circuit analyzer104for generating device models for circuits stored in a device library108and for simulating the operation and performance of an electrical circuit under design. The computer102receives design information106, such as a net list, corresponding to the electrical circuit under design. The computer102retrieves corresponding models from the device library108, and executes a design simulation using the circuit analyzer104. The circuit analyzer104, the design information106, and, the device library108may reside in a memory internal or external to the computer102.

The circuit analyzer104generates a model for a cell indicative of the timing characteristics of the cell including sensitivity of the cell to process parameters for the design and manufacturing of a device embodying the circuit. The model typically includes probability distributions of timing of the cell for global and local variations. The local variations may include systematic variations and random variations.

FIG. 2is a block diagram illustrating the circuit analyzer104.

The circuit analyzer104comprises a statistical state timing analysis (SSTA) engine202that receives process variation data204provided from a foundry and representing the process parameters to be considered as statistical rather than deterministic to describe the process variations. Process variation can affect device parameters and interconnect dimensions, such as width, thickness, and interlayer dielectric thicknesses. The process variation data may be presented in the form of a Statistical Spice model. Process variations may be categorized as global and local: Global variations include die-to-die, wafer-to-wafer and lot-to-lot variations, while within-die variations are referred to as local variations. Additionally, for local variations, different parameters have different behavior. For example oxide thickness mostly has systematic variation, while the number of dopants may have random behavior. Both global and local (including systematic and random) variations are modeled and handled by the SSTA engine202.

The SSTA engine202uses gate modeling data206and interconnect modeling data208from the device library108. The data206and208include sensitivity information of design components (e.g., devices and interconnects) to process variations.

The SSTA engine202may perform the SSTA using a variety of well-known approaches including path based and block based approaches. For all the approaches, the SSTA engine202processes correlations, Gaussian distribution assumptions, statistical min/max operations, slew/capacitance variation effects and environmental variations as described herein.

The output of the SSTA engine202includes criticality and sensitivity data210, delay/slack probability density functions data212, and clock tree analysis data214for all design components (paths, nodes) and the circuit under design itself. The data210,212and214facilitates estimating the design parametric yield and enabling performance/yield trade-off during circuit design. Statistical analysis results can help tighten on-chip variation (OCV) margins used in deterministic analysis and optimization per design basis. The SSTA engine202evaluates the criticality of paths statistically or deterministically or both. The path criticality can be combined with delay sensitivity to help determine variability bottlenecks in designs and drive statistical optimization.

The SSTA engine202performs statistical static timing analysis that evaluates correlations and propagation of distribution under min/max operations. The delay/slack correlation may be due to correlation between process parameters, or due to path sharing in static timing analysis.

FIG. 3is a flow chart illustrating a first methodology for analyzing timing of a circuit.FIG. 4is a schematic diagram illustrating an exemplary circuit400under design used to illustrate the methodology ofFIG. 3. The circuit400is one example of a circuit under test and includes AND gates and OR gates, but other circuit elements may be used.

The circuit analyzer104calculates the sensitivity of the cells in the circuit (block302). The sensitivity may include systematic variations caused by inter-die variability, such as lot to lot variations with a fabrication facility, wafer to wafer variation with a lot, and die to die variation within a wafer. The sensitivity may include local variations caused by intra-die variability, such as device to device variation with a die. In one embodiment, the sensitivity includes the delay of the cell. The delay may be calculated as a nominal delay plus the sum of probability distributions of parameters causing global and local variations. For example, the circuit analyzer104generates a model of the sensitivity of a plurality of AND gates410,412,420,421,432,440and441, a plurality of OR gates411,422,430and431and a register409of the circuit400. The circuit analyzer104performs a static timing analysis of the circuit (block303). This analysis includes timing characteristic of signal paths in the circuit based on numerical delay times, minimum setup and maximum hold times to determine criticality of the path. The circuit analyzer104selects paths to a cell for analysis based on criticality of the paths (block304). The criticality of the path includes the probability distribution for negative slack, which indicates that the path does not have sufficient time for the circuit operation. For example, the circuit analyzer104selects paths401,402, and403to the register409. The first path401comprises the AND gates410and412and the OR gate411. The second path402comprises the AND gates420and421and the OR gate422. The third path403comprises the OR gates430and431and the AND gate432. A path404is a path of a clock signal and comprises the AND gates440and441.

The circuit analyzer104filters paths based on the probability distribution functions of the paths, such as shown inFIG. 3(block306).

FIG. 5is a graph illustrating delay distributions of elements of the circuit ofFIG. 4. The line502illustrates the probability distribution function of arrival time due to global variations. A line504illustrates the probability distribution function of arrival time due to local variations.

Referring again toFIG. 3, in one embodiment, the circuit analyzer104filters paths among the selected paths that do not affect a final slack distribution of the circuit. The filtering may include removing a path that has a probability distribution with a left three sigma point that is to the right of the right three sigma point of the probability distribution of another path, such as described below for removing a line1003of the path403inFIG. 10.

FIG. 10is a graph illustrating delay distributions of paths of the circuit300under design. Lines1001,1002, and1003represent probability distribution functions (PDF) of the paths, e.g., paths401,402, and403, respectively. Because the probability distribution functions represented by the line1001dominates the probability distribution functions represented by the line1003, the circuit analyzer104removes the path403represented by the line1003from further analysis of the timing. The circuit analyzer104determines timing of the filtered paths of the circuit under design (block306). The path402has a higher probability of slack time above a time T than the path401as shown by lines1002, and1001, respectively. The circuit analyzer104adjusts the timing analysis to include the probabilities of the different paths being the critical path based on the overlap of the probability functions.

Although three sigma points are described, other points of the probability functions may be used. In one embodiment, the “worst case point” of the probability function of the removed path is greater than the “best case point” of the probability function of one of the other paths to the same register. The worst and best case points of the probability functions may be based on threshold probabilities. The filtering of the paths includes using probability distributions of the timing of the path. The filtering of the paths from the selected paths may include removing from the timing analysis all filtered paths that are statistically dominated by any of the selected paths.

Referring again toFIG. 3, the circuit analyzer104may also remove paths based on correlations between paths such as described below in conjunction withFIGS. 6-9. The circuit analyzer104determines the statistical timing of the paths using the calculated sensitivities of the elements of the paths (block308). The circuit analyzer104typically runs a simulation, such as a Monte Carlo simulation, on the model of the circuit under test.

FIG. 6is a flow chart illustrating a second methodology for analyzing a circuit under test using path sensitivity.

The circuit analyzer104collects a predetermined number of the top nominally critical paths using nominal slack (block602) and builds path sensitivity signatures to form a vector a, which is a path sensitivity vector corresponding to systematic variations (block604). The circuit analyzer104builds a covariance matrix C for systematic process parameters (block606). The covariance matrix C may have non-zero off-diagonal elements. The circuit analyzer104performs Cholesky factorization of the covariance matrix C using
C=LLT(1)
to determine the matrix L, which is the Cholesky root of the covariance matrix C (block608). The matrix LTis the transpose of the Cholesky root L. The circuit analyzer104transforms the vector a of path sensitivity signatures to form a vector aTL using the Cholesky root matrix L for a normalization process using a Gaussian random variable N(0,1) of zero mean and unit variance (block610).

The circuit analyzer104generates a path sensitivity signature for purely random variations u in the paths for a vector form bTDu, in which b is a path sensitivity vector corresponding to random variations (block612). The matrix D is a diagonal covariance matrix corresponding to purely random variations, which are by definition independent of each other. In one embodiment, the matrix D has no non-zero off-diagonal elements. The vector u is a vector of N(0,1) variables. Using the transformed path sensitivity vector a and the path sensitivity signature, the circuit analyzer104determines a global path sensitivity signature for each path (block614). The global path sensitivity signature of path i is given by
aiTL+biTD  (2)

The circuit analyzer104performs a Monte-Carlo simulation on the paths by sampling the systematic and random variations to determine the maximum delay variation in each sample over all paths (block616). For each sample y and u, the circuit analyzer104computes the maximum global sensitivity using
max(aiTL+biTD)  (3)
where y=Lu and is a vector of systematic variations, and thus aTy=aTLu, and is the transpose of the a vector for the ith path. The vector aTy provides the change in delay of a path with respect to systematic variations. The vector a is transformed to the vector aTL. During the Monte Carlo simulation (block616), the vector u is sampled by drawing independent samples from the N(0,1) distribution.

FIG. 7is a flow chart illustrating a methodology for determining path sensitivity in the methodology ofFIG. 6.

For each process parameter, the circuit analyzer104divides the chip into grid buckets (block702) and assigns distinct random variables to each grid bucket (block703). For an N×N grid, there are N2random variables. The circuit analyzer104determines a covariance matrix (block704). Each process parameter grid of size N by N contributes an N2×N2block to the covariance matrix.

For each cell in a given path, the circuit analyzer104determines which grid buckets the cell falls into and builds a path sensitivity signature of the path with respect to the grid bucket random variables (block706). As the path is traced, the circuit analyzer104sums the sensitivities of different cells to the same random variables to build vector a, and sums the sensitivities with respect to random variations to build vector b. For random variations, grid bucket information need not be used. There is one random variable per cell for each process parameter.

The circuit analyzer104collects path sensitivity signatures for both systematic and random variations for a predetermined number of critical paths (e.g., the top X critical paths) and uses them for path filtering (block708). The circuit analyzer104performs SSTA filtering using the determined correlation coefficients.

FIG. 8is a diagram illustrating multiple grids on a die for the methodology ofFIG. 6.

Two grids A and B are over laid on the same die area. The bottom grid (grid A) corresponds to the effective length Leff. The top grid (grid B) corresponds to the oxide thickness Tox. Consider a cell located in a third grid bucket of grid A. A cell C is located in the third grid bucket of grid A and the tenth grid bucket of grid B. This cell is affected by a length variation given by L2and a thickness of oxide variation of T9. Then the delay of the cell is as follows:
dcell=sL(L2)+sT(T9)  (4)

In equation (4), sLis the sensitivity of the cell to Leffand sTis the sensitivity of the cell to Tox. A path that passes through many cells has a delay equation similar to the equation (4) outlined above for cells.

How to populate a covariance matrix inspired by Pelgrom's model is described. Pelgrom's model states that the mismatch between a parameter measured for two identical transistors separated by a distance D is given by

Consider two gates, one in grid bucket i of A, and the other in bucket j of A. Assume that the locations of the two gates can be taken to be the centers of the respective grid buckets in which they are located. Let Difdenote the distance between the centers of the grid buckets i and j. Then a Pelgrom-like equation for the mismatch in Leffvalues measured at the two gates can be written as

E⁡(Li⁢Lj)=σL2-0.5*(A2WL+S2⁢Dij2)(7)
Noting that Liand Ljare variations, so E(Li)=E(Lj)=0, and thus the covariance is

Cov⁡(Li,Lj)=E⁡(Li⁢Lj)-E⁡(Li)⁢E⁡(Lj)=E⁡(Li⁢Lj)(8)
Finally we show the covariance matrix format for the two parameters Leffand Toxwith grid sizes 2×2 and 4×4 respectively.

FIG. 9is a diagram illustrating a single covariance matrix for grids on a die for the methodology ofFIG. 6. The covariance coefficients determined from equation (8) form a covariance matrix with regions901and902. The first region901is a 4×4 covariance matrix for Leff. The second region902is a 16×16 matrix for Tox. An entry cijis the covariance between the i and j grid buckets for the Toxgrid.

FIG. 11is a flow chart illustrating a methodology for calculating aggregate sensitivity of a circuit element. The circuit analyzer104determines the sensitivity of a circuit element of a circuit under test (block1102). For example, the arc sensitivity Cimay be calculated by:

Ci=∂D∂Pi(9)
where D is the arc delay and Piis the ithprocess parameter. Process parameters typically include temperature, process, and voltage.

The circuit analyzer104determines path criticality for all paths of inputs to the circuit element (block1104). The circuit analyzer104calculates an aggregate sensitivity of the electrical element from the cell sensitivities, the standard deviation of process parameters and the paths criticalities (block1106). The aggregate sensitivity is the sum of the products of the arc sensitivities and the paths criticalities. For example, the aggregate sensitivity AGfor gate G is

AG=∑Nk=1⁢πk⁢γk(10)
where N is the number of paths through gate G, πkis the criticality of path k and the arc sensitivity γkof gate G for path k is calculated as:

γk=∑Mi=1⁢Ci2⁢σi2+2·∑Mi=1⁢∑Mj=i+1⁢ρij⁢Ci⁢Cj⁢σi⁢σj(11)
where M is the number of process parameters, Ciis the sensitivity of arc k to process parameter i (as defined in (9)), ρijis the correlation between parameter i and parameter j and σiis the standard deviation of process parameter i.

FIG. 12is an exemplary circuit illustrating the aggregate sensitivity ofFIG. 11.FIG. 13is a table illustrating statistical timing of the exemplary circuit ofFIG. 12.FIG. 14is a table illustrating aggregate sensitivity for the exemplary circuit ofFIG. 12.

Both criticality and sensitivity are taken into account when performing statistical optimization. One goal of statistical optimization is to improve the probability that the overall circuit slack is positive.FIGS. 12-14provide simple example to show how the notion of criticality and sensitivity are combined into an aggregate sensitivity to be used to drive the statistical optimization.

An arc is defined as one circuit path through a cell. For a given arc, equation (11) defines the aggregate sensitivity. If an arc belongs to more than one path, the criticality is properly added for all the paths as defined in equation (10).

If a path/gate has a large spread, namely a large sensitivity, the path/gate does not need to be optimized for robustness if it is not a critical path or gate. On the contrary, if a gate has a small sensitivity but it belongs to a large number of critical paths, then optimization is performed on the gate. The aggregate sensitivity provides both the information for criticality and sensitivity and is used to drive optimization.

FIG. 13reports the statistical timing report for the circuit illustrated inFIG. 9. The values annotated inside each gate are the delay D and the sensitivity S, respectively, for that gate. Note that the path from i3 to output o has the largest standard deviation (and sensitivity) among all the paths, but its criticality measure is zero.

Given this information, the aggregate sensitivity metric can be calculated for each gate in the circuit according to Equation 11. The values for the circuit inFIG. 13are shown inFIG. 14. Traditionally, gates would be listed for optimization according to their worst negative slack. With the new metrics available from the SSTA engine202, gates can be analyzed according to their aggregate sensitivity value. Cells with a high aggregate sensitivity may have a higher priority for optimization. For the example ofFIG. 12, the cell G4is optimized first because all of the critical paths in the design pass through that cell have a non-negligible sensitivity.

The system and method described herein provide circuit modeling and simulation that eliminates dominated paths and handles correlated paths.

Upon reading this disclosure, those of skill in the art will appreciate still additional alternative structural and functional designs for a system and a process for determining sensitivities of cells and gates and determining critical paths in circuits through the disclosed principles herein. Thus, while particular embodiments and applications have been illustrated and described, it is to be understood that the present invention is not limited to the precise construction and components disclosed herein and that various modifications, changes and variations which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method and apparatus of the present invention disclosed herein without departing from the spirit and scope of the invention as defined in the appended claims.