next up previous contents index
Next: I/O Up: A Distributed Array Communication Previous: Reductions   Contents   Index

Irregular collective communications

Adlib has some support for irregular communications in the form of collective gather() and scatter() operations. In general these methods have fairly unwieldly interfaces. Also their current implementation is far from optimal. If you find yourself using these methods extensively, it may be time to consider resorting to lower-level styles of parallel programming (as discussed for example in chapter 7). Or you may just need a different library...

The simplest form of the gather() operation for one-dimensional arrays has prototypes

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...,$\\
\verb$ int [[-]] subscripts)$
\end{tabbing}\end{minipage}\end{displaymath}

The subscripts array should have the same shape as, and be aligned with, the destination array. In terms of pseudocode, the behavior of the gather operation is like:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...source [subscripts [$$i$\verb$]] ;$
\end{tabbing}\end{minipage}\end{displaymath}

where $N$ is the size of the destination (and subscripts) array. If we are implementing a parallel algorithm that involves a stage like

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...verb$] = b [${\em fun(i)}\verb$] ;$
\end{tabbing}\end{minipage}\end{displaymath}

where fun is an arbitrary function, this can be expressed using Adlib as

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...
\verb$ Adlib.gather(a, b, tmp) ;$
\end{tabbing}\end{minipage}\end{displaymath}

where p and x are the distribution group and range of a. The source array, b, may have a completely unrelated mapping.

The one-dimensional case generalizes to give a fairly complicated family of prototypes for multidimensional arrays:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...  ...

Currently the highest rank of source array with a gather() method is 36.4. The source and destination arrays can have different ranks (just as they have unrelated distribution formats). But the destination and subscript arrays are all the same shape, and all are aligned with one another. The number of subscript array arguments is equal to the rank of the source array. If the rank of the destination array is $R$, the rather complicated general behaviour of these methods is:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$f...
...R-1}$\verb$],$ \\
\>\verb$...] ;$
\end{tabbing}\end{minipage}\end{displaymath}

where $(N_0, \ldots, N_{R-1})$ is the shape of destination array.

The basic scatter function has very similar prototypes, but the names source and destination are switched. For example the one-dimensional case is

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...\verb$ int [[-]] subscripts) ;$ \\
\end{tabbing}\end{minipage}\end{displaymath}

and it behaves like

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...i$\verb$]] = source [$$i$\verb$] ;$
\end{tabbing}\end{minipage}\end{displaymath}

Currently the HPJava version of Adlib does not support combining scatters, although these could be added in later releases.

All the gather() and scatter() operations take an optional final argument which is a boolean array acting as a mask, e.g.

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{tabbing}
\verb$ ...
...]] subscripts, boolean [[-]] mask)$
\end{tabbing}\end{minipage}\end{displaymath}

The mask should have the same shape as and be aligned with the subscript arrays. Assignment to a destination element is conditional on the value of the element of the mask associated with the subscripts.


next up previous contents index
Next: I/O Up: A Distributed Array Communication Previous: Reductions   Contents   Index
Bryan Carpenter 2003-04-15