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

N 1 N 1

x[n] x[n]

+

+

y[n] y[n]

N 61

N 62

L 1

N 3 N 3

N 4

N 4

+

+

x + x

+ x

0.5 1.5

N 6

b N 5 N 5

a b

N 6

a

N 21

L 1

N 22

x

0.5 1.5

c

N 2 N 2

c

(a) (b)

Figure 7.21 (a) Retimed DFG with critical path of 4 timing units and IPB of 3.5 timing units. (b) Fine-
grain retimed DFG with critical path delay ¼ IPB ¼ 3.5 timing units

to reduce the critical path using retiming, although this requires fine-grain insertion of algorithmic
registers inside the computational units.
The designer may choose not to get to this complexity and may settle for a sub-optimal solution
where the critical path is reduced but not brought down to the IPB. In the dataflow graph, recursively
applying the delay transfer theorem around node N 4 and then around N 5 modifies the critical paths to
N 6 ! N 3 ! N 1 or N 2 ! N 3 ! N 1 with critical path delay of both the paths equal to 4 time units.
The DFG is shown in Figure 7.21(a).
Further reducing the critical path delay to the IPB requires a fine-grain pipelined multiplier. Each
multiplier node N 6 and N 2 are further partitioned into two sub-nodes, N 61 ,N 62 and N 21 ,N 22 ,
respectively, such that the computational delay of the multiplier is split as 1.5 tu and 0.5 tu,
respectively, and the critical path is reduced to 3.5 tu, which is equal to the IPB. The final design
is shown in Figure 7.21(b).

7.3.2 Cut-set Retiming for a Feedback System
In a feedback system, retiming described in section 7.2.2 can be employed for systematic shifting of
algorithmic delays of a dataflow graph G from one set of edges to others to maximize defined design
objectives such that the retimed DFG, G r , has same transfer function. The defined objectives may be
to reduce the critical path delay, the number of registers, or the power dissipation. The designer may
desire to reduce a combination of these.
Example: A second-order IIR filter is shown in Figure 7.22(a). The DFG implements the
difference equation:

y½¼ay n ½ 2 þx½n ð 7 5 Þ

:

The critical path of the system is T m þ T a , where T m and T a are the computational delays of a
multiplier and adder.
Figure 7.22(a) also shows the cut-set line tomove a delay for breaking the critical path of the DFG.
The retimed DFG is shown in (b) with a reduced critical path equal to max{T m , T a }. The same
retiming can also be achieved by applying the delay transfer theorem around the multiplier node.