Subject: triangular array access and assignment-only block foralls

From: "Rex Page" <[email-masked]>
Date: Tue, 23 Jun 92 11:36:59 -0500

forall (i=1:n)                      ! assigns new values
       forall (j=i:n) A(j,j-i+1) = ...   ! to the lower triangle
     end forall                          ! of a matrix

Array sections provide access to rectilinear portions of arrays
(i.e., portions whose index sets are Cartesian products of sets
of subscripts).

Forall statements provide access to more general portions of
arrays (the diagonal of a matrix, for example).  Block forall
constructs generalize accessible portions of arrays still further
(e.g., to slices taken at angles).

If a forall construct permits the block of statements instantiated
by one value of the index set to affect the result of another such
block, the overall effect of the construct will fail to be
deterministic.  Acceptable nondeterministic results would be fairly
easy to describe if all of the statements in the block were
assignments (... must be the same as repeated execution of the block
according to a sequence established by some permutation of the index
set, assuming all rhs's are pre-evaluated and stored in temporaries
... blah blah mumble mumble).

Fortran 90, as it stands, avoids even this level of nondeterminism.
That is why it prohibits duplicate entries in vector-valued subscripts
that occur in lhs's.

Acceptable non-determinism in a block forall becomes more difficult
to describe in the presence of statements other than assignments.
CALLs are especially difficult to deal with.  The quantity of
misunderstandings and incorrect programs that would result from
such a complex linguistic structure would, I think, negate its
potential advantages.

HPF Fortran might try to avoid this sort of complexity by requiring
that the evaluation of a forall block for one element in the forall's
index set neither affect nor be affected by the evaluation of the
block for any other element of the index set.  This almost works,
but not quite because rhs's in assignments need to be pre-evaluated,
and this exception invalidates, unfortunately, inline substitution as
a correct method of invoking subroutines.  A subroutine containing
assignments could produce a different effect if its executable
statements were substituted in place of a CALL to the subroutine
in a forall.

I conclude that forall should be used for array assignment only,
including forall assignment.  This would provide a way to access
non-rectilinear portions of arrays, but it would not provide a
parallel loop.  (A forall assignment is not a loop because it is
not a control structure.)  Perhaps HPF Fortran could get by with
a directive indicating independence in DO loops as its sole
parallel-loop facility, using block foralls simply as an array
access method.

Rex Page      Amoco Production Company              918-660-3935
              Research Center, 41&Yale zip 74135           -4163 FAX
              POBox 3385
              Tulsa OK  74102

---

From: [email-masked]
Date: Wed, 24 Jun 92 11:18:34 -0500

> To: [email-masked]
> Subject: triangular array access and assignment-only block foralls
> Date: Tue, 23 Jun 92 11:36:59 -0500
> From: "Rex Page" <[email-masked]>
> 
> ...
> 

My reading of Marc's proposal is that you can't use the outer FORALL
indices as inner FORALL bounds (as your example does).  To quote Marc:
	Constraint: A subscript-name that occurs in a
	forall-triplet-spec-list may be referenced inside the scope of
	the FORALL only by the scalar-mask-expr of a FORALL or WHERE
	statement or in an assignment of the form array-element - expr
	or array-section = expr.  A subscript-name may not be
	redefined inside the scope of the FORALL.
So I don't think the block FORALL generalizes the array sections more
than the regular FORALL.

See also the previous discussion of faking triangular FORALLs using masks.

On the other hand, I like your version of block FORALL better than Marc's.

> ...

Like Ken, I don't want nondeterminism in the HPF language.  The cases
that Rex calls "acceptable non-determinism" I would label as
"non-standard-conforming".  [Asbestos suit on]

Let me observe that function calls have essentially all the problems
that CALL statements do within FORALLs.  I want to be able to say
	FORALL ( I = 1:N ) A(I) = SIN( 2*I*PI / N )
but be protected from suprises in
	FORALL ( I = 1:N ) A(I) = MESSY_FUNCTION( I, B(I), INDX(:) )
