RETIMING - Timing - page 225

efficient way for minimum period retiming, since can be solved as a
single-source longest path problem. In the edge weights are
also real numbers and denote the number of fractional FF's present on an edge
The clock period of the circuit is P if the final continuous retimed
weight on each edge is no smaller than
10.5 MINIMUM AREA RETIMING OF EDGE-TRIGGERED CIRCUITS
As shown in Section 10.1, retiming can reduce the clock period of a circuit.
However, in doing so, it is possible that it may greatly increase the number
of registers. In fact, given any clock period for a general circuit, there will,
in general, be not one, but several retiming solutions that satisfy the clock
period; these differ in the manner in which they utilize the slack on noncritical
paths. The ASAP and ALAP retimings from Section 10.4.3 are just two of
these possible retimings, and each of these differs in terms of the number of
registers that it employs.
The objective of the minimum area retiming problem is to find one of these
retiming solutions at a given clock period, chosen in such a way that it has the
minimum number of registers over all feasible retimings satisfying the period.
This is a practical and meaningful objective, since minimizing the number of
registers would minimize the area of the circuit, as the retiming transformation
leaves the combinational logic untouched.
We will first overview the Leiserson-Saxe framework for minimum area re-
timing. Next, an efficient method for reducing the complexity of this method,
using bounds on the retiming variables derived from the equivalence between
clock skew and retiming, is presented. Finally, the extension of this approach
to level-clocked circuits is described.
10.5.1 The Leiserson-Saxe approach
A basic formulation. A mathematical programming formulation of the min-
imum area retiming problem was presented in [LS91], and is reproduced here.
Let the total number of registers in a circuit G be given by
The reader is referred back to Section 10.3 for the basic concepts and terminol-
ogy used in the representation of a circuit in terms of a retiming graph. Using
this notation, the total number of registers in a circuit after retiming,
can be calculated as follows:
where and represent the fanin and fanout sets of the gate Since
S ( G ) is a constant, the minimum area retiming problem for a target period P