Subject: Back to square one

From: Alan Karp <[email-masked]>
Date: Tue, 14 Jul 92 09:05:04 -0700

I just recently got a copy of all the discussion on FORALL and have
plowed through most of it. It seems that people are asking the wrong
question. I don't want to decide what kind of FORALL is to be adopted
until we decide if there should be any kind of FORALL at all. 

Attached is a copy of a report I wrote while I was with IBM, before I
read all the discussion. IBM did not want it widely distributed
because they were afraid someone might think it was an official IBM
position. (How anyone could believe that my rantings are the official
position of anyone is beyond me.)

What will it take to convince me that FORALL is necessary? Some code
examples where compiler parallelization assisted with directives won't
work would be a start. However, only examples from real programs are
allowed. You must also give me the opportunity to rewrite them as I
would do if I were tuning for a new machine. Notational convenience
won't do it since I think there are other mechanisms that would do the
job at least as well as FORALL.

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

%%**start of header
%forall.tex

\documentstyle[11pt]{article}
\pagestyle{plain}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin  .25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin   -.5in
\textwidth 6in
\textheight  9.0in
\def\forall{{\tt FORALL}}

\title{The Case Against FORALL}
\author{Alan Karp}
%\date{   }

\begin{document}

\maketitle

%%**end of header
%
\section{Introduction} 	
\label{sec:intro}

Programming parallel processors is hard.
One way to make the job easier is to put the burden on the compiler.
While this approach won't work for ``dusty decks'',
it shows promise for newly written programs.
A number of extensions to Fortran have been proposed to make this
job easier.
These extensions include array language,\cite{f90explained}
data distribution statements,\cite{dpf}
and various forms of \forall.\cite{forall,fortrand}

In this note I will start with a discussion of the various
\forall\ proposals.
Next, I will explain why I think \forall\ is both unnecessary
and dangerous.

\section{\forall}
\label{sec:forall}

The \forall\ statement is a convenient way to denote certain
array operations.
At various times it was included in the Fortran 8x language\cite{f8xstandard}
although it did not make it into the Fortran 90 standard.\cite{f90standard}
\forall\ is an important part of CM Fortran\cite{forall},
Data Parallel Fortran\cite{dpf}, and both
Fortran D and Fortran 90D.\cite{fortrand}

\forall\ was introduced for a couple of reasons.
Firstly, there is no way to express certain constructs in Fortran 90.
For example, there is no way of assigning the diagonal of a matrix to a 
vector or of working with non-conformable arrays.\cite{forall}

\begin{figure*}
  \begin{verbatim}
  a(2:n-1,2:n-1,2:n-1) =
 *   c(2:n-1,2:n-1,2:n-1)*(f(2:n-1,2:n-1,2:n-1)-f(1:n-2,2:n-1,2:n-1))
 * + d(2:n-1,2:n-2,2:n-1)*(f(2:n-1,2:n-1,2:n-1)-f(2:n-1,1:n-2,2:n-1))
 * + e(2:n-1,2:n-1,2:n-1)*(f(2:n-1,2:n-1,2:n-1)-f(2:n-1,2:n-1,1:n-2))
  \end{verbatim}
  \caption[Typical PDE statement in Fortran 90]
    {Fortran 90 statement that might be found in a code solving
     a partial differential equation.}
  \label{fig:pdef90}
\end{figure*}

\begin{figure*}
  \begin{verbatim}
   forall(i=2,n-1;j=2,n-1;k=2,n-1)
      a(i,j,k) = c(i,j,k)*(f(i,j,k)-f(i-1,j,k))
  *            + d(i,j,k)*(f(i,j,k)-f(i,j-1,k))
  *            + e(i,j,k)*(f(i,j,k)-f(i,j,k-1))
   endforall
  \end{verbatim}
  \caption[Typical PDE statement using a \forall]
    {The statement of Figure~\ref{fig:pdef90} written using a \forall.}
  \label{fig:pdeforall}
