Civil Engineering Reference
In-Depth Information
the change in the effective length for a gate in region
is given by
the delay can be written in the form
where the variables correspond to the sensitivity of the delay to the
L
variables. In other words‚ the change in delay can be written as a weighted
sum of the variables.
However‚ the PDF for a critical path may not be a good predictor of the
distribution of the circuit delay (which is the maximum of all path delays).
Later work by the same authors in [ABZ03b] derived an upper bound on the
CDF for the spatially correlated case‚ based on this quadtree model. Simplify-
ing the notation to represent the length variables as
each arrival time in
a CPM-like traversal may be written as
where
is the sensitivity of the delay of path to parameter
To find the
max of two such arrival times‚ the following inequality is used:
A heuristic technique is used to propagate arrival times during the CPM traver-
sal‚ using the bound to merge groups of arrival times when possible‚ and thus
propagating a set of arrival times. Experimental results in [ABZ03b] show
some success for this approach‚ but the accuracy near the tail of the CDF is
inadequate. It must be stressed‚ however‚ that research is still ongoing‚ and
the reader is invited to look out for more recent results that these authors will
have published subsequent to [ABZ03b].
A final method for SSTA under spatial correlations is due to [CS03a]‚ and
we will discuss this method in detail in the next section.
6.5.2
A principal component analysis based approach
The approach in [CS03a] is based on the application of principal component
analysis (PCA) techniques [Mor76] to convert a set of correlated random vari-
ables into a set of uncorrelated variables in a transformed space; the PCA step
can be performed as a preprocessing step for a design. The complexity of this
method is times the complexity of CPM‚ where is the number of squares
in the grid‚ plus the complexity of finding the principal components‚ which
