Subject: Working Group 4 - Issues for discussion

From: [email-masked]
Date: Fri, 20 Mar 92 11:05:54 -0600

Hello, group -

The following is my first cut at defining the issues for group 4.
Unfortunately, my original notes from the meeting have disappeared.
Please add to this list if you see obvious omissions.  In short, I'm
looking for volunteers to write up position papers outlining the
issues.  These should give us a good basis to work from at the next
meeting and into the future.

Our Charter:  

To examine issues relating to FORALL loops and local subroutines in
HPF.  In particular, the following issues were identified in the
general HPFF meeting:
	Should HPF have local blocks & subroutines?
	Should HPF have control parallelism?
	Should HPF interface with PCF parallel sections, and if so,
	    how?
	Should HPF have local data (i.e. private to a processor)?
	Should HPF have a multistatement FORALL, and if so what should
	    its semantics be?
	Should HPF have explicit processor control, and if so how
	    should this be done?
	Should HPF have SCAN intrinsics?

In addition, the following issues emerged in the working group
meeting:
	Should FORALL have a new semantics (ala CM Fortran FORALL), or
	    should it be an assertion (ala Cray directives)?  Or
	    perhaps both should be supported?
	What is the relationship between FORALLs and PCF DOALL loops?
	What is the relationship between local subroutines (local
	    sections) and PCF PARALLEL SECTIONs?
	Are local sections actually portable to SIMD and MIMD
	    machines?  If not, are there restrictions that will make
	    them portable?
	What is the relationship between local sections and the open
	    interface to other paradigms?

Getting the discussion rolling:

I think the right way to start meaningful electronic discussion is for
someone to volunteer to write a white paper on one or more of the
issues.  (Writing strawman proposals is a variation of this; I prefer
white papers since they tend to make the options explicit.)  Below are
some possible constellations of issues that could be discussed.  I'll
put something together for the first one; will others volunteer for
other tasks?

Paper 1:  Advanced FORALL loops
	Which style of parallel loop do users want?
	    A command: "Do this in parallel, whether safe or not!"
	    A new statement: "Do this in parallel, using XXXX
		semantics to resolve races!"
	    An unchecked assertion: "This is safe to do in parallel,
		trust me!"
	    A checked assertion: "I think this is safe to do in
		parallel, but check it anyway."
	Which of the above can HPF efficiently support on all
	    machines?
	What semantics do users want in a multi-statement FORALL?
	    SIMD semantics (synchronize at every statement)
	    Copy-in, copy-out (Fortran D)
	    Undefined in case of races
	    Partially defined (guarantee serializability, for example)
	Which of the above can HPF efficiently support on all
	    machines?

Paper 2:  Local Sections and Subroutines
	Actually, I think Guy's original proposal was very good.
	Maybe he could just post it, or the latest version if he has
	    made some modifications.

Paper 3:  Relation to PCF
	How do FORALL and DOALL compare?
	How do local subroutines and PARALLEL SECTIONs compare?
	Are the PCF extensions portable to distributed memory and SIMD
	    machines?
	Should HPF adopt any of the PCF extensions?  If so, which ones?
	Should HPF explicitly reject any of the PCF extensions?  If
	    so, which ones?

Paper 4:  Processor Control
	(This one probably can't be done in much detail until Group 2
	    presents their model for data distribution.)
	What do users want in the way of process control?
	    ON clauses for loops
	    SPMD paradigm
	    Inquiry functions for "current processor id" and similar
		information
	    Explicit synchronization
	    Explicit communication
	    Explicit multi-threading on a single processor
	Which of the above can HPF efficiently support on all
	    machines?
	Can processor control be better accomplished by open
	    interfaces to other paradigms?  If so, how can we define
	    the interface so that it is portable?

Paper 5:  Odds and Ends
	Do users want data private to a processor?
	Do users want SCAN intrinsics?
	Do users want parallel I/O?  If so, what do they mean by that?
	Do users want system inquiry functions?  If so, which ones?
	For each "yes" answer to the above, can HPF provide efficient,
	    portable support for that feature?

Optional: Let me know if you're interested in doing some writing.
Mandatory: If you write up a position paper, post it to this list for
discussion.

Hope to hear from you all soon!

						Chuck

---

From: Guy Steele <[email-masked]>
Date: Fri, 27 Mar 92 13:14:05 EST

Attached is a revised proposal for local subroutines.  It specifies
the behavior of local subroutines in the face of distributions other
than BLOCK; addresses the treatment of replicated distributions; and
briefly discusses interactions with Fortran 90 pointers and modules.
--Guy

