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(`` [[]] destination, `` [[]] 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 `` in `` in parallel do`
`      destination [``] = source [subscripts [``]] ;`
```
where is the size of the destination (and subscripts) array. If we are implementing a parallel algorithm that involves a stage like
```
`    for all `` in `` in parallel do`
`      a [``] = 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(`` [[]] destination, `` [[]] source,`
`                int [[]] subscripts) ;`
`    void gather(`` [[,]] destination, `` [[]] source,`
`                int [[,]] subscripts) ;`
`    void gather(`` [[,,]] destination, `` [[]] source,`
`                int [[,,]] subscripts) ;`
`    ...`
`    void gather(`` [[]] destination, `` [[,]] source,`
`                int [[]] subscripts1, int [[]] subscripts2) ;`
`    void gather(`` [[,]] destination, `` [[,]] source,`
`                int [[,]] subscripts1, int [[,]] subscripts2) ;`
`    void gather(`` [[,,]] destination, `` [[,]] 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 `` in `` in parallel do`
`      for all `` in `` in parallel do`
`         for all `` in `` in parallel do`
`           destination [``, ``, ``] = source [``subscripts1 [``, ``, ``],`
`subscripts2 [``, ``, ``]] ;`
```
where 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(`` [[]] source, `` [[]] destination,`
`                 int [[]] subscripts) ;`

```
and it behaves like
```
`    for all `` in `` in parallel do`
`      destination [subscripts [``]] = source [``] ;`
```

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