RETIMING - Timing - page 241

If is odd, the fractional change must also be considered. For a positive
value of the last latch moved on is of phase Therefore,

the latch on the boundary of (which includes gate ) will be of phase

which is same as Thus, the fractional period

added by this last latch is If is negative, then the

last latch moved off by forward retiming across is of phase and

the quantity must be subtracted from the

timing allowance of path

The third line is the change in the timing allowance of the path due to

latches being moved off or on through gate and is derived in a similar

manner to the second line.
For a more formal mathematical proof, the reader is referred to [Pap93].
These constraints in relations (10.25) and (10.26), together with the nonneg-
ativity constraint, form an integer monotonic program
that can be solved using graph-based algorithms.
A similar method for retiming level-clocked circuits was independently pre-
sented in [LE91, LE92, LE94], and was based on the SMO formulation of timing
constraints.

10.6.4 The relation between retiming and skew for level-clocked circuits
To derive timing constraints in the presence of skews, the SMO model of Sec-
tion 7.3.2 is augmented with new notation. A skew, is associated with every
latch where is the set of all latches in the circuit. It is worth pointing
out at this juncture that the skew values here are not physical skews to be
applied to the final circuit, but conceptual ideas that will eventually lead to
achieve a retiming solution. No restrictions are placed on the value of

i.e.

We define a latch shift operator shown in Figure 10.15, much like the
phase shift operator in the SMO formulation. This operator converts time
from the local time zone of latch to the local time zone of latch taking into

account their skews. It is defined as