----------------------------------------------------------------
Proposal for local program units in HPF

Guy L. Steele Jr.
Thinking Machines Corporation
Version of 25 March 1992

The basic idea is to add a new kind of program unit, called a LOCAL
program unit.  If an HPF program is running on multiple processors,
then invocation of a LOCAL program unit causes one copy of the
program unit to be executed within each processor.  The code of a LOCAL
can access any data within the processor using Fortran
array-reference syntax; it can also use array notation, but only to
operate on data within the processor.  To access data outside the
processor requires either preparatory communication before running
the LOCAL code, or the use of communications primitives such as a
message-passing library.  (The nature of such a message-passing
library is outside the scope of this proposal.  Furthermore, local
subroutines have utility even in the absence of interprocessor
communication within local code.)

A LOCAL program unit is not permitted to invoke a non-LOCAL program
unit.  (One consequence of this rule is that if the main program is
LOCAL, then the entire executable program must be LOCAL.  This might
come in handy in some cases or for some architectures!)  A LOCAL
subroutine or function may be invoked from within LOCAL code, with
everything behaving as if it were ordinary Fortran code running on a
single processor.

A transition from global execution to local execution occurs whenever
a LOCAL subroutine is invoked from non-LOCAL (that is, "global") HPF
code.  When this occurs, all global arrays accessible to the
subroutine (notably arrays passed as arguments) are logically carved
up into pieces; the copy of the local subroutine executing on a
particular physical processor sees an array containing just those
elements of the global array that are mapped to that physical
processor.

In the previous draft of this proposal, it was assumed that all
distributions were BLOCK.  This version assumes only that array axes
are mapped independently to axes of a rectangular processor grid,
each arrays axis to at most one processor axis (no "skew"
distributions) and no two array axes to the same processor axis.  But
the mapping of an array axis to a processor axis may be any mapping
whatsoever: block, cyclic, block-cyclic, reversed, vector-indexed, or
whatever.  This restriction suffices to ensure that each physical
processor contains a subset of array eleemnts that can be locally
arranged in a rectangular configuration.  (Of course, to compute the
global indices of an element given its local indices, or vice versa,
may be quite a tangled computation--but it will be possible.)

Now for the details:

Any program unit in an HPF program may have the keyword LOCAL at the
start of its first statement (in the case of a main program, the
PROGRAM statement):

      LOCAL SUBROUTINE PAUL_SIMON(A, B, C)
      LOCAL INTEGER FUNCTION BOY_GEORGE(X)
      LOCAL PROGRAM NELLIE_MELBA

The intent is that such a subprogram unit can be compiled in a
special way.  In a machine (such as the CM-5) that has a central
control processor directing the actions of the mass of individual
parallel processors, *all* the code of a LOCAL program unit runs on
the individual processors; operations that might normally be carried
out in the control processor are all compiled for the individual
processors.  Local subprograms may use array notation.  If the
individual parallel processors have vector hardware, for example,
then one would expect that such per-processor array code would be
compiled into per-processor vector operations, etc.

A local program unit is executed on a processor and executes
asynchronously and independently of all other processors.  With the
exception of returning from a local subroutine to the global caller
that initiated local execution (see below), there is no implicit
synchronization of processors.  So a local program unit may use any
control structure whatsoever.

A local program unit can call a local subprogram (subroutine or
function).  This behaves as an ordinary Fortran subprogram call.

One may also call a local subprogram from a global program unit; this
is how local execution is initiated in the first place.  (If the main
program is LOCAL, then it is as if the many local copies of the main
program had been initiated by an unseen global caller.)  When local
execution is initiated, one subprogram call occurs within each
physical processor.  The following special rules apply:

(1) Scalar parameters are broadcast, so that each processor sees a
copy of the scalar parameter.  However, we preserve the model that
allows parameter passing to be either copy-in/copy-out or by
reference, which has the following consequences.  If more than one
processor assigns to that parameter, then the value seen by the
caller is undefined.  If exactly one processor assigns to that
parameter, then the caller will see that value in the actual
argument, but if any other processor examines the parameter, the
value seen will be undefined.  So it is best to code a local
subroutine in such a way that each scalar parameter is either (a) treated
as read-only, or (b) accessed by exactly one processor.

(2) Array parameters are broken up into subgrids, and the subprogram
on a given processor receives as its argument an array (of the same
rank as the argument) representing the subgrid of elements residing
on that processor.  So if you have a 50x50 global array on a
16-processor machine, using a 4x4 processor layout with BLOCK
distribution on each axis, then each axis of length 50 will be
divided into three blocks of 13 and a final block of 11:

	processor 1:  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13
	processor 2: 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26
	processor 3: 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
	processor 4: 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50

