Polyhedral Process Networks - Signal Processing Systems - page 1337

6.3.2 Shift Registers

Another special case occurs when the number of iterations between a write to an
internal channel and the corresponding read from the channel is constant. If so, the
FIFO can be replaced by a shift register, shifting the data in the channel by one
in every iteration, independently of whether any data was read or written in that
iteration. Such shift registers can be implemented more efficiently than FIFOs in
hardware.
Checking whether we can use a shift register is as easy as writing down the
relation

d

R = { w → i |∃ r ∈ Z : ( w → r ) ∈ M ∧ i ∈ D ∧ w ≺ i ≺ r },

where M is the mapping on the channel and D is the iteration domain of the process,
and applying Operation 3 (Number of Image Elements). The result is a piecewise
quasi-polynomial q of type

n d

,where n is the number of parameters. If
the expression is independent of the last d variables, i.e., if q is defined purely in
terms of the parameters and not in terms of the write iterators, then we can use a
shift register. Note that we also count iterations in which no value is read from or
written to the channel. This means that the size of the shift register may be larger
than the buffer size of the FIFO, as computed in Sect. 8 .

Z × Z → Q

7 Scheduling

Although the processes in a process network are scheduled independently during
their execution, there are two occasions where we may want to compute a common
schedule for two or more processes. The first such occasion is when there are more
processes in the network than there are processing elements to run them on. The
second is when we want to compute safe buffer sizes as will be explained in Sect. 8 .
In principle, we could use the original schedule from Sect. 3.3 as the common
schedule, resulting in the same execution order as that of the input sequential
program. This schedule may lead to very high overestimates of the buffer sizes,
however, and we therefore prefer constructing a schedule that is more suited for the
buffer size computation. There are many ways of obtaining such a schedule. Below
we discuss a simple incremental technique.

7.1 Two Processes

Let us first consider the case where there are only two processes, P 1 and P 2 ,that
moreover have the same dimension d

= =

d 2 . We will relax these conditions in
Sects. 7.2 and 7.4 . For ease of notation, we will not work with a separate schedule,

d 1