next up previous contents
Next: Schedules Up: A distributed array communication Previous: Reductions   Contents

Irregular collective communications

Adlib has some support for irregular communications in the form of collective gather and scatter operations. The simplest form of the gather operation for one-dimensional arrays has prototypes


    void gather($T$ [[]] destination, $T$ [[]] source, int [[]] subscripts) ;
The subscripts array should have the same shape as, and be aligned with, the destination array. In pseudocode, the gather operation is equivalent to

    for all $i$ in $\{0, \ldots, N-1\}$ in parallel do 

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

    for all $i$ in $\{0, \ldots, N-1\}$ in parallel do 

a [$i$] = b [fun(i)] ;
where fun is an arbitrary function, it can be expressed in HPJava as

    int [[]] tmp = new int [[x]] on p ; 

on(p)
overall(i = x for :)
tmp [i] = fun(i) ;

Adlib.gather(a, b, tmp) ;
where p and x are the distribution group and range of a. The source array may have a completely unrelated mapping.

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


    void gather($T$ [[]] destination, $T$ [[]] source, 

int [[]] subscripts) ;
void gather($T$ [[,]] destination, $T$ [[]] source,
int [[,]] subscripts) ;
void gather($T$ [[,,]] destination, $T$ [[]] source,
int [[,,]] subscripts) ;
...
void gather($T$ [[]] destination, $T$ [[,]] source,
int [[]] subscripts1, int [[]] subscripts2) ;
void gather($T$ [[,]] destination, $T$ [[,]] source,
int [[,]] subscripts1, int [[,]] subscripts2) ;
void gather($T$ [[,,]] destination, $T$ [[,]] source,
int [[,,]] subscripts1, int [[,,]] subscripts2) ;
...
...
The complexity arises because now that the source and destination arrays can have different ranks. The pattern is that the subscript arrays have the same and alignment shape as the destination arrays. The number of subscript arrays is equal to the rank of the source array. As an example, the last of the prototypes enumerated above behaves like

    for all $i$ in $\{0, \ldots, L-1\}$ in parallel do 

for all $j$ in $\{0, \ldots, M-1\}$ in parallel do
for all $k$ in $\{0, \ldots, N-1\}$ in parallel do
destination [$i$, $j$, $k$] = source [subscripts1 [$i$, $j$, $k$],
subscripts2 [$i$, $j$, $k$]] ;
where $(L, M, N)$ is the shape of destination array.

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


    void scatter($T$ [[]] source, $T$ [[]] destination, 

int [[]] subscripts) ;
and it behaves like

    for all $i$ in $\{0, \ldots, N-1\}$ in parallel do 

destination [subscripts [$i$]] = source [$i$] ;


next up previous contents
Next: Schedules Up: A distributed array communication Previous: Reductions   Contents
Bryan Carpenter 2002-07-12