\end{figure*}

Another reason is notational convenience.
Consider a discretization problem that treats the boundary
variables differently from those on the interior.
A typical Fortran 90 statement is shown in Figure~\ref{fig:pdef90}.
Figure~\ref{fig:pdeforall} shows how it could be written with a \forall.
Clearly, the latter form is both easier to write and easier to read.

Thinking Machines Corporation had a different motivation for
introducing \forall.\cite{cmfortran}
Their SIMD back end is controlled by a front end processor.
In CM Fortran, any code not in an array language statement
is executed sequentially on the front end processor;
only code written in array language is executed in parallel
on the SIMD part of the machine.
Thus, the only way to get parallel execution of a construct
that is not expressible in Fortran 90 array notation is to use \forall.

There are two flavors proposed for \forall\ --
the single statement and block forms.
A single statement \forall\ takes as its range a single line of code,
but there are restrictions on what can be in that line.
For example, in CM Fortran any reference to an external function or an 
array stored on the front end machine causes the loop to be executed serially.

The block \forall\ takes a block of code as its argument,
but there is disagreement on the semantics of the block of code.
A standard Fortran 90 statement is executed as if the entire right hand
side is evaluated before any assignments are made.
This {\em copy-in} semantics side steps the problem of
statements with dependences.
The controversy centers on whether or not the block of code should
be understood in this way.

The block \forall\ of Fortran 90D extends copy-in semantics to the entire block with
an exception.
Each loop iteration is considered to be executed by a separate task.
The task sees the current value of array elements that it owns;
it sees the value at loop entry for all others.
For example,

\begin{verbatim}
   a(0:n) = 1.0
   forall i=1,n
      a(i) = a(i-1) + 1.0
      b(i) = a(i-1)
      c(i) = a(i)
   endforall
\end{verbatim}
%
At the completion of this loop,
{\tt a(1:n) = 2.0}, {\tt b(1:n) = 1.0}, and {\tt c(1:n) = 2.0}.

\section{Dangerous}
\label{sec:dangerous}

I believe that \forall\ is dangerous because the meaning of a
statement depends on its context.
Show the loop at the end of the last section to 10 Fortran programmers,
and ask them to tell you the values of the arrays at the
end of the loop.
You are likely to get 10 different answers.
(Well, maybe not 10.)
If this problem occurs for a simple loop,
what will happen with a more complicated one?

Imagine debugging an application code,
especially one you did not write.
Let's say that there is a loop coded with a \forall\ 
with one statement that should have been in a serial loop.
How do you find the error?
You can't simply change the \forall\ to a conventional {\tt DO}
because that would change the meaning of the other statements.
Asking the compiler to do a dependence analysis for you
probably won't help because there will be many reported
dependences that the copy-in semantics handles correctly.
Visual examination might find the error,
but the fact that statements within a \forall\ are interpreted
differently from those in a {\tt DO} will make the job hard.

The one line \forall\ is not as bad,
The copy-in semantics is not as serious a problem,
but could still result in bugs that are hard to find.
The line of code {\tt A(I)=A(I-1)+1.0} means something different in a
\forall\ than it does in a {\tt DO}.
A program containing one when the other was intended would not run correctly.
Finding such an error would be difficult.

\section{Unnecessary}
\label{sec:unnecessary}

\forall\ is unnecessary.
Modern compilers do a very good job parallelizing loops.\cite{pfparticle}
They are much better than programmers in doing dependence analysis.
When the compiler doesn't have enough information to decide if
a data dependence exists,
programmers can insert directives.

There are very few loop constructs expressible with \forall\
that a compiler could not automatically parallelize except
for those that depend on copy-in semantics.
It is my feeling that a programmer who wants copy in semantics
can introduce temporary variables.

\begin{verbatim}
   a(0:n) = 1.0
   t = a
   do i=1,n
      a(i) = t(i-1) + 1.0
      b(i) = t(i-1)
      c(i) = a(i)
   enddo