So most of the processors will receive a 13x13 array as argument;
three will see 13x11 arrays; three will see 11x13 arrays; and one
will see an 11x11 array.  With a CYCLIC distribution on each axis,
then each axis of length 50 would be distributed so that the first
two processors along the axis would receive 13 elements and the last
two processors would receieve 12 elements:

	processor 1:  1,  5,  9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49
	processor 2:  2,  6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50
	processor 3:  3,  7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47
	processor 4:  4,  8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48

In this case four processors would receive 13x13 arrays; four
processors would receive 13x12 arrays; four processors would receive
12x13 arrays; and four processors would receive 12x12 arrays.

(3) As a local subprogram on a processor returns to a global caller,
the processor performs a synchronization function.  The result is
that the global caller proceeds only when *all* processors have
completed execution of the local subprogram.  (Following the
synchronization function, arrays with replicated distributions
must be brought up to date--see below.)

(4) In the case of a local function (as opposed to a subroutine), the
result of the call is a one-dimensional array of the results
(assuming the result of the function is nominally scalar).  The
length of this array is equal to the number of physical processors;
the array is distributed one element per processor according to a
BLOCK distribution of the single axis.
In the case of an array-valued local function, the ranks and shapes
of the arrays must be identical, and an extra dimension is appended.
So if you have 128 processors and each returns a 4x2 array, the
result is 4x2x128 and its distribution will be (*,*,BLOCK).
(It is expected that in many cases a call to a local function from
global code will be surrounded by a call to a reduction intrinsic
over the processor axis.)

Within a local subprogram, all the usual array inquiry intrinsics may
be used.  When applied to subgrids resulting from the breakup of a
global parameter, such intrinsics are naturally regarded as applying
to the local subgrid, because that is the array actually visible to
the local routine.  For example:

!GLOBAL CODE
      REAL A(50,50)
      CALL CINDI_LAUPER(A)

      ...

      LOCAL SUBROUTINE CINDI_LAUPER(X)
      REAL, ARRAY(:,:):: X
      N1 = SIZE(X,1)
      L1 = LBOUND(X,1)
      U1 = UBOUND(X,1)
      N2 = SIZE(X,2)
      L2 = LBOUND(X,2)
      U2 = UBOUND(X,2)
      ...

Assume 16 processors again, 4x4, with a CYCLIC distibution on the
first axis and a BLOCK distribution on the second axis.  (This is
expressed under the Thinking Machines directives proposal as

CHPF$PROCESSORS P(4,4)
CHPF$DECOMPOSITION D(50, 50)
CHPF$DISTRIBUTE D(CYCLIC,BLOCK) ONTO P
CHPF$ALIGN A(:,:) WITH D(:,:)

These are given here merely for concreteness.)

Then here are the values to which each processor would set N1, L1,
U1, N2, L2, and U2:

Key:	proc
	[N1, L1, U1]
	[N2, L2, U2]

	(1,1)		(1,2)		(1,3)		(1,4)
	[13,1,13]	[13,1,13]	[13,1,13]	[13,1,13]
	[13,1,13]	[13,1,13]	[13,1,13]	[11,1,11]

	(2,1)		(2,2)		(2,3)		(2,4)
	[13,1,13]	[13,1,13]	[13,1,13]	[13,1,13]
	[13,1,13]	[13,1,13]	[13,1,13]	[11,1,11]

	(3,1)		(3,2)		(3,3)		(3,4)
	[12,1,12]	[12,1,12]	[12,1,12]	[12,1,12]
	[13,1,13]	[13,1,13]	[13,1,13]	[11,1,11]

	(4,1)		(4,2)		(4,3)		(4,4)
	[12,1,12]	[12,1,12]	[12,1,12]	[12,1,12]
	[13,1,13]	[13,1,13]	[13,1,13]	[11,1,11]

[A piece of rationale:

There is a question as to what L and U should be: should they be
equal to the global array indices, so that a processor might see
indices from 1:13, or 14:26, or 27:39, or 40:50?  Or should they be
normalized to start at 1, so that each processor sees a range of 1:13
or 1:11?  The former is in some ways more elegant, but the latter may
be prone to fewer errors because old Fortran programmers tend to
assume *all* arrays start at 1.

If we assume that the call to the local subroutine on processor (2,3),
for example, should behave as an ordinary Fortran 90 subroutine
call whose argument is an array section representing the subgrid local
to that processor:

      CALL CINDI_LAUPER(A(14:26,27:39))   ! on processor (2.3)

then the Fortran 90 specification for assumed-shape arrays settles
the matter: Lj should be 1, and Uj should be L-1+SIZE(A,j).

End of rationale.]

