Civil Engineering Reference
In-Depth Information
the edge is a variable whose value is to be determined; the physical meaning
of the variable here is the number of delays padded on the edge
Delays may be inserted only on the external edges. There are two arrival
times associated with each vertex
an early arrival time
and a late arrival
time
If
is a primary input (
PI
)‚ then
and
are specified by the
user or the algorithm at the higher level‚ say‚
as
If
is an
input/output pin of a gate‚ then
where denotes the set of fanins of A path is a sequence of vertices‚
and the delay of a path is denoted by At every primary output
(PO)
the data is required to be available no earlier than and no later than
namely‚ A path fails to meet the short path constraint
if In that case‚ delays are added along the edge
on the short path to remove this violation. The area overhead of this addi-
tion is proportional to the number of delays added‚ and is approximated as
The problem of finding the minimum-cost padding that sat-
isfies the timing constraints can now be expressed as a linear program‚ with
constraints obtained by relaxing Equation (8.33)‚ and an objective function
that corresponds to the number of buffers added.
It was shown that in any circuit‚ if for every pair
and
PO
such
that combinational path we are given that
then the padding problem can be solved. An intuitive explanation for this
condition is as follows. If we interpret the term‚ as the uncertainty
interval in the arrival time of the signal at the primary input‚ and the term‚
as the uncertainty in the required time at the output‚ then since
the circuit is causal‚ it cannot make the uncertainty interval at the output any
narrower than the uncertainty interval at its input.
8.10 SUMMARY
This chapter has overviewed several methods that can be used for transistor-
level timing optimization of digital circuits. The specific methods overviewed
