**ABSTRACT**

Many recent techniques for timing analysis under variability, in

which delay is an explicit function of underlying parameters, may

be described as parameterized timing analysis. The“max” operator,

used repeatedly during block-based timing analysis, causes

several complications during parameterized timing analysis. We

introduce bounds on, and an approximation to, the max operator

which allow us to develop an accurate, general, and efficient

approach to parameterized timing, which can handle either

uncertain or random variations. Applied to random variations,

the approach is competitive with existing statistical static timing

analysis (SSTA) techniques, in that it allows for nonlinear delay

models and arbitrary distributions. Applied to uncertain variations,

the method is competitive with existing multi-corner STA

techniques, in that it more reliably reproduces overall circuit sensitivity

to variations. Crucially, this technique can also be applied

to the mixed case where both random and uncertain variations

are considered. Our results show that, on average, circuit delay is

predicted with less than 2% error for multi-corner analysis, and

less than 1% error for SSTA.

## 1. INTRODUCTION

Process and environmental variations greatly impact circuit delay,

and can cause parametric yield loss. With the traditional approaches

to timing verification becoming too expensive and unable

to handle local variations, new alternatives have emerged in

recent years, most of which can be described under the heading

of parameterized timing analysis. Essentially, timing quantities

are “parameterized” as explicit functions of the underlying process

and environmental parameters, allowing one to assess the

effect of these parameters on circuit delay, which can be useful

in determining the robustness of the design and its sensitivity

to variations. It is worth mentioning that process variations1,

which are manufacturing variations or mismatches between transistor

parameters, are statistical variations and can be modeled

as random variables (RVs), while environmental variations, which

are operating context variations, are non-random and must be

treated as uncertain parameters. Both types of variations must

be taken care of in the context of parameterized timing analysis.

One of the major trends in parameterized timing analysis
is

block-based statistical static timing analysis (SSTA) [1, 7, 2, 8,

9, 4, 6, 3], where parameters are modeled as RVs. In the past

few years, several SSTA techniques have been proposed. In [1,

7], linear-time techniques were proposed using linear (first-order)

delay models and Gaussian distributions for process parameters,

which allows the use of tightness probability to resolve the max

operation efficiently. It is expected, however, that nonlinearities

will increase with technology scaling. On one hand, as the magnitude

of process variations is increasing, first-order delay models

are no longer accurate. Also, there is evidence that delay is

highly nonlinear in low-voltage modes. On the other hand, process

variations are not necessarily Gaussian. For example gate

length has an asymmetric non-Gaussian distribution due to variation

in depth of focus (DOF). To address these concerns, several

attempts were made to generalize SSTA in order to handle nonlinear

delay models and/or random variables with non -Gaussian

distributions. In [8, 9], despite the use of quadratic models, Gaussian

distributions were forced on process parameters. In [6], non-

Gaussian process parameters were addressed, but first-order linear

models were used. Recently, both non-Gaussian parameters

and nonlinear models were addressed simultaneously, with varying

degrees of success. In [4], a sampling (Monte Carlo) based

regression is used to handle the max operation, which increases

the overall runtime; [2] uses expensive multi-dimensional integration

to handle the nonlinear non-Gaussian terms, which hinders

the complexity of the approach; [3] proposes an efficient nonlinear

non-Gaussian SSTA technique with linear complexity. This technique

uses Fourier series and moment matching to approximate

the max operation efficiently. The drawback of this approach is

that it requires subdividing the region of variation of every variation

source, then for every sub-region, the Fourier transform of

every possible distribution used is pre-computed. Although this is

done as a pre-processing step, it can introduce undesired complications,

especially if these distributions are unknown . In addition,

by using moment matching and being distribution dependent, all

these SSTA techniques fail to handle uncertain non-random parameters,

which is a requirement in general parameterized timing.

Another type of parameterized timing analysis is
linear-time

multi-corner static timing analysis (STA), which was introduced

in [5]. The idea is to propagate hyperplanes, i.e., affine linear

