next up previous contents
Next: General subscripting in array Up: Patterns of communication Previous: Stencil problems and ghost   Contents

Reductions and other transformational intrinsics

Fortran implementations come with a set of built-in functions and subroutines called the intrinsics. The transformational intrinsics are a subset of the intrinsics that peform functions on whole arrays, sometimes returning whole array results. In HPF these functions can operate on distributed arrays, implying new patterns of communication.

Some of the transformational intrinsics just reshuffle elements of arrays in regular ways. For example if the CSHIFT, EOSHIFT, TRANSPOSE and SPREAD intrinsics are applied to distributed arrays, they imply patterns of data remapping that are quite similar to patterns in the array assignments of section 1.1. The reduction intrinsics, including SUM, PRODUCT, MAXVAL, MINVAL, ALL, ANY and several others, introduce qualitatively different communication patterns. They reduce an array either to a scalar or a lower-rank array by arithmetically combining elements along some or all dimensions. Typically the associated communications occur on some spanning tree. In MPI terms they are related to, and might be implemented in terms of, MPI_REDUCE.

Parallel prefix operations can also be expressed. The HPF standard includes them as standard library functions (rather than intrinsics). They can also be expressed in terms of FORALL statements:

      FORALL (I = 1 : N)  RES (I) = SUM(A (1 : I))
The $i$th element of the result contains the sum of all elements in A up to and including its $i$th element. The pattern of communication needed to implement the prefix algorithm efficiently is different to the one used in global reduction operations2. In MPI terms parallel prefixes are related to, and might be implemented in terms of, MPI_SCAN.


next up previous contents
Next: General subscripting in array Up: Patterns of communication Previous: Stencil problems and ghost   Contents
Bryan Carpenter 2002-07-12