Polyhedral Process Networks - Signal Processing Systems - page 1328

Fig. 6 Code generated for
the process in Fig. 5

1 for(i=0;i<N;i++) {
2 if (i == 0)

Read(1);

3

if (i >= 1) 4

Read(2);

5

f();

6

if(i<N-1) 7

Write(2);

8

if (i == N - 1) 9

Write(3);

10

11 }

R1 := { S[i] -> R1[i] }(ran M1);
R2 := { S[i] -> R2[i] }(ran M2);
W2 := { S[i] -> W2[i] }(dom M2);
W3 := { S[i] -> W3[i] }(dom M3);
S := { D[i] -> [i,1]; R1[i] -> [i,0]; R2[i] -> [i,0];
W2[i] -> [i,2]; W3[i] -> [i,3] }
* (D + R1 + R2 + W2 + W3);
codegen S;
The first four lines define the iteration domain and the communication channel
mappings. The next four lines compute the domains of the reads and writes by
computing domains and ranges of the mappings and performing a renaming. The
next line defines the schedule. Note that * is here applied to a relation and a set, in
which case the domain of the relation is intersected with the set. The final line prints
the code corresponding to S .

5 Dataflow Analysis

This section describes how the communication channels in the process network are
constructed using exact dataflow analysis [ 8 ] . We first discuss the standard dataflow
analysis and then explain how some inter-process communication can be avoided
by considering reuse.

5.1 Standard Dataflow Analysis

Standard exact dataflow analysis [ 8 ] is concerned with finding for each read of
a value from an array element in the program, the write operation that wrote
that value to that array element. By replacing the write to the array by a write
to one or more communication channels (as many as there are accesses in the
program where the value is read) and the read from the array to a read from