From: Guy Steele <[email-masked]>
Date: Wed, 20 May 92 18:03:58 EDT

Proposal for parallel prefix instrinsics for HPF

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 20, 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.  If present,
the array is divided into pieces

 (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 every case, every element of the result has a value equal to the
reduction of certain selected elements of ARRAY, or an "identity
value" (zero for SUM_PREFIX or SUM_SUFFIX, for example) if no
elements of ARRAY are selected for that result element.  The optional
arguments affect the selection of elements of ARRAY for each element
of the result; the selected elements of ARRAY are said to contribute
to the result element.

For any given element R of the result, let A be the corresponding
element of ARRAY.  Every element of ARRAY contributes to R unless
disqualified by one of the following rules.

For xxx_PREFIX, no element that follows A in the array element
ordering of ARRAY contributes to R.  For xxx_SUFFIX, no element that
precedes A in the array element ordering of ARRAY contributes to R.

If the DIM argument is provided, an element Z of ARRAY does not
contribute to R unless all its indices, excepting only the index for
dimension DIM, are the same as the corresponding indices of A.

If the MASK argument is provided, an element Z of ARRAY does
not contribute to R if the element of MASK corresponding to
Z is false.

If the SEGMENT argument is provided, an element Z of ARRAY does not
contribute unless the elements B and Y of SEGMENT corresponding to A
and Z (respectively), and the intervening elements of SEGMENT as
well, all have the same value.  If the DIM argument is not present,
then the "intervening" elements are all elements between them in
array element order; if the DIM argument is present, then the
"intervening" elements are those having indices the same as those of
both B and Y, except the index for dimension DIM, which must be
between (and possibly equalling) the indices of B and Y for dimension
DIM.  In other words, the prefix or suffix operation is performed
on groups of elements of ARRAY, where a group corredponds to a
maximal contiguous run of like-valued elements of SEGMENT.

If the EXCLUSIVE argument is provided and is true, then A itself
does not contribute to R.

In addition to all this, 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,T,T,T,F,F,T,F,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,T,T,T,F,F,T,F,F/)) yields (/1,1,1,1,5,5,7,8,8/)
               ------- --- - ---             ------- --- - ---
	      four input segments       four independent result segments

Note: Connection Machine software 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.

HPF adopts yet a third representation: 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:intrinsics-prefix-proposal, version 2

	(/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.