Civil Engineering Reference
In-Depth Information
path lengths on a Manhatan grid. This assumption is valid for a perfectly sym-
metric clock network in which the load capacitances at all the sinks is precisely
the same; however‚ this is an invalid assumption for real circuits. The work
in [Tsa91‚ Tsa93] recognized that due to uneven loading and buffering effects‚
path-length equalization methods do not achieve the effect of balancing clock
delays. An approach that incorporates this effect and uses the Elmore delay
model to automatically build zero-skew clock trees was suggested. We will now
describe this method in detail‚ and explain how it may be extended to build
clock trees with specified‚ and possibly nonzero‚ skews at the sink nodes.
The Elmore delay model [RPH83] is used to calculate the signal propagation
delay from a clock source to each clock sink. A modified hierarchical method
is proposed for computing these delays in a bottom-up fashion. This algorithm
takes advantage of the structure of the Elmore delay calculations to construct
a recursive bottom-up procedure for interconnecting two zero-skew subtrees to
form a new tree with zero skew.
We now describe one recursive step of the bottom-up procedure. In each such
step‚ two subtrees are combined into one subtree; by construction‚ it is ensured
that each such subtree has zero skew from its current root to all of its sinks.
In other words‚ the signal delay from the root to the leaf nodes of the subtree
are forced to be equal. In the first step‚ each sink node constitutes a subtree‚
and the skew within each such subtree is trivially seen to be equal to zero. In
subsequent steps‚ partially constructed zero-skew subtrees are combined.
In one step of the recursion‚ two zero-skew subtrees are connected with a
wire and a new root is defined for this combined structure‚ ensuring zero skew
from the root to all sinks in the merged tree. This is illustrated in Figure 9.5‚
and this new root is referred to as the
tapping point.
If we denote the total
wire length of this connecting wire segment as
and the wire length from the
tapping point to the root of subtree1 be
then the wire length
from the tapping point to the root of subtree2 is
A closed-form expression for the value of that yields zero skew will now be
determined. Consider each subtree in Figure 9.5. Since subtree1 [subtree2] has
zero skew‚ the delay from its root to each leaf node is equal‚ say
Let the
corresponding total capacitances in the subtrees be
respectively. The
wires of length
and
are modeled using the
model shown
in the
figure.
The delay from the tapping point to each leaf node in subtree1 is equated
to the delay to each node in subtree2 using the Elmore delay formula [SK93]
to provide the following equation
Substituting
and
where
and
are‚ respectively‚ the per unit resistance and capacitance of the intercon-
