RETIMING - Timing - page 229

to FF motion across its fanout gates is modeled by the mirror

variable
The change in the number of FF's in the circuit, under maximal sharing
obtained by retiming a gate by one unit can be calculated as follows. The
decrease in the cost function obtained by removing an FF from each of the
fanouts of a gate is one unit, even for multiple fanout gates since the FF's on
all the fanouts were shared. The increase in the cost function from adding an
FF to all the inputs of a gate is equal to the number of fanins of that
have only one fanout, since any FF added to a fanin of gate that has more
than one fanout is already modeled by the mirror variable of
that fanin gate Thus, the cost contribution of any single fanout gate
is given by while that of a multi-fanout gate is given by
where is the set of fanins that have only a
single output, i.e., and Therefore, the
cost function may be written as the summation of these terms over all gates.

Efficient implementation. Although the LP in (10.15) can be efficiently
solved by solving the dual, the computation of W and D matrices requires
time and memory. Further, the number of period edges re-
quired can be very large, destroying the sparsity of the circuit graph. Because
of these reasons, the minimum area retiming problem cannot be solved in rea-
sonable time using the method from [LS91]. Shenoy and Rudell in [SR94]
presented an efficient implementation, where they proposed a constraint gen-
eration method requiring time but only O (| V |) memory, and
a technique to prune the number of period constraints.
The algorithm uses a combination of the Dijkstra's algorithm and the Bellman-
Ford algorithm. It works by generating one row, say the row, of the W and
the D matrix at a time. An ordered pair denoted by
is associated with each edge and is used to compute the shortest distance
from a source vertex A heap is maintained for each distinct value of and
is indexed by this value. Until all heaps are empty, the node at the top of the
minimum index heap is extracted using the function pop-min(heap index) .
The fanouts of are then added to the appropriate heaps if their or
values are updated by Bellman-Ford relaxation. At the end of this procedure
and
Note that to satisfy a clock period, P, the only requirement is to ensure that
each path with delay greater than P has at least one FF on it. The number of
FF's on any path is monotonic with respect to the path length since negative
edge weights are not allowed. Due to this monotonicity of edge weights, if at
least one FF is placed on a sub-path, then it is guaranteed that at least one
FF will exist on all paths containing this sub-path. Adding a period constraint
from to is one way to ensure at least one FF on all paths from to The

idea is to add a period edge to only the vertex reachable from that satisfies

the following: