Subject: parallel prefix intrinsics

From: Guy Steele <[email-masked]>
Date: Wed, 6 May 92 14:44:58 EDT

Proposal for parallel prefix instrinsics for HPF

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 6, 1992

For every reduction operation XXX in the language, introduce two new
intrinsics XXX_PREFIX and XXX_SUFFIX.  They take the same arguments
as the corresponding reduction intrinsic, plus two additional
optional arguments:

	XXX_PREFIX(ARRAY, DIM, MASK, SEGMENT, EXCLUSIVE)
	XXX_SUFFIX(ARRAY, DIM, MASK, SEGMENT, EXCLUSIVE)

The first additional optional argument is called SEGMENT, which is of
type logical and conformable with the ARRAY argument (a TRUE element
indicates the start of a new segment of the first argument, that is,
a place where the running accumulation is to be reset before
processing the corresponding array element).

The second additional optional argument, a scalar logical, is called
EXCLUSIVE, default .FALSE., which determines whether the prefix or
suffix operation is inclusive (the default) or exclusive.  (The
inclusive sum-prefix of (/ 1,2,3,4 /) is (/ 1,3,6,10 /) whereas the
exclusive sum-prefix is (/ 0,1,3,6 /).)

Array elements corresponding to positions where the MASK is false
do not contribute to the running accumulation.  However, the result
is still defined for corresponding positions in the result.
In actual practice, results may not be required in those positions;
in such cases the programmer may be able to use the WHERE statement
to give the compiler a strong hint:

      WHERE (FOO) A=SUM_PREFIX(B,MASK=FOO)

If the DIM argument is omitted, then the arrays are processed in
array element order ("column-major"), as if temporarily regarded as
one-dimensional.

In all cases the result has the same shape as the first argument.

In addition, the operation COPY_PREFIX replicates the first
(lowest-indexed) element of each segment throughout the segment, and
the operation COPY_SUFFIX replicates the last (highest-indexed)
element of each segment throughout the segment.

Examples:

SUM_PREFIX( (/1,3,5,7/) ) yields (/1,4,9,16/)
SUM_SUFFIX( (/1,3,5,7/) ) yields (/16,15,12,7/)

      LOGICAL T,F
      PARAMETER (T = .TRUE., F = .FALSE. )      !just for conciseness

COUNT_PREFIX( (/T,F,F,T,T,T,F,T,F/) )              yields (/1,1,1,2,3,4,4,5,5/)
COUNT_PREFIX( (/T,F,F,T,T,T,F,T,F/), EXCLUSIVE=T ) yields (/0,1,1,1,2,3,4,4,5/)

SUM_PREFIX( (/1,2,3,4,5,6,7,8,9/),
    SEGMENT=(/T,F,F,F,T,F,T,T,F/)) yields (/1,3,6,10,5,11,7,8,17/)
              ------- --- - ---             -------- ---  - ----
	     four input segments       four independent result segments

COPY_PREFIX( (/1,2,3,4,5,6,7,8,9/),
     SEGMENT=(/T,F,F,F,T,F,T,T,F/)) yields (/1,1,1,1,5,5,7,8,8/)
               ------- --- - ---             ------- --- - ---
	      four input segments       four independent result segments

Outstanding issues: This proposal delimits the segments by indicating
the *start* of each segment.  Cray MPP Fortran delimits the segments
by indicating the *stop* of each segment.  Each method has its advantages.
There is also the question of whether this convention should change when
performing a suffix rather than a prefix.

Another way to delimit segments is to use a logical vector and say
that a new segment begins at every *transition* from false to true or
true to false; thus a segment is indicated by a maximal contiguous
subsequence of like logical values:

	(/T,T,T,F,T,F,F,F,T,F,F,T/)
          ----- - - ----- - --- -    seven segments

The main advantages of this representation are:

(a) It is symmetrical, in that the same segment specifier may
    be meaningfully used for parallel prefix and parallel suffix
    without changing its interpretation (start versus stop).

(b) It seems to be equally inconvenient for every existing
    architecture.  :-)  However, it is not that hard to accommodate.

(c) The start-bit or stop-bit representation is easily converted
    to this form by using a parallel XOR prefix or suffix.
    Of course, we would need to define one (see separate proposal
    for a PARITY reduction intrinsic).  Examples:

    SUM_PREFIX(FOO,SEGMENT=PARITY_PREFIX(START_BITS))
    SUM_PREFIX(FOO,SEGMENT=PARITY_SUFFIX(STOP_BITS))
    SUM_SUFFIX(FOO,SEGMENT=PARITY_SUFFIX(START_BITS))
    SUM_SUFFIX(FOO,SEGMENT=PARITY_PREFIX(STOP_BITS))

    These might be standard idioms for a compiler to recognize.