Database Reference
In-Depth Information
windows, and we use OS-Split and OS-Join to implement an FFT-specific
stream partitioning strategy.
As an example of a window distribute strategy,
Round Robin stream par-
titioning
(RR) is provided where entire logical windows of streams are dis-
tributed based on the order in which they arrive. In the combine phase, the
result substreams are merged on their order identifier (in our application a
time stamp is used). This is an extension of the conventional Round Robin
partitioning
22
for data streams. Window distribute by Round Robin does not
decrease the size of logical windows, and therefore the compute phase of FFT
may run slower than with window split.
Figure 11.5 illustrates the use of window split and window distribute for
computing a three-dimensional FFT with the degree of parallelism two.
For example, the window distribute (b) and split (c) strategies are specified
with PCC as:
PCC(2,"S-Distribute","RRpart","FFT","S-Merge",0.1);
PCC(2,"OS-Split","FFTpart","FFT","OS-Join","FFTcombine");
The PCC constructor is parameterized on (1) the degree of parallelism
(degree 2); (2) partitioning method (
SDistribute
or
OS-Split
); (3) parame-
ter of the partitioning method (
RRpart
or
FFTPart
); (4) SQF to be computed
(FFT); (5) the combining method (
S-Merge
or
OS-Join
); and (6) parameters
of the combining method (e.g., 0.1, a time-out).
FFT
256
FFT
256
S-distribute
S-merge
FFT
256
FFT
256
(a)
FFT
64
FFT
64
OS-split
OS-join
FFT
64
FFT
64
(b)
Figure 11.5
(a) Central strategy, (b) Round Robin window distribute strat-
egy, (c) FFT-dependent window split strategy.