functions of the process and environmental parameters, in the

timing graph. The max operation is resolved by raising the hyperplanes

in a way to always follow the maximum corner delay.

In this way, the circuit maximum corner delay is estimated accurately.

Although the approach can handle both random and

uncertain parameters, it has some drawbacks: while trying to be

always accurate at the maximum corner delay, the approach loses

accuracy at the other corners. Consequently, the sensitivity to

process variations is lost and this approach can not be used for

optimization because the true spread of the circuit delay is not

accurately estimated. In addition, the analysis is restricted to

linear delay models.

In this work, we propose an efficient and general
parameterized

timing analysis technique that can handle nonlinear delay models

and account for delay variability due to both random process

parameters with arbitrary (and possibly unknown) distributions

and uncertain non-random parameters (that typically may depend

on the operating environment). Our technique is based on

a novel and efficient method to resolve the nonlinear max operator

by either bounding or approximating it by a linear model,

while preserving the inherent nonlinearity of the delay model itself.

We have tested our technique within two timing verification

frameworks, namely multi-corner timing analysis and nonlinear

non-Gaussian SSTA, and have shown that, at least when using

quadratic delay models, the complexity of the approach is linear

in both the number of process and environmental parameters and

the circuit size. Our results show that the spread of the maximum

circuit delay is accurately captured, whereby, on average,

the maximum and minimum corner delays are predicted with less

than 2% error for multi-corner analysis. As for nonlinear non-

Gaussian SSTA, all timing characteristics are predicted with less

than 1% average error.

## 2. GENERAL PARAMETERIZED TIMING

In general, the delay of gates and interconnects is a nonlinear

function that can be approximated using a delay model that

depends on the underlying process and environmental variations.

As stated earlier, linear (first-order) and quadratic (second-order)

delay models have been previously used in the literature. Nevertheless,

for the time being, we will work under the assumption of

an arbitrary delay model; we will show later that our approach

can be used with a general class of nonlinear delay models. We

can write the delay D of gates or interconnects as follows:

where f_{D}(·) is an arbitrary delay model, and X_{i}’s represent process

and environmental variations. Recall that not all variations

can be modeled as random variables. While some parameters are

indeed random such as channel length or threshold voltage, others

are not statistical but rather uncertain parameters, such as temperature

or supply voltage. These parameters typically depend

on the operating environment. We will show that our analysis is

indifferent to whether parameters are random or uncertain and

thus the approach can be applied for both types of variations.

The benefit of parameterized timing analysis is in
elevating the

explicit delay dependence on process and environmental variations,

i.e., the delay model, from the stage level to the circuit

level, allowing one to assess the effect of these parameters on the

total circuit delay. In block-based timing analysis, this is done by

propagating timing quantities in the timing graph in topological

order, using a sequence of basic operations, such as add operations

on arrival times and arc delays, and max operations on the

timing quantities resulting from those additions in order to get

the output arrival time. If these basic operations do not distort

the delay model at hand, then circuit delay can be represented in

the same delay model. Unfortunately, it is known that the max is

nonlinear. The novelty of this work is in resolving the nonlinear

max operator using a linear model, while preserving the inherent

nonlinearity of the delay model.

In the following section, we propose two methods to
efficiently

resolve the max: first by using upper and lower bounds , and

second by using an approximation that minimizes the square of

the error . Our methods operate irrespective of the delay model

used provided it falls in a general class of nonlinear functions;

they also handle random parameters with arbitrary distributions,

as well as uncertain parameters. In the rest of the paper, we

will refer to random and uncertain parameters simply as process /

environmental parameters.

3. MATHEMATICAL FRAMEWORK

Let F be a general class of (possibly) nonlinear functions that

obey the following three properties,

1. F is closed under linear (and/or affine) operations

is bounded

can be maximized and
minimized efficiently

and assume that all timing quantities are represented using delay

models that are in F. For example, timing quantity A is modeled

as follows:

