Pipelining, Retiming, Look-ahead Transformation and Polyphase Decomposition - Digital Design of Signal Processing Systems: A Practical Approach - page 314

r( i ) = +2 r( j ) = -1

i j

i j

e ij

w(e ij ) = 1

w r (e ij) = 2

(a) (b)

Figure 7.15 Node retiming mathematical formulation. (a) An edge e ij before retiming with w(e ij ) ¼ 1.
(b) Two registers are moved-in across node i and one register is moved out across node j, for the retimed
edge w r (e ij ) ¼ 2

not get into the complications while designing the logic for large circuits. For smaller designs, the
problem can be solved intuitively for effective implementation [6]. This section, therefore, only
gives a description of the model and mentions some of the references that solve the models.
In retiming, registers are systematically moved across a node from one edge to another. Let
us consider an edge between nodes i and j, and model the retiming of the edge e ij . The retiming
equation is:

w r ðe ij Þ¼wðe ij ÞþrðjÞrðiÞ

where w(e ij )andw r (e ij ) are the number of registers on edge e ij before and after the retiming, respectively,
and r(i)andr( j) are the number of registers moved across nodes i and j using node transfer theorem. The
value of r( j) is positive if registers aremoved fromoutgoing edges of node j to its incoming edge e ij ,andit
is negative otherwise. A simple example of one edge is illustrated in Figure 7.15.
The retiming should optimize the design objective of either reducing the number of delays or
minimizing the critical path. In any case, after retiming the number of registers on any edge must
not be negative. This is written as a set of constraints for all edges in a mathematical modeling
problem as:

wðe ij Þþrð jÞrðiÞ 0 for all edges e ij

Secondly, retiming should try to break the critical path between two nodes bymoving the appropriate
number of extra registers on the corresponding edge. The constraint is written as:

wðe ij Þþrð jÞrðiÞC

for all edges e ij in the DFG that requires C additional registers tomake the nodes i and j meet timings.
The solution of the mathematical modeling problem for a DFG computes the values of all r(v)
for all the nodes v in the DFG such that the retimed DFG does not violate any constraints and still
optimizes the objective function.

7.2.12 Minimizing the Number of Registers and Critical Path Delay
Retiming is also used tominimize the number of registers in the design. Figure 7.16(a) shows a graph
with five registers, and (b) shows a retimed graph where registers are retimed to minimize the total
number to three.
To solve the problem for large graphs, register minimization is modeled as an optimization
problem. The problem is also solved using incremental algorithms where registers are recursively