\end{verbatim}
%
We can even expect the compiler to recognize that {\tt t} is a temporary
and not use any more storage than required with \forall.
A programmer who later changes the {\tt t} in the first line
of the loop to an {\tt a} might get a serial loop.
What won't happen is a statement that gives different results  depending
on its context.

\begin{figure*}
  \begin{verbatim}
    m = spread ( p(:,:,ic) .lt.  spread(amid,1,nn), 3, 10 )
    px(1:nn/2,:,:) = reshape( pack(p,m), (/(nn/2),nc,10/) )
    px(nn/2+1:nn,:,:) = reshape( pack(p,.not.m), (/(nn/2),nc,10/) )
  \end{verbatim}
  \caption[Fortran 90 version of part of an N-body code.]
    {Part of a tree-based N-body code that recursively partitions
     the particles into two groups.}
  \label{fig:nbodyf90}
\end{figure*}

Some very complicated constructs become simple to express
if we combine array language with conventional {\tt DO} loops.
For example, the code in Figure~\ref{fig:nbodyf90} is used to construct part 
of the data structure needed for an N-body simulation that
uses a tree structure.\cite{barneshut}
%
\begin{figure*}
  \begin{verbatim}
    iota = (/(1:nn)/)
    do k = 1, nc
       m = p(:,k,ic) .lt. amid
       p(:,k,:) = p( (/ pack(iota,m), pack(iota,.not.m) /), k, : )
    enddo
  \end{verbatim}
  \caption[Mixed version of tree code.]
    {The code of Figure~\ref{fig:nbodyf90} mixing Fortran 90 and
     an ordinary {\tt DO} loop.}
  \label{fig:nbodyforall}
\end{figure*}
% 
An APL programmer can figure out what is going on,
but most Fortran programmers would find it cryptic,
to say the least.
(This version is much clearer than the one line version I created
on the first pass.)

Compare it with the mixed version shown in Figure~\ref{fig:nbodyforall}.
Although the code is a bit longer,
it is easier to understand,
and the compiler should have no trouble parallelizing over {\tt k}.
The \forall\ version of this loop gained me nothing in
either expressiveness or clarity.

\section{Conclusions}
\label{sec:conclusions}

People are smart and can learn most anything.
(As a graduate student I was able to use an APL type ball on
a 1050 terminal to do my Fortran work.)
However, \forall\ is particularly insidious because it
forces us to look at familiar statements and interpret them
differently.
Worse yet, the meaning of any statement depends on its context;
the output from {\tt a(i) = a(i-1) + 1.0} depends on whether
it is contained in a {\tt DO} loop or a \forall.
It is the schizophrenia \forall\ forces on programmers that
is the most dangerous part of the construct.

The only argument in favor of \forall\ that makes sense to me
is the notational convenience.
I think we should be able to find a more direct way to 
simplify the expressions such as the {\tt DOMAIN} statement in Data
Parallel Fortran.\cite{dpf}

In conclusion, I think I have shown ways in which \forall\ is
dangerous.
I have given examples where I have shown that it is unnecessary.
I have even suggested a way to simplify the expression of
complicated statements.

\forall\ should not be adopted as a standard,
de facto or otherwise,
without much more discussion than has been given the question to date.
In describing High Performance Fortran,
the statement

\begin{quote}
What sort of \forall\ should be included?
\end{quote}
%
has been made.\cite{hpfsummary}
I would be happier if the statement read

\begin{quote}
What sort of \forall , {\em if any}, should be included?
\end{quote}
%
% Bibliography
%
\begin{thebibliography}{10}

\bibitem{forall}
E.~Albert, J.~D. Lukas, and G.~L. {Steele, Jr.}
\newblock {Data Parallel Computers and the FORALL Statement}.
\newblock {\em Journal of Parallel and Distributed Computing}, 13(2):185--192,
  October 1991.