where X = [X_{1}, · · · ,X_{p}] represent
process/environmental parameters.

**Figure 1: Upper bound on Y**

The first property essentially states that linear
operations (such

as addition or subtraction) will result in functions that belong

to F; in other words, F “survives” linear operations, that is, if

A = f_{A}(X) ∈ F and B = f_{B}(X) ∈ F, then C = aA + bB + c,

where [a, b, c] ∈ R, will be such that C = f_{C}(X) ∈ F. Note

that all polynomial models satisfy this property. The second and

third properties imply that the delay model, and consequently

any timing quantity expressed using the model, is bounded by a

minimum and a maximum value over the space of parameters, i.e,

A_{min} ≤ A ≤ A_{max}, where:

Note that the second property is trivial if we recall that
all physical

process and environmental parameters are bounded, which

implies that delays are also bounded. The third property is only

forced to guarantee that our approach, which requires maximizing

and minimizing the delay model in order to operate, is computationally

efficient. For instance, if maximizing/minimizing the

delay model is linear (in the process/environmental parameters),

then the overall complexity of our approach is linear in the circuit

size and process/environmental parameters. By property 1,

it is clear that the add operation, being linear, will maintain their

membership in F as delay models are propagated during timing

analysis. However, the max operation, being nonlinear in general,

is the crux of the problem, and we now focus on it.

### 3.1 Max Operation

Let A and B be two timing quantities expressed using delay

models in F. Let C = max(A,B) be the maximum of A and

B. Since the maximum operator is, in general, nonlinear, then C

is not necessarily expressible using a delay model in F. We are

interested however in finding (1) two bounds on C, C_{l} and C_{u},

and (2) an approximation C_{a}, which can all be expressed using

functions in F, and such that:

where D = A − B and Y = max(D, 0).

Recall from property 1 that F survives linear operations
(including

subtraction), which means that D = f_{D}(X) ∈ F. By

properties 2 and 3, D is bounded and varies between [D_{min},D_{max}]

where D_{min} ≤ D_{max}. Depending on the signs of these extreme

values of D, we can identify two cases in which the max operator

is either linear or nonlinear. If D_{min} ≥ 0 then
, and

Y = D. In this case, C = A since A completely dominates B.

The converse happens when D_{max} ≤ 0; in this case, C = B, since

B completely dominates A. The more interesting case is when

the max is nonlinear, which can be identified when D_{max} ≥ 0

and D_{min} ≤ 0. In this case, which we will refer to by saying that

A and B are co-dominant, Y = max(D, 0) can not be expressed

using a delay model from F. We will now show how we can bound

and approximate Y using functions that belong to F.

### 3.2 Bounding the Max

**3.2.1 Upper bound**

Fig. 1 shows a broken solid line representing a plot of Y =

max(D, 0) between D_{min} and D_{max}, the extreme values of D.
We

are interested in finding a linear function of D that is guaranteed

to upper bound Y (recall, since D ∈ F, then any linear function

of D is also a member of F). The dashed line represents an affine

function of D which upper bounds Y and is exact at D_{max} and

D_{min}. Note that the bound is closer to the exact max around

D_{min} and D_{max} where either A or B dominates. The equation

for Y_{u}, the upper
bound on Y , can be expressed as follows:

By replacing Y with Y_{u}
in (7), we get an upper bound C_{u}
on C:

Note that since it is a linear combination of

A and B (property 1). To gain a more intuitive understanding of

the above relationship, let us define the following terms:

• S = D_{max} − D_{min} to be the “spread” of D

• S_{A} = D_{max} to be
the “strength” of A, i.e. the region where A dominates B (D ≥ 0)

• S_{B} = −D_{min} = |D_{min}|
to be the “strength” of B, i.e. the region where B dominates A (D ≤ 0)

• α = S_{A}/S is the
fraction of space where A dominates B

• (1 − α) = 1 − S_{A}/S
= S_{B}/S is the
fraction of space where B dominates A