Sometimes, however, it is useful to know the global dimension
information for an array.  A separate series of intrinsics,
GLOBAL_SIZE, GLOBAL_LBOUND, and GLOBAL_UBOUND may be applied to
arrays to determine their global extents.  In the CINDI_LAUPER
example above, GLOBAL_SIZE(X,1) would return 50.

The following intrinsics may also be desirable:

MY_PROCESSOR_INDEX(array, dim) returns the index of the processor
executing the call along the specified axis of the processors
arrangement onto which the given array was distributed.

PROCESSOR_SIZE(array, dim) returns the length of the specified axis
of the processors arrangement onto which the given array was
distributed.

GLOBAL_LOC(array, idx1, ..., idxn) takes an array of rank n and n
integer local indices; it returns an array of rank 1 and size n
containing the corresponding global indices of indicated array
element.

PROCESSOR_LOC(array, idx1, ..., idxn) takes an array of rank n and n
integer global indices; it returns an array of rank 1 and size n
containing the indices of the processor containing the indicated
array element.

GLOBAL_SHAPE and PROCESSOR_SHAPE are defined in terms of GLOBAL_SIZE
and PROCESSOR_SIZE in the same manner that SHAPE is defined in terms
of SIZE.  So in the CINDI_LAUPER example,

      GLOBAL_SHAPE(X) is (/ 50, 50 /)      on every processor
      PROCESSOR_SHAPE(X) is (/ 4, 4 /)     on every processor
      SHAPE(X) is (/ 13, 13 /)	     in 6 of the processors,
		  (/ 13, 11 /)	     in 2 of the processors,
		  (/ 12, 13 /)	     in 6 of the processors, and
		  (/ 12, 11 /)	     in 2 of the processors.

If a local program unit calls a local subprogram, then it may be that
a locally allocated array may be passed as a parameter; this is okay.
The GLOBAL_ and PROCESSOR_ intrinsics may be applied to an array that
was allocated locally.  The GLOBAL values are the same as the
non-GLOBAL values, and all elements turn out to be on a single
processor.  The same is true of an array that is not distributed (for
example, allocated in the control processor, if there is one).

      LOCAL SUBROUTINE KINKS()
      REAL, ARRAY(40,40):: YOU_REALLY_GOT_ME
      CALL CINDI_LAUPER(YOU_REALLY_GOT_ME)

Then:

GLOBAL_SIZE(YOU_REALLY_GOT_ME, 1)   = SIZE(YOU_REALLY_GOT_ME, 1)   = 40
GLOBAL_LBOUND(YOU_REALLY_GOT_ME, 1) = LBOUND(YOU_REALLY_GOT_ME, 1) = 1
GLOBAL_UBOUND(YOU_REALLY_GOT_ME, 1) = UBOUND(YOU_REALLY_GOT_ME, 1) = 40
GLOBAL_INDEX(YOU_REALLY_GOT_ME, 1)  = INDEX(YOU_REALLY_GOT_ME, 1)  = 1

You can't access array elements outside the local subgrid using
array notation.  It is necessary to use a communications library
to accomplish this.  The specification of a complete communications
and synchronization library is beyond the scope of this proposal,
but some simple examples might include:

      CALL ARRAY_FETCH(dest, global_source, i1, ..., in)
      CALL ARRAY_STORE(source, global_dest, i1, ..., in)

Thesewhich transfer a scalar (integer, logical, real, complex) from
source to dest.  The global operand must be the name of an array, and
the following arguments are integers that are used as indexes into
the global array of which the named array is presumably a subgrid.
(If it's a local array, it still works, but it obviously doesn't have
to go outside the executing processor!  It's probably a silly thing
to do, though, unless you're trying to use a general-purpose routine
on a local array.)  The intended CM-5 implementation is through the
use of messages that generate interrupts at the destination
processor; the interrupt routine services read and write requests.

Extended Examples

Here is some code that implements bitwise-AND reduction
on a one-dimensional array of integers:

      INTEGER FUNCTION BITAND(X)
      INTEGER, ARRAY(:):: X
      INTEGER, ARRAY(PROCESSOR_SIZE(X)):: PARTIAL_RESULTS
C  GET EACH PROCESSOR TO COMBINE ITS OWN VALUES AND DELIVER ONE RESULT EACH.
      CALL BITAND_WITHIN_PROCESSOR(X, PARTIAL_RESULTS)
