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

cin

cin

cin

FA3 FA2 FA1 FA0

FA3 FA2 FA1 FA0

FA3 FA2 FA1 FA0

(a) (b) (c)

Figure 7.10 Node transfer theorem to add one level of pipeline registers in a 4-bit RCA. (a) the
original DFG. (b) Node transfer theorem applied around node FA0. (c) Node transfer theorem applied
around FA1

Example: Figure 7.10 shows this strategy of pipelining applied to the earlier example of adding
one stage of pipeline registers in a 4-bit RCA. The objective is to break the critical path that is the
carry out path from node FA1 to FA2 of the DFG. To start with, one register is added to all the input
edges of the DFG, as shown in Figure 7.10(a). The node transfer theorem is applied on the FA0 node.
One register each is transferred from all incoming edges of node FA0 to all outgoing edges.
Figure 7.10(b) shows the resultant DFG. Now the node transfer theorem is applied on node FA1. One
delay each is again transferred from all incoming edges of node FA1 to all outgoing edges. This has
moved the pipeline register in the critical path of the DFG while keeping the data coherency intact.
The final pipelined DFG is shown in Figure 7.10(c).
Example: This example adds three pipeline registers by applying the delay transfer theorem to a
4-bit RCA. Figure 7.11 shows the node transfer theorem applied repeatedly to place three pipeline

cin

FA3 FA2 FA1 FA0

FA3 FA2 FA1 FA0

cin

(a) (b)

cin

cin

FA0

FA3 FA2 FA1 FA3 FA2 FA1 FA0

(c) (d)

Figure 7.11 Adding three stages of pipeline registers by applying the node delay transfer theorem on
(a) the original DFG, around (b) FA0, (c) FA1, and (d) FA2