Then, using the above notations, we can rewrite C_{u}
as follows:

where A and B are both weighted by their “extent of
dominance”,

so to speak, and the last term accounts for the region where both

A and B are dominant, hence the product of α and (1 − α).

**3.2.2 Lower bound**

Similarly, we would like to find a lower bound on Y in
order to

find a lower bound C = max(A,B). Looking back at Fig. 1, it is

easy to see that any function in the form Y_{l}
= aD, where 0 ≤ a ≤

1, is a valid lower bound on Y = max(D, 0) and can be expressed

using a function in F (property 1). In practice, we have found

that limiting the choice of Y_{l}
to one of three functions depending

on the values of D_{min} and D_{max} is sufficient. Figures 2-4 depict

these three cases. In addition to showing Y in solid line and upper

bound Y_{u} in
dashed line, these figures show the lower bound Y_{l}

to be one of the following:

where the slope of Y _{l}
in the third case is equal to that of the

upper bound Y_{u}.
Note that means “much larger than”, and it

was set to be at least 4 times larger in our simulations.

Replacing each case of the above in (7) gives us C_{l},
the lower

bound on C:

where α is as defined in (10). Therefore,
since

it is a linear combination of A and B (property 1).

### 3.3 Least Squares Max Approximation

In the previous sections, we have shown how we can
determine

upper and lower bounds on C = max(A,B) using a carefully

chosen linear combination of A and B. We are now interested

in finding an expression C_{a}
that approximates C = max(A,B)

and can be expressed using a function that belongs to F. To do

that, it suffices to approximate Y = max(D, 0) in (7) by a linear

approximation Y_{a}
in the form Y_{a} =
aD + b. We will choose a

and b in such a way to minimize the sum of the squares of the

error inside the interval [D_{min},D_{max}]; we call this approximation

the least squares max approximation. It is understood that this

approximation is applied only when the max is nonlinear, i.e., in

the case of co-dominance.

Let E be the total error incurred by the above
approximation.

Then we can express E as follows:

We now determine the parameters a and b that minimize E.

To do that, we first determine the partial derivatives of E, ∂E/∂a

and ∂E/∂b , with respect to a and b, then we set the derivatives to

zero and solve for a in b. This gives us the following two equations

in a and b:

Finally, a and b can be easily obtained by solving the
system of

equations (14) and (15), which result in:

C_{a}
can be easily obtained by replacing Y with Y_{a}
= aD + b

in (7). It is easy to see that since it is a
linear

combination of A and B which are in F (property 1). Fig. 5

**Figure 5: Least squares Max approximation**

shows the true max, Y = max(D, 0) in solid line, and the
least

squares max approximation, Y_{a}
= aD + b, in dashed line.

To summarize, we have presented a mathematical framework

that resolves the nonlinear max operator in two ways; either by

using bounds, or by using an approximation that minimizes the

error with the true max. This framework is simple and general,

in the sense that it can be applied to a general class of nonlinear

delay models, and it uses simple linear operations, allowing

to keep and propagate the same delay model to later stages. In

addition, the analysis is indifferent (1) to whether the variation

sources are modeled as random variables or uncertain variables,

or (2) to the types of distributions used, when the variations are

random. In spite of its apparent simplicity, we will now demonstrate

that this approach is extremely effective and competitive in

dealing with two difficult application areas: multi-corner timing

analysis as well as nonlinear non-Gaussian SSTA. Crucially, this

approach can also deal with the “mixed” case, which is typical

of practical situations, where some variables are random while

others are simply uncertain.

## 4. MULTI-CORNER STA

In corner case analysis, circuit timing must be checked at
various

process/environmental corners, which are typically extreme

values of process/environmental parameters. This approach to

timing verification is exponential in the number of varying parameters

as multiple runs of STA are needed to cover all possible

corners in order to determine the maximum and minimum

corner delays. Instead, in practice, using parameterized timing,

where timing quantities are expressed using a variational delay

