Civil Engineering Reference
In-Depth Information
by a convolution‚ and for parallel-connected edges‚ the CDF may be computed
by taking the product of the CDFs of the incoming edges (assuming that these
edges are statistically independent). For reconvergent subgraphs that are in
neither of these forms‚ in principle‚ the computation can be carried out by a
path enumeration over the subgraph. However‚ this is liable to be computa-
tionally expensive arid is not a feasible option‚ particularly for reconvergences
with a large depth.
Therefore‚ the method identifies dependence .sets corresponding to such re-
convergences and employs bounding techniques to approximate the PDFs. The
informal definition of a dependence set is illustrated in Figure 6.7‚ where
is a dummy source node and is a dummy sink node. For nodes and
the nodes in the shaded region correspond to the transitive fanin that the two
nodes share. The set of nodes within this structure that fan out to the re-
mainder of the transitive fanin of is the set and this constitutes the
dependence set of Similarly‚ the dependence set of is The method
proceeds by propagating the arrival time PDFs to the first dependence node‚
and using conditional probabilities to perform the enumeration. More detailed
enumeration schemes that enumerate over different parts of a CDF are also
provided.
Since enumeration can be a costly procedure‚ a bounding technique is in-
troduced. The principles behind bounding are simple to understand. Consider
the graph shown in Figure 6.8(a). It is proven in [AZB03] that an
upper
bound
on the CDF of the graph in the figure is provided by the CDF
of the graph which simply splits the node and carries out the PDF
propagation by ignoring the structural correlation between the path
and the path. A
lower bound
on the CDFs for two dependent arrival
times can be found by simply using the envelope of their CDFs using the min
operator on the original graph (without node splitting)‚ and this is shown in
Figure 6.8(b).
The overall procedure uses a heuristic method for merit computation for a
dependence node‚ to determine whether it should be enumerated or bounded.
Experimental results on benchmark circuits show that these bounds are very
successful in generating tight estimates of the CDF.
6.5
STATISTICAL STA UNDER SPATIAL CORRELATIONS
In cases where significant spatial correlations exist‚ it is important to take these
into account. Figure 6.5 shows a comparison of the PDF yielded by an SSTA
technique that is unaware of spatial correlations‚ as compared with a Monte
Carlo simulation that incorporates these spatial correlations‚ and clearly shows
a large difference. This motivates the need for developing methods that can
handle these dependencies.