C  NOW USE A BINARY TREE TO COMBINE ONE VALUE FROM EACH PROCESSOR.
C  CAREFUL FOOTWORK MAKES SURE THAT ANY SIZE WORKS, NOT JUST POWER OF 2.
      K = PROCESSOR_SIZE(X)
      DO WHILE (K .GT. 1)
	PARTIAL_RESULTS(1:K/2) = IAND(PARTIAL_RESULTS(1:K/2),         &
				      PARTIAL_RESULTS((K+1)/2):K)
	K = (K+1)/2
      END DO
      BITAND = PARTIAL_RESULTS(1)
      END

      LOCAL SUBROUTINE BITAND_WITHIN_PROCESSOR(X, PARTIAL_RESULTS)
      INTEGER, ARRAY(:):: X
      INTEGER, ARRAY(1):: PARTIAL_RESULTS
      INTEGER P
C  WITHIN A PROCESSOR, JUST DO A SERIAL LOOP TO AND THINGS UP
C  (THIS CODE ASSUMES NO VECTOR PROCESSING IS AVAILABLE).
      P = -1
      DO J = LBOUND(X),UBOUND(X)   ! LBOUND(X) will in fact be 1
	P = IAND(P, X(J))
      END DO
      PARTIAL_RESULTS(1) = P
      END

In a global program unit, COMMON means global common.  The keyword
COMMON may optionally be preceded by the word GLOBAL.