model that depends on process and environmental parameters,

one hopes to do this task with only one traversal of the timing

graph; this is what we call linear-time multi-corner STA.

In this section, we demonstrate how our simple framework
can

handle this otherwise complex analysis in a simple and elegant

fashion. To our knowledge, and unlike [5], where the approach

is restricted to linear delay models, we are the first to handle,

in linear-time, multi-corner STA with linear and nonlinear delay

models alike. In order for our framework to hold, all we need

to show is that the three properties of section 3 are satisfied.

For illustration, we will demonstrate our approach for linear and

quadratic models.

### 4.1 Linear and Nonlinear Models

Let F_{1}
and F_{2} be the
sets of linear and quadratic delay models

respectively. Let A be a timing quantity such that:

where a_{o}
is the nominal delay of A, and a_{i}
and are first-order

and second-order sensitivities to X_{i}.
Note that X_{i}’s
are arbitrary

variation sources (random/uncertain variables) that are bounded,

and without loss of generality, assume that −1 ≤ X_{i}
≤ 1.

It can be easily shown that property 1 holds, i.e., both F_{1}
and

F_{2} survive linear
operations. In fact, if [A,B] ∈ F_{1},
then C =

aA+bB +c also ∈ F_{1}.
The same applies for F_{2}.
Property 2 also

holds, since X_{i}’s
are bounded. As for property 3, both the linear

and the quadratic model can be easily maximized and minimized

in O(p) time, where p is the number of process/environmental

parameters; if A ∈ F_{1},
then:

whereas, if A ∈ F_{2},
then maximizing and minimizing A over the

space of variations requires maximizing and minimizing the individual

quadratic terms, In the Appendix,

we show how this can be done analytically depending on whether

g(X_{i}) is monotone
in [−1, 1] or not. Therefore maximizing and

minimization A is linear in the number of parameters, since there

are p quadratic terms.

Given that all the required properties are satisfied by F_{1}
and

F_{2}, the methods
described in sections 3.2 and 3.3 for resolving

the max operation can be applied to demonstrate multi-corner

STA with linear and nonlinear delay models. The timing graph is

traversed topologically, and our bounding/approximation scheme

is applied to handle the max operation at every stage. This results

in expressing the arrival time at the sink node, i.e., the maximum

circuit delay, using the delay model at hand. Once this expression

is obtained, it can be easily maximized and minimized as shown in

this section to bound/approximate the maximum and minimum

corner delays of the maximum circuit delay.

### 4.2 Results

We have tested our approach by first characterizing a 90nm

CMOS library using HSPICE in order to determine the sensitivities

of gate delay to various process parameters. We have chosen

to vary channel length (L_{n}
and L_{p}), and
threshold voltage (V_{tn}

and V_{tp}) of NMOS
and PMOS transistors, and have determined

the sensitivities of gate delays to these process parameters. The

variation information was specified in the technology files. Our

technique was then implemented using C/C++ and was tested on

the ISCAS85 benchmark circuits. For each circuit, the maximum

circuit delay is determined at various corners using exhaustive

corner case analysis, and the true maximum and minimum corner

delays are recorded. Our framework is then applied, using (1)

the lower bound technique, (2) the upper bound technique, and

(3) the least squares approximation, to predict the maximum and

minimum corner delay for every circuit. The results are summarized

in Table 1, where the values shown are normalized to the

true minimum and maximum corner delays respectively, determined

by corner case analysis. For example, the second column

gives a lower bound on the minimum (over all corners) circuit delay,

and the last column gives an approximation of the maximum

(over all corners) circuit delay. The closer the values are to 1 the

more accurate they are. Note that, unlike [5] where the method

is only accurate in predicting the circuit delay at the maximum

corner, we can accurately estimate the maximum circuit delay at

both the minimum and the maximum corners, so that the spread

of the maximum circuit delay is well-captured. In addition, our

approach is not restricted to linear models. The last row of the

table shows the average percent error for every approach; the

