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.
Search WWH ::




Custom Search