Array Communicaton Library

Bryan Carpenter University of Southampton

December 12, 1991

Motivation

Puma architecture provides efficient point-to-point communications. In data-parallel applications many more elaborate communication patterns recur frequently. Regard these as more global operations: rearrangements of or simple arithmetic transformations on distributed data.

• “Array” in ACL refers to process array: library operates within arbitrary-dimensional arrays of processes.

• Level is somewhere between low-level communication libraries and libraries providing specialised support for particular applications, or specific distribution strategies for data arrays.

Process Arrays

Each logical direction has a structure called an “index” associated with it, e.g., x, y and z.

Interface

• Index structures are passed to communication routines in much the same way as channels in occam. For example

     PERM.SHIFT (x, result, data, 3)

shifts the values in ‘data’ 3 sites in the ‘x’ direction, and returns the shifted values in ‘result’.

• The index structure also contains the coordinate value for the local process associated with the index direction:

     local_x = INDEX.coord (x)

Implementations

• In the occam/VCR implementation of ACL any two sites connected by an index have a virtual channel between them.

• The data structure embodying an index contains vectors of these channels.

• The channels are hidden from the user of the communication library. Thus the same library interface can be provided in non-channel-oriented communication environments.

Selected Entry Points

PERM.DS            -- arbitrary permutation.
PERM.SHIFT         -- a particular permutation.
RELATE.DS          -- a generalised permutation.
BROADCAST          -- and variants.
PREFIX.REAL32.SUM  -- and other prefixes
GLOB.REAL32.SUM    -- and other reductions.

Example—toy FFT

SEQ b = 0 FOR d
VAL p        IS 1 << b :
VAL odd.site IS ((INDEX.coord (x) / p) /\ 1) = 1 :
[2] REAL32 import :
SEQ
  IF
    odd.site
      twiddle (datum, x \ p, p)
    TRUE
      SKIP
  PERM.XOR (x, import, datum, p)
  IF
    odd.site
      datum := [import [0] - datum [0], import [1] - datum [1]]
    TRUE
      datum := [import [0] + datum [0], import [1] + datum [1]]

Array Communication Library 7

Example—optimal matrix multiplication

SEQ
INDEX.broadcast (y, a, 0)
INDEX.broadcast (x, b, 0)
matmul (c, a, b, m, l, n)
MERGE.EL.REAL32.VEC.SUM (z, C, c, 0)

I/O

• As well as operations for communication within a particular process array, the library has a sophisticated set of routines for sequential I/O.

• These allow a process array to talk to an external process (e.g., a master or host process, or other process arrays—perhaps an array of graphics processors, etc).

• For these purposes a second type of communication structure is introduced—a logical “distributed channel”.

Mixing indices and distributed channels Configuration

• With static process configuration the channel connectivity of the networks is exposed to the user in the configuration file. This is a failure of abstraction—the underlying virtual channels are supposed to be hidden (transparent).

• By configuring “procedurally”—using the dynamic features of VCR—have possibility of hiding channels completely. Also, this run-time configuration is more flexible.

Dynamic Configuration

• The implemented ACL primitives for dynamic configuration use the remote procedure call, dynamic channel creation, and channel-moving operations provided in VCR.

• One of the most important operations for dynamic configuration is “channel-copying”. Given a virtual channel connecting two processes, the channel-copying operation creates a new, independent, virtual channel connecting the same processes.

Spawning of an “All-to-All” Network

Array Communication Library 13