maximum and minimum corner delays can be approximated up

to 0.7% and 1.8% respectively.

## 5. NONLINEAR NON-GAUSSIAN SSTA

We now demonstrate nonlinear non-Gaussian SSTA, using a

general quadratic delay model that depends on process variables

modeled as RVs with arbitrary distributions, as well as uncertain

non-random parameters. As has become typical in the SSTA

literature [1], we assume that one can deal with within-die correlations

using some simple scheme by which correlation is resolved

based on the physical location of a cell on the layout surface. As a

result, when it comes to those variations which are random variables

(as opposed to the uncertain non-random parameters), we

assume that we are only dealing with global variations and purely

random variations. Before proceeding with the details, we first

show how the three properties of the delay model are satisfied in

order for our framework to hold.

### 5.1 Delay Model

Assume that gate delay D is expressed using a quadratic
model,

F, as follows:

where d_{o}
is the nominal delay, d_{i}
and are first-order and second-order

sensitivities to X_{i},
and d_{r} is the
sensitivity to the purely

independent random variation specific to D.

Because our framework is indifferent to whether parameters

are random or uncertain, there is no restriction on X_{i}’s,
which

can be either RVs or uncertain non-random parameters alike. If

it is random, X_{i} is modeled as an independent zero mean RV

with an arbitrary distribution, such that −1 ≤ X_{i}
≤ 1. This can

be any distribution, including common cases such as a truncated

Gaussian (normal) distribution, a uniform distribution, etc. If it

is uncertain, X_{i}
is simply assumed to vary in [−1, 1]. Note that,

in both case, X_{i}’s
are global variation sources that are shared

by all gate delays and timing quantities. As for the purely independent

random variation , we will assume that it
can be

modeled as a standard normal distribution with zero mean and

unit variance. This is because are typically
the result of

various independent random effects that add up and converge to

a normal distribution by the central limit theorem.

**5.1.1 Add Operation**

The add operation and generally any linear operation can
be

easily performed without destroying the above quadratic model.

Assume that [A,B] ∈ F:

then C = aA+bB+c can be expressed using the quadratic
model

as follows:

where since
are independent

standard normal RVs, and is an independent
standard

normal RV specific to C. Therefore, F satisfies property 1.

**5.1.2 Max Operation**

As explained in section 3, the max operation C = max(A,B)

is resolved by first subtracting A and B , i.e., D = A − B and

then bounding/approximating C using linear combinations of A

and B; recall that the coefficients of the linear combinations are

functions of the minimum and maximum values of the difference

D, i.e., D_{min} and D_{max}.

We have already shown how to perform linear operations
using

the quadratic model. Hence, in order to apply the results of

section 3, it remains to show how the quadratic model is bounded

and can be efficiently maximized and minimized over the space

of variations (properties 2 and 3). Assume that we have already

performed the subtraction D = A − B, and D is given by:

Since X_{i}’s
and are all independent, then the maximum
D_{max}

and minimum D_{min} of D are achieved when all variations are

maximized and minimized separately. In other words, we need to

maximize and minimize the quadratic terms and the independent

random term.

The quadratic terms
can be analytically

maximized and minimized as shown in the Appendix. As for

the purely independent random variation ,
recall that it is

modeled as an RV with standard normal distribution, which suggests

that can take values in −∞ to +∞. This,
however,

is not realistic, and it is usually the case that standard normal

distributions are truncated between [−k, k], where k represents

multiple standard deviations. As an example, setting k = 3 will

cover 99.73% of the standard normal distribution. As a result,

the maximum and minimum values contributed by the independent

random component are kd_{r }
and −kd_{r}
respectively. Hence,

by combining the above two contributions, D_{min} and D_{max} can

be easily determined. Having shown that the three properties of

section 3 are satisfied by F, we use the approaches in sections 3.2

and 3.3 to resolve the max operation.

### 5.2 Complexity Analysis

We have shown that both add and max operations are
resolved

