Polyhedral Process Networks - Signal Processing Systems - page 1335

Fig. 9 Outer product source

1 for(i=0;i<N;++i)
2 a: a[i] = A(i);
3 for(j=0;j<N;++j)
4 b: b[j] = B(j);
5 for(i=0;i<N;++i)
6

code

for (j = 0; j < N; ++j)

7 c:

c[i][j] = a[i] * b[j];

Fig. 10 Outer product
network with multiplicity

••••••

b

b

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

a a c

Fig. 11 Outer product
network without multiplicity

••••••

b

b

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

•
•
•
•
•
•

a

a a c

b

It should be noted that if we use the dataflow analysis from Sect. 5.2 , i.e., taking
into account possible reuse, then the resulting communication channels will never
exhibit multiplicity. Instead, two channels would be constructed, one for the first
time a value is read and one for propagating the value to later iterations. In general,
it is preferable to detect reuse rather than multiplicity, because the analysis results in
fewer types of channels and because taking advantage of reuse may split channels
that are both reordering and with multiplicity into a pair of FIFOs.

Example 17. Consider the code for computing the outer product of two vectors
showninFig. 9 . Figures 10 and 11 show the results of applying standard dataflow
analysis (Sect. 5.1 ) and dataflow analysis with reuse (Sect. 5.2 ) respectively. Each
figure shows the network on the left and the dataflow between the individual
iterations of the processes on the right. The iterations are executed top-down, left-
to-right. In the first network, the channel between b and c has mapping

M b → c = { b ( w ) → c ( r 1 , r 2 ) | 0 ≤ r 1 , r 2 < N ∧ w = r 2 }.

For testing multiplicity, we have the relation

T = { r 1 , 2 → r 2 , 2 |∃ r 1 , 1 , r 2 , 1 ∈ Z :0 ≤ r 1 , 1 , r 1 , 2 , r 2 , 1 , r 2 , 2 < N ∧ r 1 , 2 = r 2 , 2 ∧ r 1 , 1 < r 2 , 1 },

which is clearly non-empty, while for testing reordering we use the relation

T = { r 1 , 2 → r 2 , 2 |∃ r 1 , 1 , r 2 , 1 ∈ Z :0 ≤ r 1 , 1 , r 1 , 2 , r 2 , 1 , r 2 , 2 < N ∧ r 1 , 2 > r 2 , 2 ∧ r 1 , 1 < r 2 , 1 },