In a LOCAL program unit, COMMON means local common.  Global COMMON may
be specified by prefixing the word COMMON with the word GLOBAL.
The keyword LOCAL may also appear before the word COMMON.

      SUBROUTINE QUESTION_MARK
      COMMON /FOO/ TEARS(96)          !COULD ALSO HAVE SAID "GLOBAL COMMON"
      CALL THE_MYSTERIANS
      END QUESTION_MARK

      LOCAL SUBROUTINE THE_MYSTERIANS
      GLOBAL COMMON /FOO/ TEARS(96)   !EACH PROCESSOR HAS CEILING(96/N) ELEMENTS
      COMMON /BAR/ CRY(4)             !EACH PROCESSOR HAS 4 ELEMENTS
      LOCAL COMMON /BAZ/ TEARDROPS(10000000)  !EACH PROCESSOR HAS 1E7 ELEMENTS
					      ! (TOO MANY TEARDROPS :-)
      ...
      !EACH PROCESSOR ASSIGNS ONLY TO ITS OWN SUBSET OF THE TEARS.
      FORALL (J=1:UBOUND(TEARS,1)) TEARS(J) = CRY(1+(MOD(J,4))
      ...
      END THE_MYSTERIANS

Fortran 90 Pointers

Just as we prohibit the use of array subscript syntax from requiring
interprocessor communication in LOCAL code, so we must place
restrictions on the use of pointers.

We distinguish between global pointers and local pointers; wherever
the POINTER attribute may appear, the attribute GLOBAL POINTER or
LOCAL POINTER may potentially appear instead.  (The attribute POINTER
always means GLOBAL POINTER.)

It is forbidden for global code to dereference a local pointer or for
local code to dereference a global pointer.  

Global code may not not perform pointer assignment involving local
pointers.  Local code may perform pointer assignment involving local
pointers, including assigning a local pointer to a global pointer or
a global pointer to a local pointer (implementations may wish to
insert a run-time error check in the latter case to ensure that the
global pointer refers to an object that is in fact local to the
executing processor).

[Open question: should there similarly be a distinction between
LOCAL TARGET and GLOBAL TARGET?]

A communications library may provide for interprocessor data transfer
using Fortran 90 pointers.  For example, such a library might include
routines like:

      CALL POINTER_FETCH(dest, global_source)
      CALL POINTER_STORE(source, global_dest)

where the "global" arguments are global pointers.

Fortran 90 Modules

It should work out to declare a Fortran 90 module LOCAL.  I haven't
yet looked at all the details of this, but it seems clear that any
subprogram in a LOCAL module should be treated as LOCAL.

Updating Replicated Arrays

If an array has a replicated distribution, then we must specify what
happens when such an array is updated by local code.  We will specify
that for each element of such an array, from one synchronization
point to the next, no more than one processor may update it, and if a
processor does update it then no other processor should read it.
(In the absence of a communications library providing additional
synchronization functionality, the only synchronization point occurs
at the transition from local execution to global execution when all
instances of a local subprogram return to their global caller.)  All
copies of a replicated element should behave as if brought up to date
no later than the next synchronization point.

The LOCALLY Statement

locally-statement	  is  LOCALLY
			        declarations ???
			        block
			      END LOCALLY

This statement behaves as if its contents were the body of a local
subroutine invoked at that point, with all visible objects that
it uses passed as parameters of the same name.

You may not use LOCALLY within local code (there is no point),
even though you may call a local subroutine from local code.

So the above example could be written:

      INTEGER FUNCTION BITAND(X)
      INTEGER, ARRAY(:):: X
      INTEGER, ARRAY(PROCESSOR_SIZE(X)):: PARTIAL_RESULTS
C  GET EACH PROCESSOR TO COMBINE ITS OWN VALUES AND DELIVER ONE RESULT EACH.
      LOCALLY
	INTEGER P
C  WITHIN A PROCESSOR, JUST DO A SERIAL LOOP TO AND THINGS UP
C  (THIS CODE ASSUMES NO VECTOR PROCESSING IS AVAILABLE).
	P = -1
	DO J = LBOUND(X),UBOUND(X)
	  P = IAND(P, X(J))
	END DO
	PARTIAL_RESULTS(1) = P
      END LOCALLY
C  NOW USE A BINARY TREE TO COMBINE ONE VALUE FROM EACH PROCESSOR.
C  CAREFUL FOOTWORK MAKES SURE THAT ANY SIZE WORKS, NOT JUST POWER OF 2.
      K = PROCESSOR_SIZE(X)
      DO WHILE (K .GT. 1)
	PARTIAL_RESULTS(1:K/2) = IAND(PARTIAL_RESULTS(1:K/2),         &
				      PARTIAL_RESULTS((K+1)/2):K)
	K = (K+1)/2
      END DO
      BITAND = PARTIAL_RESULTS(1)
      END

---

From: Guy Steele <[email-masked]>
Date: Thu, 2 Apr 92 15:44:41 EST

Proposal for loops in HPF

Guy L. Steele Jr.
Version of 2 April 1992

This proposal recommends:

[1] Synchronized (SIMD-style) FORALL statement
    [a] Single-assignment, as in Connection Machine Fortran
    [b] Block FORALL
    [c] Allow statements other than assignments in body
        [i] WHERE
	[ii] FORALL
        [iii] ALLOCATE and DEALLOCATE
	[iv] Other?

[2] Directive for independent execution of iterations
----------------------------------------------------------------

[1] Synchronized (SIMD-style) FORALL statement

[a] Single-assignment, as in Connection Machine Fortran

      FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn [, mask] ) a(e1,...,em) = rhs

    The FORALL statement declares v1,v2,...,vn to be integer
    variables locally to the FORALL statement.  Associated
    with each is a subscript-triplet.  There is also an optional
    logical mask expression that may depend on the variables
    v1,v2,...,vn. The single statement controlled must be an
    assignment with an array reference on the left-hand-side.
    Each of the variables v1,v2...,vn must appear within the
    subscript expression(s) on the left-hand-side.  (This is
    a syntactic consequence of the semantic rule that no two
    execution instances of the body may assign to the same
    array element.)  The assignment statement is executed
    once for every combination of values for the variables
    for which the mask expression is true.  (If there is no
    mask expression, it is assumed always to be true.)
    The various instances of the assignment statement are
    executed in such a way that it appears that the right-hand
    sides of all instances, and also the subscript expressions
    on the left-hand-sides of all instances, and also the mask
    expression, are evaluated before any assignment is performed.
    So a FORALL statement is roughly equivalent to:

      templ1 = l1
      tempu1 = u1
      temps1 = s1
      DO v1=templ1,tempu1,temps1
	templ2(v1) = l2
	tempu2(v1) = u2
	temps2(v1) = s2
	DO v2=templ2(v1),tempu2(v1),temps2(v10
	  ...
	    templn(v1,v2,...,v<n-1>) = ln
	    tempun(v1,v2,...,v<n-1>) = un
	    tempsn(v1,v2,...,v<n-1>) = sn
	    DO vn=templn(v1,v2,...,v<n-1>),tempun(v1,v2,...,v<n-1>),tempsn(v1,v2,...,v<n-1>)
	    tempmask(v1,v2,...,vn) = mask
	    tempe1(v1,v2,...,vn) = e1
	    ...
	    tempem(v1,v2,...,vn) = em
	    temprhs(v1,v2,...,vn) = rhs
	    END DO
	  ...
	END DO
      END DO
      DO v1=templ1,tempu1,temps1
	DO v2=templ2(v1),tempu2(v1),temps2(v10
          ...
	    DO vn=templn(v1,v2,...,v<n-1>),tempun(v1,v2,...,v<n-1>),tempsn(v1,v2,...,v<n-1>)
	      IF (tempmask(v1,v2,...,vn)) THEN
		a(tempe1(v1,v2,...,vn),...,tempem(v1,v2,...,vn)) = temprhs(v1,v2,...,vn)
	      END IF
            END DO
          ...
        END DO
      END DO

Of course, there are other ways to implement it as well.

[b] Block FORALL

      FORALL (... e1 ... e2 ...)
	s1
	s2
	...
	sn
      END FORALL

means exactly the same as

      temp1 = e1
      temp2 = e2
      FORALL (... temp1 ... temp2 ...) s1
      FORALL (... temp1 ... temp2 ...) s2
      ...
      FORALL (... temp1 ... temp2 ...) sn

That is, a block FORALL means exactly the same as replicating
the FORALL header in front of each array assignment statement
in the block, except that any expressions in the FORALL header
are evaluated only once, rather than being re-evaluated before
each of the statements in the body.

Thus one may wish to think of a block FORALL as synchronizing twice
per contained statement: once after handling the rhs and other
expressions but before performing assignments, and once after all
assignments have been performed but before commending the next
statement.  (In practice, appropriate flow analysis often permits
the compiler to eliminate unnecessary synchronizations.)

[c] Allow statements other than assignments in body

[i] IF and WHERE

Assume that a block IF is first reduced to single IF statements
by introducing temporary variables and replicating the IF header:

      IF (m) THEN
        s1
        ...
        sm
      ELSE
        t1
        ...
        tn
      END IF

becomes

      tempm = m
      IF (tempm) s1
      ...
      IF (tempm) sm
      IF (.NOT. tempm) t1
      ...
      IF (.NOT. tempm) tn

Then we simply define

      FORALL (v1=l1:u1:s1,...,vn=ln:un:sn,fmask) IF (imask) s

to mean

      FORALL (v1=l1:u1:s1,...,vn=ln:un:sn,fmask .AND. imask) s

WHERE can be treated similarly, though the details are a bit
more complicated.

The motivation here is to make it easier to transform DO loops
into FORALL statements and vice versa, despite the fact that they
may contain conditional statements.

[ii] FORALL

      FORALL (va1=...,...,van=...,maska) FORALL (vb1=...,...,vbn=...,maskb) s

means

      FORALL (va1=...,...,van=...,vb1=...,...,vbn=...,maska.AND.maskb) s

assuming there is no duplication of the variable names (a compiler
should logically rename the variables if there is a duplication).

The motivation here is to make it easier to transform DO loops
with DO loops (that happen not to be closely nested) into FORALL
blocks within FORALL blocks, and vice versa.

[iii] ALLOCATE and DEALLOCATE

In the presence of Fortran 90 pointers and derived types,
it would be perfectly sensible to say:

      FORALL (I=1:100) ALLOCATE(FOO(I)%SUBARRAY(F(I)))

thereby constructing a ragged array.

[iv] Other?

[2] Directive for independent execution of iterations

Let there be a directive

!HPF$INDEPENDENT

that can precede either a DO loop or a FORALL statement.
It asserts to the compiler that the iterations of the loop
may be executed independently--that is, in any order, or
interleaved, or concurrently--without changing the semantics
of the program.  (The compiler is justified in producing
a warning if it can prove otherwise.)

!HPF$INDEPENDENT
      DO I=1,100
        A(I)=B(P(I))   !I happen to know that P is a permutation
      END DO

!HPF$INDEPENDENT
      FORALL (I=1:100) A(I)=A(F(I))
!I happen to know that F(I) > 100, so synchronization is not
!needed to delay assignments until every rhs has been computed.

One may apply this directive to a nest of multiple loops
by listing all the loop variables of the loops in question;
the loops must be contiguous with the directive and in the
same order that the variables are listed:

!HPF$INDEPENDENT (I1,I2,I3)
      DO I1 = ...
        DO I2 = ...
          DO I3 = ...
            DO I4 = ...    !The inner two loops are *not* independent!
              DO I5 = ...
                ...
              END DO
            END DO
          END DO
        END DO
      END DO

In the case of a FORALL, any of the variables may be mentioned:

!HPF$INDEPENDENT (I1,I3)
      FORALL(I1=...,I2=...,I3=...) ...

This means that for any given values for I1 and I3,
all the right-hand sides for all values of I2 must
be computed before any assignment are done for that
specific pair of (I1,I3) values; but assignments for
one pair of (I1,I3) values need not wait for rhs
evaluation for a different pair of (I1,I3) values.

These directives are purely advisory and a compiler is free
to ignore them if it cannot make use of the information.

This directive is of course similar to the DOSHARED directive
of Cray MPP Fortran.  A different name is offered here to avoid
even the hint of commitment to execution by a shared memory machine.
Also, the "mechanism" syntax is omitted here, though we might want
to adopt it as further advice to the compiler about appropriate
implementation strategies, if we can agree on a desirable set
of options.

---

From: [email-masked]
Date: Tue, 21 Apr 92 11:52:37 -0400

Guy,

I finally got around to studying your FORALL proposal, and I have a
few questions about it:

  Guy L. Steele Jr.

  . . .

You don't specify any restrictions on the form or content of rhs.  Was
it your intention to leave it unconstrained?  Or did you just omit
that part of the specification?  (As you know, lots of FORALL
specifications restrict the RHS rather severely, and if you don't
restrict it at all, you may have some interesting semantic and
implementation problems with things like calling user-defined
functions in the rhs.)

Similarly, you don't specify any restrictions on the form or content
of e1,...,em, except to state that every iteration variable must be
used at least once.  Can I call user-defined functions from here?

  . . .

Your use of a tentative word ("would") makes me wonder if you're
proposing this seriously, or just as an interesting idea to
consider...

Aside from these two questions, it seems like a good proposal,
although it goes a lot further than our proposal did.  (We were
intentionally restrained in our FORALL proposal, in the hope that at
least the minimal functionality would be adopted quickly, rather than
losing the whole ball of wax in a protracted debate about possible
extensions.  But I think we would have been pretty happy to go along
with a proposal like this one.)				-Bert

---

From: Guy Steele <[email-masked]>
Date: Tue, 21 Apr 92 12:10:10 EDT

Date: Tue, 21 Apr 92 11:52:37 -0400
   From: [email-masked]

   Guy,

     Guy L. Steele Jr.

     . . .

Yes and yes, though if things  get too weird, the CM Fortran
compiler just punts, implements it as two serial loops using
an array temporary, and issues a warning.  As time goes on,
we have increased the set of cases it can parallelize.

     . . .

I just used "would" so as not to prejudge the question of whether
Fortran 90 pointers and derived types would be in HPF.

Thanks.
--Guy

---

From: [email-masked]
Date: Tue, 21 Apr 92 13:59:20 -0400

Guy, I finally read over your March 25 proposal for local subroutines.
I still haven't heard much comment on it, even after your plea early
this month, but I find a fair amount of fodder for thought and
controversy in it.

Your proposal clearly responds to an expressed need in the user
community, but I dare say that by the time there would be convergence
on the subject of local subroutines and local program execution
blocks, we would have done as much new language design as for all of
the rest of HPF put together.  This makes me think it might be
valuable to find ways to "factor out" the question of local
subroutines and local execution so that it could proceed in parallel
with the rest of the HPF specification but not be a source of delay.

So I've been thinking about how we could respond to the need with the
smallest amount of detail work, and here are some thoughts:

 * A low-tech way to get much of the value of local subroutines is to
   provide a foreign-function-call interface to another
   (thread-oriented) language.  HPF implementations will probably need
   to have such interfaces anyhow, so this shouldn't be extra work.
   But if we have such an interface, then instead of doing the
   language design work required to be able to write thread-oriented
   execution in HPF itself, we could just let that code be written in
   another (presumably already existing) language.

   Since (by this logic) we should already be considering
   foreign-function-call interfaces from HPF to thread-oriented
   languages, perhaps we should start by just considering that aspect
   of the problem, and once that seems to be under control, we can
   tackle the task of how to do thread-oriented programming in HPF
   itself, if we still want to.  A lot of the issues in your proposal
   (notably the question of defining the local views of global data)
   still arise in defining a foreign-function-call interface, but
   other issues (such as defining the thread-oriented synchronization
   primitives) do not, since they are the property of the language in
   which the foreign functions are written.

   So, as a concrete proposal for how to proceed with this issue, I
   propose that we leave aside the question of what constructs are
   used within the thread-oriented parts of the program and just try
   to define how the global HPF data is made accessible to the local
   procedures through the foreign-function-call interface.

 * If we do indeed specify HPF as "core HPF" plus "options," then I
   think local subroutines should go in as "options," since they may
   be difficult to implement on some architectures.  On the other
   hand, the foreign-function-call design may be something that wants
   to be part of the core.

Those are my two cents.					-Bert