\bibitem{f8xstandard}
{American National Standards Institute, Inc.}
\newblock {American National Standards for Information Systems Programming
  Language Fortran (Fortran 8x)}.
\newblock Technical Report Draft S8, Version 109 (X3.9-198x), American National
  Standards Institute, Washington, DC, August 1988.

\bibitem{f90standard}
{American National Standards Institute, Inc.}
\newblock {American National Standards for Information Systems Programming
  Language Fortran (Fortran 90)}.
\newblock Technical Report ISO/IEC 1539: 1991(E), American National Standards
  Institute, Washington, DC, 1991.

\bibitem{barneshut}
J.~Barnes and P.~Hut.
\newblock {A Hierarchical O(NlogN) Force-Calculation Algorithm}.
\newblock {\em Nature}, 324:446--449, 1986.

\bibitem{hpfsummary}
Walt Brainerd.
\newblock {High Performance Fortran}.
\newblock {\em Fortran Journal}, 4(1):14--15, January/February 1992.

\bibitem{cmfortran}
Thinking~Machines Corporation.
\newblock {\em {CM Fortran}}.
\newblock Thinking Machines Corporation, Cambridge, Mass., 1990.

\bibitem{dpf}
P.~M. Elustondo, L.~A. Vazquez, O.~J. Nestares, J.~S. Avalos, G.~A. Alvarez,
  C.-T. Ho, and J.~L.~C. Sanz.
\newblock {Data Parallel Fortran}.
\newblock Technical report, IBM RJ 8690, March 1992.

\bibitem{fortrand}
F.~Fox, S.~Hirandandani, K.~Kennedy, C.~Koelbel, U.~Kremer, C.~Tseng, and
  M.~Wu.
\newblock {Fortran D Language Specification}.
\newblock Technical Report TR90--141, Computer Science Dept., Rice University,
  December 1990.

\bibitem{f90explained}
M.~Metcalf and J.~Reid.
\newblock {\em {Fortran 90 Explained}}.
\newblock Oxford Science Publishers, Oxford, 1990.

\bibitem{pfparticle}
Leslie~J. Toomey, Emily~C. Plachy, Randolf~G. Scarborough, Richard~J. Sahulka,
  Jin~F. Shaw, and Alfred~W. Shannon.
\newblock {IBM Parallel Fortran}.
\newblock {\em IBM Systems Journal}, 27(4):416--435, 1988.

\end{thebibliography}
%
\end{document}

---

From: [email-masked] (James Cownie)
Date: Thu, 16 Jul 92 11:52:40 BST

Alan Karp argues strongly against introducing FORALL on the grounds of
the semantic complications it introduces into the language, and in
particular the way it modifies the semantics of embedded statements.

I would also argue against its inclusion in HPF because it is the ONLY
place where HPF is going to add syntax to Fortran. All of the other
HPF additions are comment annotations of (potentially) standard
conforming source, and leave the source still as standard conforming
as it was before they were added. We really should think (and think
again) before taking this step, since we're about to encourage people
to write non-standard code, and also make valid HPF programs invalid
Fortran. (Are we even allowed to call it Fortran after doing this ?)

(I know there was a straw poll still in favour of it at the last
meeting, after Joel raised exactly this point, but I think a lot of
people are still nervous about it...)

I don't find the argument that 
"Lots of us already have an implementation" 
a convincing one for forcing everyone else to have one too. 

HPF is not about to outlaw other extensions to Fortran (this is
clearly impossible !), so if people already have FORALL in their code
they can continue to use it on the machines which support it.
(Presumably these users knew what they were getting into when they started to
use it !). 

At the very least we should NOT add FORALL to the HPF core standard. (I
have no objection to putting it in a subsidiary document of extensions
along the lines of "If you do this do it this way", so that at least
everyone does the same thing with FORALL, David Loveman's document on
FORALL seems a fine place to start for this).

Please can we think long and hard about this.

--Jim
James Cownie 
Meiko Limited
650 Aztec West
Bristol BS12 4SD
England

