Optimization for block distribution formats

For the most straightforward, block-based distribution formats--these include arrays parameterized BlockRange, ExtBlockRange and IrregRange, there is a fairly straightforward optimization. We can do prefix computation within individual blocks, then do a global exclusive prefix combining the sums of the blocks. Finally we add the global prefix back to the incomplete prefixes within the blocks. This is illustrated in Figures 7.17, 7.18.

Figure 7.17: Parallel prefix optimized for block-wise distribution formats.

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}stat... ...l ;as [k, sub] += sum ; } } }\end{verbatim}\end{minipage}$$

Figure 7.18: Prefix optimized for block distributions: illustration for N = 8, P = 3.

This version has a hope to be reasonably efficient if $N \gg P$, so arithmetic costs have a chance to dominate communication cost. It still does about $2N$ total additions operations instead the $N$ operations for the sequential code. But in principle if $P > 2$ it should be possible to compensate for this factor, and gain some parallel speedup.

The code given here will work for the ranges mentioned above, and subranges of these^7.5. It will not work for cyclic distributions.