RETIMING - Timing - page 231

ASTRA approach is used for efficient minimum area retiming. By utilizing the
merits of both approaches, an efficient algorithm for constrained minimum area
retiming was developed. This algorithm, called MINArea RETiming (Minaret),
is capable of handling very large circuits in very reasonable runtime. The basic
idea of the approach is to use the ASTRA approach to find tight bounds on
the retiming variables. These bounds help reduce both the number of variables
and the number of constraints in the problem without any loss in accuracy.
By spending a small amount of additional CPU time on the ASTRA runs,
this method leads to significant reductions in the total execution time of the
minimum area retiming problem. The reduction in the problem size also reduces
the memory requirements, thus enabling retiming of large circuits. On a mid-to-
late 90s vintage computer, this approach has been shown to solve problems with
more than 57,000 variables and 3.6 million constraints in about 2.5 minutes.
The approach in Minaret is to find tight bounds on the variables, and
to use these bounds to avoid generating redundant constraints. By appropri-
ate application of these bounds, not only is the constraint set pruned but the
number of variables is also reduced. In this way, the size of the LP is reduced
enabling it to be solved more efficiently. The reduced constraints can be gener-
ated efficiently by using these bounds. Note that the exactness of the solution
is not sacrificed in doing so, since none of the essential constraints are removed.
We will now show the relation between the Leiserson-Saxe approach and
the ASTRA approach, and how a modified version of ASTRA can be used to
derive bounds on the variables in the Leiserson-Saxe method. Next, we show
how these bounds can be used to prune the number of constraints in minimum
area Leiserson-Saxe retiming. Finally, we present an example to illustrate the
method.
The concept of restricted mobility and bounds for the variables.
For the circuit in Figure 10.12, to achieve the minimum clock period of 4.0
units, one must move one copy of FF B to the output of gate G4. The possible
locations for FF's along the other path to FF C are at the input to gate G8,
or at the output of gate G8, or the inputs of gates (G9,G10) or the outputs of
gates (G9,G10); no other locations are permissible
Therefore, it can be seen that the FF's cannot be sent to just any location
in the circuit; rather, there is a restricted range of locations into which each
FF may be moved, and the mobility of each FF is restricted. This restricted
mobility may be used to reduce the search space, and hence the number of
constraints.
The concept of restricted mobility is related to the ASAP and ALAP retim-
ings presented in Section 10.4.3 in that the ASAP and ALAP retiming solutions
define the boundaries of the region into which an FF can move during retiming
while satisfying the target clock period. For example, Figures 10.12(a) and (b)
are the ASAP and ALAP retiming for the given clock period of 4.0 units and
the FF can move only in the region defined by these locations. These ASAP
and ALAP retiming solutions can be used to obtain bounds on the retiming