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

a b

D

(2) (4) (2) (4) (5)

A B A B C

2D 2D

Fig. 18 ( a ) A DFG with one loop that has a loop bound of 6 / 2 = 3 u.t. The iteration bound for

this DFG is 3 u.t. ( b ) A DFG with iteration bound T ∞ = max { 6 / 2 , 11 / 1 } = 11 u.t.

For example, the edge from node A to node B in Fig. 2 b enforces the inter-
iteration precedence constraint, which states that the execution of the k -th iteration
of A must be completed before the -th iteration of B . On the other hand, the

edge from B to A enforces the intra-iteration precedence constraint, which states that
the k -th iteration of B must be executed before the k -th iteration of A .

( k + 1 )

5.2 Definition of Critical Path and Iteration Bound

The critical path of a DFG is defined to be the path with the longest computation
time among all paths that contain no delay elements. The critical path in the DFG in
Fig. 18 a is the path A B , which requires 6 u.t. Since the critical path is the longest

path for combinational rippling in the DFG, the computation time of the critical
path is the minimum computation time for one iteration of the DFG, which is the
execution of each node in the DFG exactly once.
A loop is a directed path that begins and ends at the same node and the amount
of time required to execute a loop can be determined from the precedence relation
described by the edges of the DFG. According to these precedence constraints,
iteration k of the loop consists of the sequential execution of A k and B k . Given that
the execution times of nodes A and B are 2 and 4 u.t., respectively, one iteration of
the loop requires 6 u.t. This is the loop bound, which represents the lower bound on
the loop computation time. Formally, the loop bound of the l -th loop is defined as
t l

→

w l ,where t l is the loop computation time and w l is the number of the delays in the
loop. As a result, the loop bound for the loop in Fig. 18 a is6 2=3u.t.

As another example, the DFG in Fig. 18 b contains two loops, namely, the loops
l 1 =

/

A . Therefore, the loop bounds for l 1 and
l 2 are 6/2 = 3 u.t. and 11/1 = 11 u.t., respectively. The loop with the maximum loop
bound is called the critical loop and its corresponding loop bound is the iteration
bound of the DSP program, which is the lower bound on the iteration or sample
period of the DSP program regardless of the amount of the computing resources
available. Formally, the iteration bound is defined as

A → B → A and l 2 = A → B → C →

t l
w l }

T ∞ = max l ∈ L { (10)