CLOCKING AND CLOCK SKEW OPTIMIZATION - Timing - page 199

of a Euclidean geometry‚ under a Manhattan geometry‚ there are several paths
between two points that have the same distance. Therefore‚ when the tapping
point is chosen during a bottom-up zero-skew merge‚ it may lie at a distance
away from one node along any of these routes‚ and the locus of possible
tapping points forms a line segment‚ called a merging segment.
In the problem at hand‚ since the skew is not fixed‚ but bounded‚ this permits
a variation in the location of the tapping point‚ and therefore‚ a variation in the
location of the merging segment of the DME procedure. A move in simulated
annealing corresponds to changing the position of a merging segment in such a
way that the skew bounds are satisfied.
The gate sizing results are stored in the form of a look-up table. The mini-
mum power of each combinational block for various sets of skews is determined
and stored in this table. When the clock network is perturbed‚ the skews are
mapped on to the closest set of skew values listed in the table‚ and the table
is accessed to determine the corresponding power dissipation. The cost of this
configuration is evaluated and fed into a simulated annealing loop that finds
the optimal solution to the problem.

9.5 TIMING ANALYSIS OF SEQUENTIAL CIRCUITS FOR SKEW

SCHEDULING

The optimization in Section 9.4.2‚ and indeed‚ many other procedures that work
with clock skew‚ requires the detection of violations of the clocking constraints.
This may be carried out by using a modification of CPM for delay estimation
that is generalized to handle sequential circuits [SSF95].
The procedure for timing analysis requires the determination of the optimal
skews and the arrival times at all gate outputs. Since the constraint graph for an
acyclic pipeline is acyclic‚ and since timing analysis involves the solution of the
longest path problem on this constraint graph‚ the complexity can be reduced
substantially by processing the vertices in topological order [CLR90]. Specifi-
cally‚ the timing analysis procedure is equivalent to applying CPM‚ described
in Section 5.2.1‚ to the graph‚ with gates being represented in the normal way‚
and flip-flops being represented by blocks with “delay” values of
where is the setup time for the flip-flop and P is the applied clock period‚
and is the uncertainty in the clock skew 5 .
We point out here that the reference point for the arrival time in each combi-
national block is the zero skew. For example‚ an arrival time of at the output
of a flip-flop implies that the clock signal at the flip-flop has been skewed by
If this flip-flop fans out to a single inverter with a delay of then the arrival
time at the output of this inverter would be Since skews may be either
positive or negative‚ it can be seen that arrival times may have either sign.
Consider Figure 9.13(a). We symbolically show the path from to
as being represented by a single gate with delay which corresponds
to the maximum combinational delay between these flip-flops. From (9.17) we