Phone : +44 454 616171
FAX   : +44 454 618188
E-Mail: [email-masked] or [email-masked]

---

From: Richard Shapiro <[email-masked]>
Date: Thu, 16 Jul 92 09:49:15 EDT

Date: Thu, 16 Jul 92 11:52:40 BST
   From: [email-masked] (James Cownie)

FORALL gives us something that we don't get with a DO loop--order
independent "loops". I claim that this cannot be obtained with a simple DO
loop with directives, because such a directive breaks a fundamental rule
about directives not changing program semantics. For example, consider the
following 3 programs which produce a pseudo-random permutation of an
array:

C
C     Permute an array semi-randomly with FORALL
C
      SUBROUTINE SHUFFLE(DECK,NCARDS,SEED1,SEED2)
      INTEGER DECK(NCARDS),NCARDS,SEED1,SEED2
C
C     Make sure we will do a permutation by asserting that SEED1
C     and NCARDS are realtively prime
C
      CALL ASSERT_RELATIVELY_PRIME(NCARDS,SEED1)
      FORALL(I=1:NCARDS) DECK(I) = DECK(MOD(SEED2+SEED1*I,NCARDS)+1)
      RETURN
      END

This example uses a FORALL to achieve the shuffle. (I am aware that the
same program could be re-written using a vector-valued subscript, but I'm
trying to keep the example as simple as possible. If the arrays involved
were multidimensional, VVS's wouldn't suffice).  The code is short and causes
the user to see no temporary arrays.  A translation into a correct DO loop
looks like:

C
C     Permute an array semi-randomly with DO, correctly
C
      SUBROUTINE SHUFFLE(DECK,NCARDS,SEED1,SEED2)
      INTEGER DECK(NCARDS),NCARDS,SEED1,SEED2,TEMP(NCARDS)
C
C     Make sure we will do a permutation by asserting that SEED1
C     and NCARDS are realtively prime
C
      CALL ASSERT_RELATIVELY_PRIME(NCARDS,SEED1)
      DO I = 1,NCARDS
         TEMP(I) = DECK(MOD(SEED2+SEED1*I,NCARDS)+1)
      ENDDO
      DECK = TEMP
      RETURN
      END

Note the addition of an additional variable TEMP.  Finally, here is an
example with a "directive".

C
C     Permute an array semi-randomly with DO, and directive
C
      SUBROUTINE SHUFFLE(DECK,NCARDS,SEED1,SEED2)
      INTEGER DECK(NCARDS),NCARDS,SEED1,SEED2
C
C     Make sure we will do a permutation by asserting that SEED1
C     and NCARDS are realtively prime
C
      CALL ASSERT_RELATIVELY_PRIME(NCARDS,SEED1)

CHPF$ ALL_ITERATIONS_SIMULTANEOUS
      DO I = 1,NCARDS
         DECK(I) = DECK(MOD(SEED2+SEED1*I,NCARDS)+1)
      ENDDO
      RETURN
      END

Essentially, this is a directive which specifies that I want each iteration
of the loop to happen "at the same time" (someone has already invented a
term for this, no doubt).  In other words, each iteration of the loop must
occur as if no other iteration has yet occurred.  But now if I take my
correct code (with the directive) and remove the directive, I get different
answers.  

The FORALL statement adds a *semantics* which users have found very useful
in practical codes.  Of course, the same semantics can be achieved using DO
loops and other language features in an appropriate manner (in F90, *not*
in F77), but so what?  If we take this tack, why do we need the array
syntax? Or, to be very silly, why do we need DO at all?

I agree that we need to be *extremely* careful on multi-statement FORALL
(given the many possible meanings), but single-statement FORALL provides a
functionality which is very clumsily obtained any other way.

If anyone really wants an example (from a real applications code) of an
FORALL statement which cannot be re-written in any other F90 array-like
manner without the translation similar to that described in David Loveman's
document, I will be happy to provide one.

		Richard Shapiro,
		Thinking Machines Corporation
		(formerly of United Technologies)
		([email-masked])