where MESSY_FUNCTION could potentially 
	Assign to B(I) [ no problem, they're independent ]
	Assign to B(INDX(I)) [ big problem, in general ]
	Reference all of INDX [ possibly complicated if INDX is distributed ]
	Assign anything in INDX [ big problem ]
We need to figure out some restrictions on functions to avoid
ambiguities and problems.  Pres, weren't you going to circulate a
definition of user elemental functions?  If nothing else, that sounds
like a good starting point.

>               Research Center, 41&Yale zip 74135           -4163 FAX

This sounds like something I can support, with a couple
qualifications:
    I support WHERE in FORALL loops (which requires extending
	WHERE to scalar assignments as well).
    It appears that nested single-statement FORALL is allowed, but
	nested multi-statement FORALL is not.  What is the reason for
	this?
    We still need firm agreement on what to do for functions and DO
	INDEPENDENT.  There's been almost no discussion of Min-You's
	INDEPENDENT proposal; should I read this as general agreement
	or general "too busy/don't care"?

	Chuck

---

From: [email-masked] (Joel Williamson)
Date: Wed, 24 Jun 92 12:51:11 CDT

> 	or general "too busy/don't care"?
I continue to prefer Min-You's INDEPENDENT proposal.  Being able to
code:

	forall (...)
	...synchronous-forall-stuff...
CHPF$ INDEPENDENT
	...freeforall-stuff...
CHPF$ END INDEPENDENT
	...more-synchronous-forall-stuff...
	end forall

instead of three separate foralls with the second declared INDEPENDENT,
is concise, clear, and "natural."

Joel

---

From: "Rex Page" <[email-masked]>
Date: Wed, 24 Jun 92 15:29:33 -0500

> So I don't think the block FORALL generalizes the array sections more

I'm not sure why Marc's proposal restricts the use of FORALL indices.
I view the block FORALL as a semantic equivalent to a collection of
statement blocks executing concurrently.  The collection contains one
instance of the block for each value in the index set, and in that
instance the appropriate values of the indices replace the index variables.
An index variable cannot be redefined (that would be like redefining a
constant), but it should be usable in any way that an integer constant
could be used.

I also don't understand the rationale for prohibiting FORALL-type
array-assignments in block FORALLs, especially when section-type
assignments are permitted.

>"non-standard-conforming".  [Asbestos suit on]

I don't have a strong feeling about nondeterminism, but it doesn't make
me uncomfortable as long as the collection of correct results from a
non-deterministic piece of code is easy to describe.  Actually, Fortran
has had nondeterminism from the outset in the 1966 standard because it
permited expressions to be computed without full evaluation of all the
operands as long as the value delivered for the expression is mathematically
equivalent to the one that would have been delivered if all operands had
been evaluated.

An example from the Fortran 90 document implies that the expression 
    .TRUE. .OR. f(x)
need not invoke the function f.  If f contains a write statement,
Fortran 90 admits both the computation that executes the write and the
one that doesn't as legitimate interpretations of the code.  (I think
there is actually a theoretical problem with this philosophy because f
might be non-terminating, in which case the value delivered if f is not
evaluated, namely .TRUE., seems mathematically different from the value
delivered when f is evaluated, namely none.)  A similar example in
Fortran 66 would be the expression 0*f(x).

Nevertheless, prohibiting further instances of nondeterminism is ok by me.
Assignemnt statements of the form A(v)=..., where v is a vector, are
non-standard if v contains duplicate values.  The reason it's non-standard
is to avoid nondeterminism. On the other hand, if Fortran 90 had not made
this restriction, I don't think we'd need intrinsic subroutines for
defining send.  (By the way, don't defining sends introduce some
nondeterminism?).

>like a good starting point.

One restriction I would favor is to prohibit side-effects in functions
used in this FORALLs (such as assigning to B(I) in your MESSY_FUNCTION).

>	nested multi-statement FORALL is not.  What is the reason for

I would include block FORALL as a form of FORALL assignment.
That is, I did not intend to exclude nested multi-statement FORALL.

Rex Page

---

From: [email-masked]
Date: Wed, 24 Jun 92 15:57:00 -0500

> Subject: Re: triangular array access and assignment-only block foralls 
> Date: Wed, 24 Jun 92 15:29:33 -0500

Marc, where are you?  Please lead us out of this darkness!

I agree with Rex that FORALL bounds shouldn't be restricted thus.

> ... example ...

Sounds like we basically agree on nondeterminism.

Yes, a Fortran 90 definition would have eliminated the need for the
COPY_SEND intrinsic.  I think SUM_SEND and the others would still have
been needed, because Fortran 90 doesn't have C-style += operators.

Yes, COPY_SEND is nondeterministic (as defined now, it could probably
be changed).  SUM_SEND can be implemented deterministically on all
architectures I'm aware of as long as you keep the number of
processors constant.  A few have hefty performance penalties, though.
Changing the number of processors can change the answer due to
roundoff errors; then again, this is also true of the SUM intrinsic.
Changing data distributions probably has similar kinds of effects to
changing number of processors.

