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

Further, the same operand will be required as an input to the operator OP j at time
T i + t j . By the requirement that the operand can not be used by operator OP j before

it is produced by operator OP i , the following inequality can be derived:

T j + t j ≥ T i + t i (11)

Such an inequality holds for each pair of operands joined by an edge in the DFG.
In these inequalities, T i and T j are the unknowns, where the value t i − t j is a known

constant. A solution to the set of inequalities can be determined by using common
techniques for solving linear programming problems. Once a solution is found to
this set of inequalities, the circuit may be correctly synchronized by inserting a
delay equal to T j −

clock cycles between the operators OP i and OP j .
In general, many solutions exist to satisfy the set of inequalities for a given
architecture and hence there are many ways to synchronize the circuit. The goal of
optimal scheduling is to generate a solution that provides the minimal cost, where
cost is defined to be the total number of shift-register delays required to properly
synchronize the circuit. If a linear cost function can be defined, the minimum cost
problem can be easily formulated as a linear programming problem.

T i − ( t i − t j )

5.3.2 Minimum Cost Solution

Minimizing the total number of synchronization delays required for reach edge
between functional units of a circuit is not sufficient. Note that there exists the
possibility of multiple fanout from any functional unit. Therefore, the delays from
a multiple fanout output should be allocated sequentially instead of in parallel.
Consider a simple case where an output of some operator OP o is used as an input
to three other operators, OP A , OP B and OP C as shown in Fig. 20 a with delays of
10, 12 and 25 clock cycles. respectively. The total number of delays is equal to
10

47. An alternative sequential arrangement of the delays is shown in
Fig. 20 b , where the total number of delays is 25, which is the length of the longest
delay. Therefore, the total number of delays that need to be allocated to any node in
the circuit is equal to the maximum delay that must be allocated.
Let D x represents the maximum delay that must be allocated to an operand
OPND x of width w x . A total cost function to be minimized can now be defined:

+ 12 + 25 =

= ∑ x Cost D x w x (12)

where the sum is over each operand node in the circuit. For each node as shown in
Fig. 20 b , there exists a constraint equivalent to ( 11 ) ,

T j − T i ≥ t i − t j (13)