---

From: [email-masked] (James Cownie)
Date: Thu, 16 Jul 92 15:40:55 BST

> about directives not changing program semantics. 

I disagree (what a surprise !).

A directive provides information to the compiler. The compiler can
ignore the information if it feels fit, or generate a warning if it
can show that the information in the directive is false.

Your third example :

CHPF$ ALL_ITERATIONS_SIMULTANEOUS
      DO I = 1,NCARDS
         DECK(I) = DECK(MOD(SEED2+SEED1*I,NCARDS)+1)
      ENDDO
      RETURN
      END
is a well defined Fortran program, whether or not the directive is
present. The fact that it doesn't do what you want is neither
here nor there, and the directive doesn't (in my mind) make it do what
you want. (Either the directive is ignored, or it is ignored and you
get a warning).

If you want to achieve the permutation you should write it like
your second example :
C

Surely then adding a
CHPF$ INDPENDENT 
above the loop expresses exactly what you want (or have I
misunderstood the meaning of this directive ?)

In summary : 
1) Directives NEVER change the semantics.
2) If you assert that the loop iterations have no data dependence,
   then you must write your code so that this is true.

--Jim
James Cownie 
Meiko Limited
650 Aztec West
Bristol BS12 4SD
England

Phone : +44 454 616171
FAX   : +44 454 618188

---

From: Richard Shapiro <[email-masked]>
Date: Thu, 16 Jul 92 11:02:12 EDT

Date: Thu, 16 Jul 92 15:40:55 BST
   From: [email-masked] (James Cownie)

Actually, we probably don't disagree. You made the point that I was trying
to make; if I want to get the semantics of a FORALL, I can't get it with a
single DO loop + directives.  I am arguing that we *want* the semantics of
the FORALL, because it can expresses what I am trying to say in my
algorithm more directly.

Note that I also agree with Alan Karp that the DO loop in his figure 4 is
much more readable than his figure 3 Fortran 90.  This is not an argument
against FORALL, but rather an argument against compilers which don't
paralellize DO loops. FORALL is as useful on an IBM PC as it is on a
Connection Machine.

		Richard Shapiro,

---

From: [email-masked] (James Cownie)
Date: Thu, 16 Jul 92 16:40:35 BST

> Actually, we probably don't disagree. 
Good !
> You made the point that I was trying
> single DO loop + directives.  
... without explicitly adding the temporary arrays.

> I am arguing that we *want* the semantics of
True, but then maybe APL could express it even better, or a language
which already had
	SOLVE_RICHES_PROBLEM 
as an intrinsic, so where do we stop ???

Stopping at the point of adding NOTHING to the base language is very
clean, clear, and simple. The statements "Any F90 program is an HPF
program", and "Any HPF program is an F90 program" are extremely
attractive ones to be able to make.

The attraction of FORALL seems to be that various people already have
implementations of it, but that's a very poor reason for putting it
in.

> paralellize DO loops. 
or against writing obscure code, or against "using the full power of
the language" :-)

> FORALL is as useful on an IBM PC as it is on a
> Connection Machine.
Sure, but this is saying that it should have been in F90. Since it
isn't (whatever the rights and wrongs of that maybe), it seems wrong
to me to make this the one place where we extend the base language,
and thus make a "standards conforming HPF" program NOT be a "standards
conforming F90" program.

--Jim
James Cownie 
Meiko Limited
650 Aztec West
Bristol BS12 4SD
England

Phone : +44 454 616171
FAX   : +44 454 618188

---

From: [email-masked] (Joel Williamson)
Date: Thu, 16 Jul 92 13:27:06 CDT

> attractive ones to be able to make.

This is a very powerful argument.  Furthermore, SISD vendors have almost
no incentive to include FORALL in an otherwise compliant F90 compiler,
which will reduce portability of HPF programs.

Joel Williamson