Polyhedral Process Networks - Signal Processing Systems - page 1312

Fig. 2 A process network corresponding to the sequential program in Fig. 1

second loop performs the actual edge detection and writes out the output image.
A process network that corresponds to this program is shown in Fig. 2 . Thereare
three processes in the network, each corresponding to one of the three “operations”
performed by the program, i.e., reading, edge detection and writing. Data flows
from the reading process to the edge detection process and from the edge detection
process to the writing process, resulting in the communication channels shown in
the figure. The annotations on the edges will be explained later.

The extraction of a polyhedral process network consists of several steps summa-
rized below and explained in more detail in the following sections:
￿ In a first step, a model is extracted from the input program on which all

further analysis will be performed. In particular, the program is represented by a
polyhedral model . This model allows for an efficient analysis, but imposes some
restrictions on the input programs. The polyhedral model is explained in Sect. 3 ,
while some basic components for the analysis of polyhedral models are explained
in Sect. 4 .

￿ Dataflow analysis is performed to determine which processes communicate with

which other processes and how, i.e., to determine the communication channels.
For example, the results of the call to ReadImage in Line 3 of Fig. 1 are
stored in the a array, which is read by the call to Sobel in Line 6. Dataflow
analysis therefore results in one or more communication channels from the
reading process to the edge detection process. Dataflow analysis is explained
in Sect. 5 .

￿ In the next step, the type of each communication channel is determined. For

example, the channel may be a FIFO, in which case the processes connected to
the channel simply need to write to and read from the channel, or it may not be a
FIFO, in which case additional processing will be required. The classification of
channels is discussed in Sect. 6 .

￿ The communication channels may need to buffer some data to ensure a deadlock-

free execution of the network. Especially for a hardware implementation of
process networks, it is important to know how large these buffers may need to
grow. The computation of buffer sizes is the subject of Sect. 8 .