Signal Flow Graphs and Data Flow Graphs - Signal Processing Systems - page 1263

a b

G 1

D

D D D

IN IN

a b c a b c

G 2

OUT OUT

c

D D

IN

a b c

2D 2D

2D

OUT

Fig. 8 ( a ) The unretimed DFG with a cutset shown as a dashed line .( b ) The 2 graphs G 1and G 2
formed by removing the edges in the cutset. (c) The graph obtained by cutset retiming with k = 2

Cutset retiming is a special case of retiming and it only affects the weights of the
edges in the cutset, which is a set of edges that can be removed from the graph to
create two disconnected subgraphs. If these two disconnected subgraphs are labeled
G 1 and G 2 as depicted in Fig. 7 b , then cutset retiming consists of adding k delays
to each edge from G 1 and G 2 , and removing k delays from each edge from G 2 to
G 1 . In the case of k 1, the DFG in Fig. 7 a can then be transformed to the DFG in

Fig. 7 c by using cutset retiming technique.

=

3.4.2 Pipelining

Pipelining is a special case of cutset retiming where there are no edges in the cutset
from the subgraph G 2 to the subgraph G 1 as shown in Fig. 8 b , i.e., pipelining applies
to graphs without loops. These cutsets are referred to as feed-forward cutsets, where
the data move in the forward direction on all the edges of the cutset. Consequently,
registers can be arbitrarily placed on a feed-forward cutset without affecting the
functionality of the algorithm. If two registers are inserted to each edge, the DFG
in Fig. 8 a can then be transformed into the DFG in Fig. 8 c by applying pipelining
technique. Therefore, complex retiming operations can be described by multiple
simple cutest retiming or pipelining operations applied in a step-by-step manner.