Polyhedral Process Networks - Signal Processing Systems - page 1344

iteration domain, while the second process has a two-dimensional iteration domain.
The mapping on the channel ( 12 ) shows that there is a relation w r 2 between the

single iterator of the writing process and the second iterator of the reading process.
We therefore insert a zero before the iteration vectors of the writing process such
that the original iterator ends up in the second position. For the channel between
a and c the relation is w

=

r 1 , so in this case we insert a zero after the original
iterator. These choices are reflected by the orientations of these two one-dimensional
iteration domains in Fig. 11 . With these orientations, the writes may be moved on
top of the corresponding reads by simply shifting the iteration domains, meaning
that a buffer size of at most 1 is needed. Had we chosen a different orientation for
the two one-dimensional iteration domains, then this would not have been possible.

=

8 Buffer Size Computation

This section describes how to compute valid buffer sizes for all communication
channels. The buffer sizes are valid in the sense that imposing them does not cause
deadlocks. The first step is to compute a global schedule for all processes in the
network, e.g., using the techniques of Sect. 7 . This scheduling step effectively makes
all communication channels internal (to the single combined process). We then
compute buffer sizes for this particular schedule. The schedule itself is not used
during the actual execution of the network. However, we know that there is at least
one schedule for which the buffer sizes are valid. The blocking reads and writes on
the communication channels will therefore not introduce any deadlocks.

8.1 FIFOs

We are given an internal communication channel that has been identified as a FIFO
using the technique of Sect. 6.1 and we want to know how much buffer space is
needed on the FIFO. Recall that any channel may be considered internal after a
global scheduling step that maps all iteration domains to a common iteration space.
The buffer should be large enough to hold the number of tokens that are in transit
between a write and a read at any point during the execution. We therefore first
count this number of tokens in terms of an arbitrary iteration and then compute an
upper bound over all iterations.
Let us look at these steps in a bit more detail. The communication channel is
described by a mapping M from the write iteration domain D w to the read iteration
domain D r . The maximal number of tokens in the buffer will occur after some write
to the buffer and before the first subsequent read from the buffer. It is therefore
sufficient to investigate what happens right before a token is read from the buffer.
Let W be the relation mapping any read iteration r to all write iterations that occur