> used in this FORALLs (such as assigning to B(I) in your MESSY_FUNCTION).

I assume you mean at least "all side effects visible in the caller"
(we'll discuss side-effects in SAVE variables later).  Sounds rational
to me.  The floor is open for users to complain that this is too
restrictive...

> That is, I did not intend to exclude nested multi-statement FORALL.

My misunderstanding.  Objection overruled.

	Chuck

---

From: "Rex Page" <[email-masked]>
Date: Thu, 25 Jun 92 09:02:40 -0500

Chuck said:

It doesn't seem to me that the lack of += operators should be an obstacle.
What's wrong with  A(v)=A(v)+B instead of A(v)+=B?

Chuck said:

Performance is the key issue.  Nondeterminism similarly can be defined away
in assignments like A(v)=... when v contains duplicates, but why restrict
the processor?  A sequential program is always an option when the programmer
needs the extra synchonization.  Defining away the nondeterminism sacrifices
performance in the cases where the programmer is satisfied with any
interleaving of the updates.  Another advantage of permitting nondeterminism
over defining it away is that the definition will be clumsy and difficult
to remember; description of the nondeterministic semantics will be simpler
(operationally, at least).

> used in this FORALLs (such as assigning to B(I) in your MESSY_FUNCTION).

Chuck responded:

No, I mean side effects that change the subsequent result of the
computation.  This includes assignments to SAVE variables, writes,
reads, assignments to COMMON or MODULE variables, assignments to dummy
arguments, and probably a bunch of stuff I haven't thought of.

I don't want the processor to have to execute any statments in a function
at all if the processor can figure out the value of the expression
containing the funtion's invocation in some other way.  (I know you didn't
mean to open the floor to people who thought it wasn't restrictive enough,
Chuck, but as you can see I have strong feelings about this.) 

 - Rex Page

---

From: [email-masked]
Date: Thu, 25 Jun 92 14:42:24 -0500

> Date: Thu, 25 Jun 92 09:02:40 -0500

Consider the Fortran 90 interpretation of any array assignment
statement: first the RHS is evaluated, then the LHS is assigned.  By
this definition, the RHS evaluation doesn't depend on where it's
going; by the time you have to choose between COPY_SEND and SUM_SEND,
the expression has already been evaluated, and the (wrong) additions
done.

This could be fixed by a suitable (albeit more complex) interpretation
in the standard.

> (operationally, at least).

The performance penalties come in on machines where data moves among
processors dynamically (virtual paging, etc.); then it's hard to
control order of evaluation, hence overhead.  Of course, it's not
really clear what static data distributions mean on hardware like
that, anyway.

Numerical users: How important is controlling roundoff to you?  This
is the classic question "Do you want the right answers, or do you want
them fast?"

> Chuck, but as you can see I have strong feelings about this.) 

OK, a strong stand against *any* side effects.  Pending some
codification of this condition (anyone want to list all possible side
effects?), does anyone want to argue against this restriction?

	Chuck

---

From: "Rex Page" <[email-masked]>
Date: Thu, 25 Jun 92 14:53:15 -0500

Chuck said:

Chuck said:

Chuck responded:

 - Rex Page

---

From: Guy Steele <[email-masked]>
Date: Mon, 29 Jun 92 16:25:09 EDT

Chuck said:

If v has duplicate values, then  A(v)=A(v)+B  is forbidden by Fortran 90.
SUM_SEND is intended to cover precisely this possibility.

Chuck is correct that COPY_SEND would not be needed if  A(v)=...  were
in fact defined to result in storing some one of the assigned values
in the case of duplicate values in v.  (Note that such a definition might
present some implementation difficulties in some architectures--consider
that explicit synchronization might be required, even in a shared-memory
machine, if elements of A were large enough that they could not be
updated in a single atomic memory operation.)  However, SUM_SEND would
still be needed, because if v has duplicates,  A(v)=A(v)+B  would result
in adding *one* of the B values to A(i), where i is some value duplicated
in v, rather than adding in *all* the B values which which the corresponding
element of v is i.  (You can find more discussion of this topic in the
context of the C language in:

  Rose, John R., and Steele, Guy L. Jr.  "C*: An Extended C Language for
  Data Parallel Programming."  Proc. Second International Conference on
  Supercomputing.  International Supercomputing Institute, Inc. (Santa
  Clara, 1987) Volume II, 2-16.

See especially section 5.4.)

--Guy