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$] ;