Subject: Questions

From: Rob Schreiber <[email-masked]>
Date: Tue, 12 May 92 14:41:24 PDT

Dear members of the Intrinsics subcommittee:

We have a number of proposals on the table.   Now we need to begin a
debate on them, or we will be forced to have a meeting sometime.   I
hope we can avoid all but a short meeting on June 8.

First, here are the intrinsics that have been proposed.    VOTE up
or down (this is a straw poll) on whether to include them in
some form, and give Guy some help on his questions:

------------------------------------------------------
  POPCNT

  POPPAR

  LEADZ

  ILEN

Issues: I hope I have defined POPCNT, POPPAR, and LEADZ consistent
with their use in Cray Fortran.  I believe that Cray Fortran allows
these intrinsics to be applied to data types other than integers;
should HPF allow this also?

------------------------------------------------------
  extended MAXLOC   (with DIM argument)

  extended MAXLOC   (with DIM argument)

------------------------------------------------------

New reductions:

	AND
	OR
	EOR
	PARITY

------------------------------------------------------

For each reduction intrinsic XXX, introduce the parallel prefix and suffix
intrinsics:

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

(The possible values of XXX are:

	 SUM, PRODUCT, ALL, ANY, MAXVAL, MINVAL, AND, OR, EOR, PARITY.)

On PREFIX and SUFFIX:

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

------------------------------------------------------

For each reduction intrinsic XXX, introduce the send with combination
intrinsic:

	XXX_SEND(SOURCE,DEST,IDX1,...)

------------------------------------------------------

Sorting:

	GRADE_UP(ARRAY,DIM)

	GRADE_DOWN(ARRAY,DIM)

>>>	Question: should stability be guaranteed?

The alternative:

	INDEX(ARRAY,SUBS)

	GRADE(ARRAY1,ARRAY2,...)

------------------------------------------------------

	NUMBER_OF_PROCESSORS()  with optional DIM argument

The alternative:

	NUMBER_OF_PROCESSORS()  with no optional DIM argument and
	PROCESSORS_SHAPE()

Question:  Should these be allowed for processor_arrangements in HPF 
directives?

------------------------------

---

From: Richard Shapiro <[email-masked]>
Date: Thu, 14 May 92 12:22:49 EDT

Date: Tue, 12 May 92 14:41:24 PDT
   From: Rob Schreiber <[email-masked]>

   ------------------------------------------------------
     POPCNT
Yes, but can it be POPCOUNT?

     POPPAR
Maybe, it's the same as IAND(POPCNT,1)

     LEADZ
Yes

     ILEN
Yes

No. I don't believe we should open a can of worms and get into
floating-point representation.

Absolutely

   New reductions:

	   AND
	   OR
	   EOR
	   PARITY
Yes

Yes

   >>>    These might be standard idioms for a compiler to recognize.

I like the alternating sequence method as well. I have never been able to
get segmented scans right on the CM-2 without much confusion and many
minutes with a manual.

Yes. I'm not sure how usefule product is, but it's better to have it than
to make an assymetric restriction.

   Sorting:

	   GRADE_UP(ARRAY,DIM)

	   GRADE_DOWN(ARRAY,DIM)

How about just GRADE(array,dim,direction)?

   >>>	Question: should stability be guaranteed?

Stability is a very useful property. Yes.

   The alternative:

	   INDEX(ARRAY,SUBS)

	   GRADE(ARRAY1,ARRAY2,...)

Don't like this as much.

I like this method...

   The alternative:

but could certainly live with this method.

Yes, otherwise the usefulness is very limited.