using simple linear operations involving the delay model; in addition,

the coefficients of the linear combination needed for the max

operation involve a subtraction and a maximization/minimization

performed on the model. If p is the total number of variation

sources, then performing an addition or a subtraction is O(p);

also, performing a maximization/minimization of the model is

O(p). This means that both add and max operations are linear in

the number of variation sources. Therefore, the overall complexity

of a block-based SSTA technique using the above operations

is O(pn), where n is the circuit size.

### 5.3 Results

We have implemented our nonlinear non-Gaussian block-based

SSTA technique using C/C++ and have tested it on the ISCAS85

benchmark suite. Similarly to [3], and as a proof of concept, we

have generated the variation information randomly. We have chosen

the coefficients of the quadratic delay model in such a way that

every variation source causes 10% to 20% deviation in the nominal

delay. In addition to the purely random variation which follows a

truncated Gaussian distribution, 4 global variation sources X_{i}’s

were used, each following either a truncated Gaussian, a uniform,

or a triangular distribution as shown in Fig. 6. The accuracy of

our technique is compared to Monte Carlo analysis with 10, 000

runs. All delays reported are normalized to the nominal circuit

delay. Fig. 7 shows a plot of the cumulative distribution functions

(CDF) for benchmark c1355 for the case of variations with

a uniform distribution, generated using our SSTA technique and

compared to Monte Carlo simulation. Note that the bounds are

valid and accurate, and the least squares (LS) approximation is

very close to the true distribution. Table 2 compares the following

timing metrics: the 95 and the 99 delay percentiles, and the

ratio of standard deviation to the mean σ/μ, generated using the

least squares approximation (LS-SSTA) to Monte Carlo analysis,

for Gaussian, uniform, and triangular distributions. The results

show that our approach is consistently accurate for all metrics

and different distributions, with an average error less than 1%.

In the mixed case, where one is dealing with both random

variables and uncertain variables, the overall (random) circuit

delay and the interesting statistical metrics (like mean, variance,

percentiles) are effectively functions of the uncertain variables. If

this functional dependence is complex, then the desirable worstcase

values (of the interesting statistical metrics) must be found

by a process of search or optimization. This type of follow-up

analysis is beyond the scope of this paper, and is the topic of our

continued work under this project. For now, the above results

were obtained at a specific setting (the nominal) of the uncertain

variables. This does not diminish the value of the results, because

one strength of our existing approach is that it provides an explicit

dependence of the total circuit delay on the uncertain parameters,

so that one does not simply have to repeat the overall SSTA for

different settings.

**Figure 7: CDF comparison for c1355.**

## 6. CONCLUSION

We have proposed a general parameterized timing analysis
technique

that can handle nonlinear delay models and account for delay

variability due to both random process parameters with arbitrary

distributions and uncertain non-random parameters which

depend on the operating environment. Central to this technique

is a novel and efficient method to resolve the max operator by

bounding it and approximating it using linear models, while preserving

the inherent nonlinearity of the delay model itself. We

have tested our technique within two timing verification frameworks,

namely multi-corner timing analysis and nonlinear non-

Gaussian SSTA, and have shown that the complexity of the approach

is linear in both the number of process and environmental

parameters and the size of the circuit. Our results show that,

on average, circuit delay is predicted with less than 2% error for

multi-corner analysis, and less than 1% error for SSTA.

## APPENDIX

For completeness, we show the (simple) process by which
one can

maximize or minimize a quadratic function of the form, g(x) =

ax+bx^2, where −1 ≤ x ≤ 1, and [a, b] ∈ R. Recall that the minimum/

maximum is at x_{v}
= −a/(2b). If x_{v}
falls outside [−1, 1]

then g(x) is monotone in [−1, 1], so that its maximum and minimum

occur at the domain boundaries:

On the other hand, if x_{v}
falls in [−1, 1], then g(x) is not monotone

in [−1, 1], i.e., the maximum and minimum can be either at the

vertex or at the boundaries of the domain: