Polyhedral Process Networks - Signal Processing Systems - page 1311

depend on the signals being processed. Furthermore, all loop bounds, conditions
and array index expressions need to be such that they can be expressed using
affine constraints. All functions called from within the program fragment should
be pure. In particular, they should not change the values of loop iterators or arrays
other than through their output arguments. These requirements ensure that we can
represent all relevant information about the program using mathematical objects that
we will call polyhedral sets and relations. The name derives from related objects
called polyhedra [ 26 ] . The resulting parallel model, a variation on Kahn process
networks [ 9 , 11 ] , can then also be described using such polyhedral sets and relations,
whence the name polyhedral process networks .
The concept of a polyhedral process network was developed in the context of
the Compaan project [ 14 , 20 ] . The name was coined in [ 15 ] . The exposition in this
chapter closely follows that of [ 24 ] .

2Ov rv ew

This section presents a high-level overview of the process of extracting a process
network from a sequential program. The extracted process network represents the
task-level parallelism that is available in the program. The input program is assumed
to consist of a sequence of nested loops performing various “operations”. These op-
erations may be calls to functions that can be arbitrarily complicated. The operations
are performed on data that has been computed in some iteration of another operation
or in a previous iteration of the same operation. The output process network consists
of a set of processes, each encapsulating all iterations of a given operation, and
communication channels connecting the processes and representing the dataflow.
The processes in the network can be executed independently of each other, as long
as data is available from the channels from which the process reads and as long as
buffer space is available in the channels to which the process writes. That is, the
communication primitives implement blocking reads and blocking writes.

Example 1. As a simple example, consider the code for performing Sobel edge
detection in Fig. 1 . The first loop of this program reads the input image, while the

1 for(i=0;i<K;i++)
2 for(j=0;j<N;j++)
3 R: a[i][j] = ReadImage();
4 for (i = 1; i < K-1; i++)
5 for (j = 1; j < N-1; j++) {
6 S: Sbl[i][j] = Sobel(a[i-1][j-1], a[i][j-1], a[i+1][j-1],
7 a[i-1][ j], a[i][ j], a[i+1][ j],
8 a[i-1][j+1], a[i][j+1], a[i+1][j+1]);
9 W: WriteImage(Sbl[i][j]);
10

}

Fig. 1 Source code of a Sobel edge detection program