Subject: FORALL is not a loop (and neither is DO INDEPENDENT)

From: [email-masked] (Rector L. Page)
Date: Mon, 20 Jul 92 10:29:35 CDT

--------
Some writings on forall refer to it as a "parallel loop."  This
unfortunate term leads to confusion.  The terminology may derive
from the fact that both forall constructs and do-loops specify an
index set that parameterizes a block of statements.  In effect,
both denote a collection of statement blocks.  The collection
contains one copy of the block of statements for each index in
the index set.

         forall (i=1:n)           do i=1,n               
           . block                   . block             
           .  of                     .  of               
           .   stmts                 .   stmts           
         end forall               end do                

Here the similarity ends.  The statement blocks in a forall are
carried out independently (and simultaneously, the programmer hopes),
but the statement blocks in a do-loop are carried out in sequence.

In a forall the index set is unordered, while it is an ordered
sequence in a do-loop.  The two constructs use different delimiters
(colon and comma) to highlight the difference in meaning:
  forall (i=1:n)  specifies an index set in the usual mathematical sense;
  do i=1,n        specifies a sequence of indices.

With the looping concept out of the picture, it is not at all surprising 
that
       forall (i=1:n)
         a(i)=a(i-1)+1  ! means increment a shifted array
       end forall
while
       do i=1,n
         a(i)=a(i-1)+1   ! means to compute a running sum
       end do            ! and save the partial sums.

If all of the assignments a(i)=a(i-1)+1 in the forall are to take
place simultaneously, what value could a(i-1) denote other than the
value a(i-1) had on entry to the forall construct?  With the parallel
computation view of forall (as distinguished this from the sequence
view of looping, it is hard to imagine any meanings other than
increment-shifted-array in the forall example and running-sum
in the do-loop example.

The do-independent notation, when taken as a programming construct
rather than as a hint to the compiler, expresses the same idea
as forall, but in a restricted form.  An example restriction:
   !hpf$ independent
         do i=1,n
           a(i)=a(i-1)+1  ! is illegal because the statements
         end do           ! contain interdependencies.

When viewed as a hint to the compiler, do-independent is not so bad.
Viewed as a programming construct, it encourages confusion
between parallel computation and looping.  I oppose it on these
grounds.  Programmers trying to get the last bit of efficiency out
of their computers will try to use do-independent rather than forall
whenever they can (so the compiler can omit a few synchronization
operations).  They will spend a lot of time trying to figure out
if there are any untoward interdependencies in their indexed,
parallel blocks of statements.  They will often get it wrong.
Even when they don't get it wrong, the next programmer to
fiddle the code will.  The resulting plethora of errors will
cost a great deal more than the savings produced by avoiding
a few synchronizations.

If HPF turns out to have a parallel construct for an indexed
collection of statement blocks, I hope it uses a notation that
doesn't piggy-back on the coincidence that the do-loops happen
to specify index sequences and statement blocks.

Rex Page

---

From: [email-masked]
Date: Mon, 20 Jul 1992 14:31:42 -0600

>but the statement blocks in a do-loop are carried out in sequence.

... and Rex then goes on to say a lot of things I agree with.  I've tried to
stick to "FORALL construct" and similar circumlocutions in the current
draft proposal; I'd be grateful if anybody could point out instances
where I failed.

I think, however, that we are in mild disagreement over INDEPENDENT.
 
>to specify index sequences and statement blocks.

I believe that INDEPENDENT should be considered a user assertion,
not a programming construct.  I favor having the assertion, because
the users who I talk to lack faith in their compilers' dependence
analysis.  (Whether faith would be justified, or whether users
make mistakes in their analysis are questions that I refuse to
debate.)  I agree that DO INDEPENDENT should not be given the status
of new statement construct, as it is in (for example) PCF for the
same reasons as Rex gives. 

Note that defining DO INDEPENDENT as an assertion disallows some
important (or at least well-publicized) algorithms:
        Accumulations (the variable being accumulated has loop-carried
            dependences) and other recurrences
        Chaotic relaxation, and other algorithms with nondeterminate 
            execution (if the DO was really INDEPENDENT, then the 
            algorithm would be determinate)
        "Return any valid answer" (if the answer is not unique, the
            solutions create dependences)
        Explicit synchronization (how do you synchronize without
            changing shared state)
My hope is that Clemmens' group can provide a good mechanism for
expressing most of these in HPF version 2.  We have explicitly limited
FORALL and DO INDEPENDENT for the current version of HPF in order
to get faster agreement.

                                                Chuck