RETIMING - Timing - page 239

In an edge-triggered circuit, the critical path is independent of the clock
period, and simply corresponds to the output with the largest delay, except
in the uninteresting case when the clock period is satisfied. In a level-clocked
circuit, however, critical paths are more difficult to identify since they may vary
from one clock period value to another. This was illustrated in [LE94] through
the following example. Figure 10.14 shows a situation where three paths,
and connect the vertex to the vertex the delay of each node is written
within its corresponding vertex. The description of each path is as follows:

where denotes the number of registers that currently lie on the path.
If a path from to has registers on it, then for a symmetric two-phase
clock with an active period of the amount of time available for data to
travel from to is time units, corresponding to the total active
time available from the input register of node to the output register of node

This leads to the following statements:
When a symmetric two-phase clock with a period of 3 units (and therefore,
an active time of 1.5 units) is applied, we require that and
Therefore, the path is critical since satisfying the constraint
on in the given circuit would violate the constraint on
When the period of the same clock is changed to 5 units, the requirements
are altered to and in this case, satisfying the former

would lead to a violation of the latter.
It is easily verified that the crossover point for the critical paths occurs at a
clock period of 4 units, where both are critical.
Note that the path is always subservient to path since it has the same
number of registers, but a smaller delay, and can, hence, never be critical.

10.6.2 Retiming of single phase level-clocked circuits
In [SBS91] an MILP formulation is presented for retiming single phase level-
clocked circuits. Constraints for correct clocking of single-phase circuits are laid
down, which were essentially similar to the SMO constraints in Section 7.3.2.
A new functionality constraint was also introduced in this work, which main-
tains temporal equivalence between the initial and the retimed circuit. The
constraint identifies a set of fundamental cycles in the directed graph corre-
sponding to this problem, and ensures that the sum of latches on each of these
is maintained during retiming. The property of the set of fundamental cycles
is that all other cycles can be expressed as a composition of these fundamental
cycles. The essential idea of the approach is to build a spanning tree on the di-
rected graph. If the graph has edges and vertices, then there are