Subject: new draft proposal

From: [email-masked]
Date: Wed, 14 Oct 92 15:56:07 -0500

Below is the latest and greatest version of the HPF FORALL chapter.
Unless major errors or new proposals come up before the weekend (and I
have reason to believe they will), this will be the version presented
at the HPFF meeting next week.  If you have comments, please send them
to the group before next Tuesday so the meeting attendees have a
chance of hearing them.

Changes from the last draft:
1. Substantially rewritten PURE functions - thanks/blame goes to John
Merlin
2. Included ON clause proposals from Tin-Fook Ngai and Clemens Thole.
3. Included nested WHERE proposal from Guy Steele.
4. Minor reorganization of "Other Proposals"

						Chuck

---------------- cut here -------------

%chapter-head.tex

%Version of August 5, 1992 - David Loveman, Digital Equipment Corporation

\documentstyle[twoside,11pt]{report}
\pagestyle{headings}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin=.25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin=-.5in
\textwidth=6.0in
\textheight=9.0in
\parindent=2em

%the file syntax-macs.tex is physically included below

%syntax-macs.tex

%Version of July 29, 1992 - Guy Steele, Thinking Machines

\newdimen\bnfalign         \bnfalign=2in
\newdimen\bnfopwidth       \bnfopwidth=.3in
\newdimen\bnfindent        \bnfindent=.2in
\newdimen\bnfsep           \bnfsep=6pt
\newdimen\bnfmargin        \bnfmargin=0.5in
\newdimen\codemargin       \codemargin=0.5in
\newdimen\intrinsicmargin  \intrinsicmargin=3em
\newdimen\casemargin       \casemargin=0.75in
\newdimen\argumentmargin   \argumentmargin=1.8in

\def\IT{\it}
\def\RM{\rm}
\let\CHAR=\char
\let\CATCODE=\catcode
\let\DEF=\def
\let\GLOBAL=\global
\let\RELAX=\relax
\let\BEGIN=\begin
\let\END=\end

\def\FUNNYCHARACTIVE{\CATCODE`\a=13 \CATCODE`\b=13 \CATCODE`\c=13 \CATCODE`\d=13
		     \CATCODE`\e=13 \CATCODE`\f=13 \CATCODE`\g=13 \CATCODE`\h=13
		     \CATCODE`\i=13 \CATCODE`\j=13 \CATCODE`\k=13 \CATCODE`\l=13
		     \CATCODE`\m=13 \CATCODE`\n=13 \CATCODE`\o=13 \CATCODE`\p=13
		     \CATCODE`\q=13 \CATCODE`\r=13 \CATCODE`\s=13 \CATCODE`\t=13
		     \CATCODE`\u=13 \CATCODE`\v=13 \CATCODE`\w=13 \CATCODE`\x=13
		     \CATCODE`\y=13 \CATCODE`\z=13 \CATCODE`\[=13 \CATCODE`\]=13
                     \CATCODE`\-=13}

\def\RETURNACTIVE{\CATCODE`\
=13}

\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus 
 -.2ex}{2.3ex plus .2ex}{\large\sf}}
\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus 
 -.2ex}{1.5ex plus .2ex}{\large\sf}}
\def\alternative#1 #2#3{\def\@tempa{#1}\def\@tempb{A}\ifx\@tempa\@tempb\else
    \expandafter\@altbumpdown\string#2\@foo\fi
    #2{Version #1: #3}}
\def\@altbumpdown#1#2\@foo{\global\expandafter\advance\csname c@#2\endcsname-1}

\def\@ifpar#1#2{\let\@tempe\par \def\@tempa{#1}\def\@tempb{#2}\futurelet
    \@tempc\@ifnch}

\def\?#1.{\begingroup\def\@tempq{#1}\list{}{\leftmargin\intrinsicmargin}\relax
  \item[]{\bf\@tempq.} \@intrinsictest}
\def\@intrinsictest{\@ifpar{\@intrinsicpar\@intrinsicdesc}{\@intrinsicpar\relax}}
\long\def\@intrinsicdesc#1{\list{}{\relax
  \def\@tempb{ Arguments}\ifx\@tempq\@tempb
			  \leftmargin\argumentmargin
			  \else \leftmargin\casemargin \fi
  \labelwidth\leftmargin  \advance\labelwidth -\labelsep
  \parsep 4pt plus 2pt minus 1pt
  \let\makelabel\@intrinsiclabel}#1\endlist}
\long\def\@intrinsicpar#1#2\\{#1{#2}\@ifstar{\@intrinsictest}{\endlist\endgroup}}
\def\@intrinsiclabel#1{\setbox0=\hbox{\rm #1}\ifnum\wd0>\labelwidth
  \box0 \else \hbox to \labelwidth{\box0\hfill}\fi}
\def\Case(#1):{\item[{\it Case (#1):}]}
\def\&#1 {\@ifnextchar({\def\@tempq{#1}\@intrinsicopt}{\item[#1]}}
\def\@intrinsicopt(#1){\item[{\@tempq} (#1)]}

\def\MATRIX#1{\relax
    \@ifnextchar,{\@MATRIXTABS{}#1,\@FOO, \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar;{\@MATRIXTABS{}#1,\@FOO; \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar:{\@MATRIXTABS{}#1,\@FOO: \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar.{\hfill\penalty1\null\penalty10000\hskip0pt plus 1filll
		  \@MATRIXTABS{}#1,\@FOO.\penalty-50\@gobble
  }{\@MATRIXTABS{}#1,\@FOO{ }\hskip0pt plus 1filll\penalty-1}}}}}

\def\@MATRIXTABS#1#2,{\@ifnextchar\@FOO{\@MATRIX{#1#2}}{\@MATRIXTABS{#1#2&}}}
\def\@MATRIX#1\@FOO{\(\left[\begin{array}{rrrrrrrrrr}#1\end{array}\right]\)}

\def\@IFSPACEORRETURNNEXT#1#2{\def\@tempa{#1}\def\@tempb{#2}\futurelet\@tempc\@ifspnx}

{
\FUNNYCHARACTIVE
\GLOBAL\DEF\FUNNYCHARDEF{\RELAX
    \DEFa{{\IT\CHAR"61}}\DEFb{{\IT\CHAR"62}}\DEFc{{\IT\CHAR"63}}\RELAX
    \DEFd{{\IT\CHAR"64}}\DEFe{{\IT\CHAR"65}}\DEFf{{\IT\CHAR"66}}\RELAX
    \DEFg{{\IT\CHAR"67}}\DEFh{{\IT\CHAR"68}}\DEFi{{\IT\CHAR"69}}\RELAX
    \DEFj{{\IT\CHAR"6A}}\DEFk{{\IT\CHAR"6B}}\DEFl{{\IT\CHAR"6C}}\RELAX
    \DEFm{{\IT\CHAR"6D}}\DEFn{{\IT\CHAR"6E}}\DEFo{{\IT\CHAR"6F}}\RELAX
    \DEFp{{\IT\CHAR"70}}\DEFq{{\IT\CHAR"71}}\DEFr{{\IT\CHAR"72}}\RELAX
    \DEFs{{\IT\CHAR"73}}\DEFt{{\IT\CHAR"74}}\DEFu{{\IT\CHAR"75}}\RELAX
    \DEFv{{\IT\CHAR"76}}\DEFw{{\IT\CHAR"77}}\DEFx{{\IT\CHAR"78}}\RELAX
    \DEFy{{\IT\CHAR"79}}\DEFz{{\IT\CHAR"7A}}\DEF[{{\RM\CHAR"5B}}\RELAX
    \DEF]{{\RM\CHAR"5D}}\DEF-{\@IFSPACEORRETURNNEXT{{\CHAR"2D}}{{\IT\CHAR"2D}}}}
}

%%% Warning!  Devious return-character machinations in the next several lines!
%%%           Don't even *breathe* on these macros!
{\RETURNACTIVE\global\def\RETURNDEF{\def
{\@ifnextchar\FNB{}{\@stopline\@ifnextchar
{\@NEWBNFRULE}{\penalty\@M\@startline\ignorespaces}}}}\global\def\@NEWBNFRULE
{\vskip\bnfsep\@startline\ignorespaces}\global\def\@ifspnx{\ifx\@tempc\@sptoken \let\@tempd\@tempa \else \ifx\@tempc
\let\@tempd\@tempa \else \let\@tempd\@tempb \fi\fi \@tempd}}
%%% End of bizarro return-character machinations.

\def\IS{\@stopfield\global\setbox\@curfield\hbox\bgroup
  \hskip-\bnfindent \hskip-\bnfopwidth  \hskip-\bnfalign
  \hbox to \bnfalign{\unhbox\@curfield\hfill}\hbox to \bnfopwidth{\bf is \hfill}}
\def\OR{\@stopfield\global\setbox\@curfield\hbox\bgroup
  \hskip-\bnfindent \hskip-\bnfopwidth \hbox to \bnfopwidth{\bf or \hfill}}
\def\R#1 {\hbox to 0pt{\hskip-\bnfmargin R#1\hfill}}
\def\XBNF{\FUNNYCHARDEF\FUNNYCHARACTIVE\RETURNDEF\RETURNACTIVE
  \def\@underbarchar{{\char"5F}}\tt\frenchspacing
  \advance\@totalleftmargin\bnfmargin \tabbing
  \hskip\bnfalign\hskip\bnfopwidth\hskip\bnfindent\=\kill\>\+\@gobblecr}
\def\endXBNF{\-\endtabbing}

\def\BNF{\BEGIN{XBNF}}
\def\FNB{\END{XBNF}}

\begingroup \catcode `|=0 \catcode`\\=12
|gdef|@XCODE#1\EDOC{#1|endtrivlist|end{tt}}
|endgroup

\def\CODE{\begin{tt}\advance\@totalleftmargin\codemargin \@verbatim
   \def\@underbarchar{{\char"5F}}\frenchspacing \@vobeyspaces \@XCODE}
\def\ICODE{\begin{tt}\advance\@totalleftmargin\codemargin \@verbatim
   \def\@underbarchar{{\char"5F}}\frenchspacing \@vobeyspaces
   \FUNNYCHARDEF\FUNNYCHARACTIVE \UNDERBARACTIVE\UNDERBARDEF \@XCODE}

\def\@underbarsub#1{{\ifmmode _{#1}\else {$_{#1}$}\fi}}
\let\@underbarchar\_
\def\@underbar{\let\@tempq\@underbarsub\if\@tempz A\let\@tempq\@underbarchar\fi
  \if\@tempz B\let\@tempq\@underbarchar\fi\if\@tempz C\let\@tempq\@underbarchar\fi
  \if\@tempz D\let\@tempq\@underbarchar\fi\if\@tempz E\let\@tempq\@underbarchar\fi
  \if\@tempz F\let\@tempq\@underbarchar\fi\if\@tempz G\let\@tempq\@underbarchar\fi
  \if\@tempz H\let\@tempq\@underbarchar\fi\if\@tempz I\let\@tempq\@underbarchar\fi
  \if\@tempz J\let\@tempq\@underbarchar\fi\if\@tempz K\let\@tempq\@underbarchar\fi
  \if\@tempz L\let\@tempq\@underbarchar\fi\if\@tempz M\let\@tempq\@underbarchar\fi
  \if\@tempz N\let\@tempq\@underbarchar\fi\if\@tempz O\let\@tempq\@underbarchar\fi
  \if\@tempz P\let\@tempq\@underbarchar\fi\if\@tempz Q\let\@tempq\@underbarchar\fi
  \if\@tempz R\let\@tempq\@underbarchar\fi\if\@tempz S\let\@tempq\@underbarchar\fi
  \if\@tempz T\let\@tempq\@underbarchar\fi\if\@tempz U\let\@tempq\@underbarchar\fi
  \if\@tempz V\let\@tempq\@underbarchar\fi\if\@tempz W\let\@tempq\@underbarchar\fi
  \if\@tempz X\let\@tempq\@underbarchar\fi\if\@tempz Y\let\@tempq\@underbarchar\fi
  \if\@tempz Z\let\@tempq\@underbarchar\fi\@tempq}
\def\@under{\futurelet\@tempz\@underbar}

\def\UNDERBARACTIVE{\CATCODE`\_=13}
\UNDERBARACTIVE
\def\UNDERBARDEF{\def_{\protect\@under}}
\UNDERBARDEF

\catcode`\$=11  

%the following line would allow derived-type component references 
%FOO%BAR in running text, but not allow LaTeX comments
%without this line, write FOO\%BAR
%\catcode`\%=11 

\makeatother

%end of file syntax-macs.tex

\title{{\em D R A F T} \\High Performance Fortran \\ FORALL Proposal}
\author{High Performance Fortran Forum}
\date{October 14, 1992}

\hyphenation{RE-DIS-TRIB-UT-ABLE sub-script Wil-liam-son}

\begin{document}

\maketitle

\newpage

\pagenumbering{roman}

\vspace*{4.5in}

This is the result of a LaTeX run of a draft of a single chapter of 
the HPFF Final Report document.

\vspace*{3.0in}

\copyright 1992 Rice University, Houston Texas.  Permission to copy 
without fee all or part of this material is granted, provided the 
Rice University copyright notice and the title of this document 
appear, and notice is given that copying is by permission of Rice 
University.

\tableofcontents

\newpage

\pagenumbering{arabic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%put text of chapter here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%put \end{document} here
%statements.tex

%Revision history:
%August 2, 1992 - Original version of David Loveman, Digital Equipment
%	Corporation and Charles Koelbel, Rice University
%August 19, 1992 - chk - cleaned up discrepancies with Fortran 90 array 
%	expressions
%August 20, 1992 - chk - added DO INDEPENDENT section, Guy Steele's 
%	pointer proposals
%August 24, 1992 - chk - ELEMENTAL functions proposal
%August 31, 1992 - chk - PURE functions proposal
%September 3, 1992 - chk - reorganized sections
%September 21, 1992 - chk - began incorporating updates from Sept
%	10-11 meeting
%October 14, 1992 - chk - Incorporated ON and revised PURE 

\newenvironment{constraints}{
        \begin{list}{Constraint:}{
                \settowidth{\labelwidth}{Constraint:}
                \settowidth{\labelsep}{w}
                \settowidth{\leftmargin}{Constraint:w}
                \setlength{\rightmargin}{0cm}
        }
}{
        \end{list}
}

\chapter{Statements}
\label{statements}

\section{Overview}

\footnote{Version of September 21, 1992 
- Charles Koelbel, Rice University.}
The purpose of the FORALL construct is to provide a convenient syntax for 
simultaneous assignments to large groups of array elements.
In this respect it is very similar to the functionality provided by array 
assignments and WHERE constructs.
FORALL differs from these constructs primarily in its syntax, which is 
intended to be more suggestive of local operations on each element of an 
array.
It is also possible to specify slightly more general array regions than 
are allowed by the basic array triplet notation.
Both single-statement and block FORALLs are defined in this proposal.

The FORALL statement, in both its single-statment and block forms, was
accepted by the High Performance Fortran Forum working group on its
second reading September 10, 1992.
This vote was contingent on a more complete definition of PURE
functions.
The idea of PURE functions was accepted by the HPFF working group at
its first reading on September 10, 1992.
However, the definition at that time was not completely acceptable due to
technical errors; those errors discussed at that time have been
revised in this draft.
The single-statement form of FORALL was accepted by the HPFF working
group as part of the official HPF subset in a first reading on
September 11, 1992; the block FORALL was excluded from the subset at
the same time.

The purpose of the INDEPENDENT directive is to allow the programmer to
give additional information to the compiler.
The user can assert that no data object is defined by one iteration of
a loop and used (read or written) by another; similar information can
be provided about the combinations of index values in a FORALL
statement.
A compiler may rely on this information to make optimizations, such as
parallelization or reorganizing communication.
If the assertion is true, the semantics of the program are not
changed; if it is false, the program is not standard-conforming and
has no defined meaning.
The ``Other Proposals'' section contains a number of additional
assertions with this flavor.

The INDEPENDENT assertion was accepted by the High Performance Fortran
Forum working group on its second reading on September 10, 1992.
The group also directed the FORALL subgroup to further explore methods for
allowing reduction operations to be accomplished in INDEPENDENT loops.

The following proposals are designed as a modification of the Fortran 90 
standard; all references to rule numbers and section numbers pertain to 
that document unless otherwise noted.

\section{Element Array Assignment - FORALL}

\label{forall-stmt}

\footnote{Version of September 21, 1992 - David
Loveman, Digital Equipment Corporation and Charles Koelbel, Rice
University.
Approved at second reading on September 10, 1992.}
The element array
assignment statement (FORALL statement) is used to specify an array
assignment in terms of array elements or groups of array sections.
The element array assignment may be
masked with a scalar logical expression.  
In functionality, it is similar to array assignment statements;
however, more general array sections can be assigned in FORALL.

Rule R215 for {\it
executable-construct} is extended to include the {\it forall-stmt}.

\subsection{General Form of Element Array Assignment}

                                                                       \BNF
forall-stmt          \IS FORALL (forall-triplet-spec-list
                       [,scalar-mask-expr ]) forall-assignment

forall-triplet-spec  \IS subscript-name = subscript : subscript 
                          [ : stride]
                                                                       \FNB

\noindent
Constraint:  {\it subscript-name} must be a {\it scalar-name} of type
integer.

\noindent
Constraint:  A {\it subscript} or a {\it stride} in a {\it
forall-triplet-spec} must not contain a reference to any {\it
subscript-name} in the {\it forall-triplet-spec-list}.

                                                                       \BNF
forall-assignment    \IS array-element = expr
                     \OR array-element => target
                     \OR array-section = expr
                                                                       \FNB

\noindent
Constraint:  The {\it array-section} or {\it array-element} in a {\it
forall-assignment} must reference all of the {\it forall-triplet-spec
subscript-names}.

\noindent
Constraint: In the cases of simple assignment, the {\it array-element} and 
{\it expr} have the same constraints as the {\it variable} and {\it expr} 
in an {\it assignment-stmt}.

\noindent
Constraint: In the case of pointer assignment, the {\it array-element} 
and {\it target} have the same constraints as the {\it pointer-object} 
and {\it target}, respectively, in a {\it pointer-assignment-stmt}.

\noindent
Constraint: In the cases of array section assignment, the {\it 
array-section} and 
{\it expr} have the same constraints as the {\it variable} and {\it expr} 
in an {\it assignment-stmt}.

\noindent Constraint: If any subexpression in {\it expr}, {\it 
array-element}, or {\it array-section} is a {\it function-reference}, 
then the {\it function-name} must be a ``pure'' function as defined in
Section~\ref{forall-pure}.

For each subscript name in the {\it forall-assignment}, the set of
permitted values is determined on entry to the statement and is
\[  m1 + (k-1) * m3, where~k = 1, 2, ..., \lfloor \frac{m2 - m1 +
1}{m3} \rfloor  \]
and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
subscript, the second subscript, and the stride respectively in the
{\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
were present with a value of the integer 1.  The expression {\it
stride} must not have the value 0.  If for some subscript name 
\(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
forall-assignment} is not executed.

A ``pure'' function is defined in Section~\ref{forall-pure}; the
intuition is that a pure function cannot have side effects.
The PURE declaration places syntactic constraints on the function to
ensure this.

Examples of element array assignments are:

                                                                  \CODE
REAL H(N,N), X(N,N), Y(N,N)
TYPE MONARCH
    INTEGER, POINTER :: P
END TYPE MONARCH
TYPE(MONARCH) :: A(N)
INTEGER B(N)
      ...
FORALL (I=1:N, J=1:N) H(I,J) = 1.0 / REAL(I + J - 1)

FORALL (I=1:N, J=1:N, Y(I,J) .NE. 0.0) X(I,J) = 1.0 / Y(I,J)

! Set up a butterfly pattern
FORALL (J=1:N)  A(J)%P => B(1+IEOR(J-1,2**K))
                                                                  \EDOC 

\subsection{Interpretation of Element Array Assignments}  

Execution of an element array assignment consists of the following steps:

\begin{enumerate}

\item Evaluation in any order of the subscript and stride expressions in 
the {\it forall-triplet-spec-list}.
The set of valid combinations of {\it subscript-name} values is then the 
cartesian product of the sets defined by these triplets.

\item Evaluation of the {\it scalar-mask-expr} for all valid combinations 
of {\em subscript-name} values.
The mask elements may be evaluated in any order.
The set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true.

\item Evaluation in any order of the {\it expr} or {\it target} and all 
subscripts contained in the 
{\it array-element} or {\it array-section} in the {\it forall-assignment} 
for all active combinations of {\em subscript-name} values.
In the case of pointer assignment where the {\it target} is not a 
pointer, the evaluation consists of identifying the object referenced 
rather than computing its value.

\item Assignment of the computed {\it expr} values to the corresponding 
elements specified by {\it array-element} or {\it array-section}.
The assignments may be made in any order.
In the case of a pointer assignment where the {\it target} is not a 
pointer, this assignment consists of associating the {\it array-element} 
with the object referenced.

\end{enumerate}

If the scalar mask expression is omitted, it is as if it were
present with the value true.

The scope of a
{\it subscript-name} is the FORALL statement itself. 

The {\it forall-assignment} must not cause any element of the array
being assigned to be assigned a value more than once.

Note that if a function called in a FORALL is declared PURE, then it 
is impossible for that function's evaluation to affect other expressions' 
evaluations, either for the same combination of 
{\it subscript-name} values or for a different combination.
In addition, it is possible that the compiler can perform 
more extensive optimizations when all functions are declared PURE.

\subsection{Scalarization of the FORALL Statement}

A {\it forall-stmt} of the general form:

                                                                   \CODE
FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn , mask ) &
      a(e1,...,em) = rhs
                                                                   \EDOC

\noindent
is equivalent to the following standard Fortran 90 code:

\raggedbottom
                                                                   \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1
templ2 = l2
tempu2 = u2
temps2 = s2
  ...
templn = ln
tempun = un
tempsn = sn

!then evaluate the scalar mask expression

DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        tempmask(v1,v2,...,vn) = mask
      END DO
	  ...
  END DO
END DO

!then evaluate the expr in the forall-assignment for all valid 
!combinations of subscript names for which the scalar mask 
!expression is true (it is safe to avoid saving the subscript 
!expressions because of the conditions on FORALL expressions)

DO v1=templ1,tempu1,temps1
  DO v2=tel2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          temprhs(v1,v2,...,vn) = rhs
        END IF
      END DO
	  ...
  END DO
END DO

!then perform the assignment of these values to the corresponding 
!elements of the array being assigned to

DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          a(e1,...,em) = temprhs(v1,v2,...,vn)
        END IF
      END DO
	  ...
  END DO
END DO
                                                                      \EDOC
\flushbottom

\subsection{Consequences of the Definition of the FORALL Statement}

This section should be moved to the comments chapter in the final
draft.

\begin{itemize}

\item The {\it scalar-mask-expr} may depend on the {\it subscript-name}s.

\item Each of the {\it subscript-name}s 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.)

\item Right-hand sides and subscripts on the left hand side of a {\it 
forall-assignment} are
evaluated only for valid combinations of subscript names for which the
scalar mask expression is true.

\item The intent of ``pure'' functions is to provide a class of
functions without side-effects, and to allow this side-effect freedom
to be checked syntactically.

\end{itemize}

\section{FORALL Construct}

\label{forall-construct}

\footnote{Version of August 20, 1992 -
David Loveman, Digital Equipment Corporation and 
Charles Koelbel, Rice University.  Approved at second reading on
September 10, 1992.}
The FORALL construct is a generalization of the element array
assignment statement allowing multiple assignments, masked array 
assignments, and nested FORALL statements to be
controlled by a single {\it forall-triplet-spec-list}.  Rule R215 for
{\it executable-construct} is extended to include the {\it
forall-construct}.

\subsection{General Form of the FORALL Construct}

                                                                    \BNF
forall-construct   \IS FORALL (forall-triplet-spec-list [,scalar-mask-expr ])
                               forall-body-stmt-list
                            END FORALL

forall-body-stmt     \IS forall-assignment
                     \OR where-stmt
                     \OR forall-stmt
                     \OR forall-construct
                                                                    \FNB

\noindent
Constraint:  {\it subscript-name} must be a {\it scalar-name} of type
integer.

\noindent
Constraint:  A {\it subscript} or a {\it stride} in a {\it
forall-triplet-spec} must not contain a reference to any {\it
subscript-name} in the {\it forall-triplet-spec-list}.

\noindent
Constraint:  Any left-hand side {\it array-section} or {\it 
array-element} in any {\it forall-body-stmt}
must reference all of the {\it forall-triplet-spec
subscript-names}.

\noindent
Constraint: If a {\it forall-stmt} or {\it forall-construct} is nested 
within a {\it forall-construct}, then the inner FORALL may not redefine 
any {\it subscript-name} used in the outer {\it forall-construct}.
This rule applies recursively in the event of multiple nesting levels.

For each subscript name in the {\it forall-assignment}s, the set of
permitted values is determined on entry to the construct and is
\[  m1 + (k-1) * m3, where~k = 1, 2, ..., \lfloor \frac{m2 - m1 +
1)}{m3} \rfloor  \]
and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
subscript, the second subscript, and the stride respectively in the
{\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
were present with a value of the integer 1.  The expression {\it
stride} must not have the value 0.  If for some subscript name 
\(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
forall-assignment}s are not  executed.

Examples of the FORALL construct are:

                                                                 \CODE
FORALL ( I = 2:N-1, J = 2:N-1 )
  A(I,J) = A(I,J-1) + A(I,J+1) + A(I-1,J) + A(I+1,J)
  B(I,J) = A(I,J)
END FORALL

FORALL ( I = 1:N-1 )
  FORALL ( J = I+1:N )
    A(I,J) = A(J,I)
  END FORALL
END FORALL

FORALL ( I = 1:N, J = 1:N )
  A(I,J) = MERGE( A(I,J), A(I,J)**2, I.EQ.J )
  WHERE ( .NOT. DONE(I,J,1:M) )
    B(I,J,1:M) = B(I,J,1:M)*X
  END WHERE
END FORALL
                                                                \EDOC

\subsection{Interpretation of the FORALL Construct}

Execution of a FORALL construct consists of the following steps:

\begin{enumerate}

\item Evaluation in any order of the subscript and stride expressions in 
the {\it forall-triplet-spec-list}.
The set of valid combinations of {\it subscript-name} values is then the 
cartesian product of the sets defined by these triplets.

\item Evaluation of the {\it scalar-mask-expr} for all valid combinations 
of {\em subscript-name} values.
The mask elements may be evaluated in any order.
The set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true.

\item Execute the {\it forall-body-stmts} in the order they appear.
Each statement is executed completely (that is, for all active 
combinations of {\it subscript-name} values) according to the following 
interpretation:

\begin{enumerate}

\item Assignment statements, pointer assignment statements, and array
assignment statements (i.e.
statements in the {\it forall-assignment} category) evaluate the 
right-hand side {\it expr} and any left-and side subscripts for all 
active {\it subscript-name} values,
then assign those results to the corresponding left-hand side references.

\item WHERE statements evaluate their {\it mask-expr} for all active 
combinations of values of {\it subscript-name}s.
All elements of all masks may be evaluated in any order. 
The assignments within the WHERE branch of the statement are then 
executed in order using the above interpretation of array assignments 
within the FORALL, but the only array elements assigned are those 
selected by both the active {\it subscript-names} and the WHERE mask.
Finally, the assignments in the ELSEWHERE branch are executed if that 
branch is present.
The assignments here are also treated as array assignments, but elements 
are only assigned if they are selected by both the active combinations 
and by the negation of the WHERE mask.

\item FORALL statements and FORALL constructs first evaluate the 
subscript and stride expressions in 
the {\it forall-triplet-spec-list} for all active combinations of the 
outer FORALL constructs.
The set of valid combinations of {\it subscript-names} for the inner 
FORALL is then the union of the sets defined by these bounds and strides 
for each active combination of the outer {\it subscript-names}.
For example, the valid set of the inner FORALL in the second example in 
the last section is the upper triangle (not including the main diagonal) 
of the \(n \times n\) matrix a.
The scalar mask expression is then evaluated for all valid combinations 
of the inner FORALL's {\it subscript-names} to produce the set of active 
combinations.
If there is no scalar mask expression, it is assumed to be always true.
Each statement in the inner FORALL is then executed for each valid 
combination (of the inner FORALL), recursively following the 
interpretations given in this section.

\end{enumerate}

\end{enumerate}

If the scalar mask expresion is omitted, it is as if it were
present with the value true.

The scope of a
{\it subscript-name} is the FORALL construct itself. 

A single assignment or array assignment statement in a {\it 
forall-construct} must obey the same restrictions as a {\it 
forall-assignment} in a simple {\it forall-stmt}.
(Note that the lowest level of nested statements must always be an 
assignment statement.)
For example, an assignment may not cause the same array element to be 
assigned more than once.
Different statements may, however, assign to the 
same array element, and assignments made in one
statement may affect the execution of a later statement.

\subsection{Scalarization of the FORALL Construct}

A {\it forall-construct} othe form:

                                                                \CODE
FORALL (... e1 ... e2 ... en ...)
    s1
    s2
     ...
    sn
END FORALL
                                                                \EDOC

where each si is an assignment is equivalent to the following scalar code:

                                                                \CODE
temp1 = e1
temp2 = e2
 ...
tempn = en
FORALL (... temp1 ... temp2 ... tempn ...) s1
FORALL (... temp1 ... temp2 ... tempn ...) s2
   ...
FORALL (... temp1 ... temp2 ... tempn ...) sn
                                                                \EDOC

A similar statement can be made using FORALL constructs when the 
si may be WHERE or FORALL constructs.

A {\it forall-construct} of the form:

                                                                \CODE
FORALL ( v1=l1:u1:s1, mask )
  WHERE ( mask2(l2:u2) )
    a(vi,l2:u2) = rhs1
  ELSEWHERE
    a(vi,l2:u2) = rhs2
  END WHERE
END FORALL
                                                                \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1

!then evaluate the FORALL mask expression

DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the masks for the WHERE

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    tmpl2(v1) = l2
    tmpu2(v1) = u2
    tempmask2(v1,tmpl2(v1):tmpu2(v1)) = mask2(tmpl2(v1):tmpu2(v1))
  END IF
END DO

!then evaluate the WHERE branch

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      temprhs1(v1,tmpl2(v1):tmpu2(v1)) = rhs1
    END WHERE
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      a(v1,tmpl2(v1):tmpu2(v1)) = temprhs1(v1,tmpl2(v1):tmpu2(v1))
    END WHERE
  END IF
END DO

!then evaluate the ELSEWHERE branch

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( .not. tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      temprhs2(v1,tmpl2(v1):tmpu2(v1)) = rhs2
    END WHERE
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( .not. tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      a(v1,tmpl2(v1):tmpu2(v1)) = temprhs2(v1,tmpl2(v1):tmpu2(v1))
    END WHERE
  END IF
END DO
                                                                   \EDOC

A {\it forall-construct} of the form:

                                                                   \CODE
FORALL ( v1=l1:u1:s1, mask )
  FORALL ( v2=l2:u2:s2, mask2 )
    a(e1,e2) = rhs1
	b(e3,e4) = rhs2
  END FORALL
END FORALL
                                                                  \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                   \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1

!then evaluate the FORALL mask expression

DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the inner FORALL bounds, etc

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    templ2(v1) = l2
    tempu2(v1) = u2
    temps2(v1) = s2
    DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      tempmask2(v1,v2) = mask2
    END DO
  END IF
END DO

!first statement

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      IF ( tempmask2(v1,v2) ) THEN
        temprhs1(v1,v2) = rhs1
      END IF
    END DO
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      IF ( tempmask2(v1,v2) ) THEN
        a(e1,e2) = temprhs1(v1,v2)
      END IF
    END DO
  END IF
END DO

!second statement

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      IF ( tempmask2(v1,v2) ) THEN
        temprhs2(v1,v2) = rhs2
      END IF
    END DO
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      IF ( tempmask2(v1,v2) ) THEN
        b(e3,e4) = temprhs2(v1,v2)
      END IF
    END DO
  END IF
END DO
                                                                   \EDOC

\subsection{Consequences of the Definition of the FORALL Construct}

This section should be moved to the comments chapter of the final
draft.

\begin{itemize}

\item A block FORALL means roughly 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.
(The exceptions to this rule are nested FORALL statements and WHERE
statements, which introduce syntactic and functional complications
into the copying.)

\item One may think of a block FORALL as synchronizing twice per
contained assignment statement: once after handling the rhs and other 
expressions
but before performing assignments, and once after all assignments have
been performed but before commencing the next statement.  (In practice,
appropriate dependence analysis will often permit the compiler to
eliminate unnecessary synchronizations.)

\item The {\it scalar-mask-expr} may depend on the {\it subscript-name}s.

\item In general, any expression in a FORALL is evaluated only for valid 
combinations of all surrounding subscript names for which all the
scalar mask eressions are true.

\item Nested FORALL bounds and strides can depend on outer FORALL {\it 
subscript-names}.  They cannot redefine those names, even temporarily (if 
they did there  would be no way to avoid multiple assignments to the same 
array element).

\item Dependences are allowed from one statement to later statements, but 
never from an assignment statement to itself.

\end{itemize}

\section{Pure Procedures and Elemental Reference}

\label{forall-pure}

\footnote{Version of October 14, 
1992 - John Merlin, University of Southampton, 
and Charles Koelbel, Rice University. Approved at first reading on
September 10, 1992, subject to technical revisions for correctness.
The suggestions made there have been incorporated in this draft.}
A {\it pure function\/} is one that produces no side effects.  This
means that the only effect of a pure function reference on the state 
of a program is to return a result---it does not modify the values, 
pointer associations or data mapping of any of its arguments or global 
data, and performs no I/O.
A {\em pure subroutine\/} is one that produces no side effects
except for modifying the values and/or pointer associations of certain
arguments.  

A pure procedure (i.e.\ function or subroutine) may be used in any way 
that a normal procedure can.
In addition, a procedure is required to be pure if it is used in any 
of the following contexts:
\begin{itemize}
        \item a FORALL statement or construct;
        \item an elemental reference (see section \ref{elem-ref-of-pure-procs});
        \item within the body of a pure procedure;
        \item as an actual argument in a pure procedure reference.
\end{itemize}

The side-effect freedom of a pure function ensures that it can be invoked
concurrently in a FORALL or elemental reference without undesirable
consequences such as non-determinism, and additionally assists the efficient
implementation of concurrent execution.  A pure subroutine can be
invoked concurrently in an elemental reference, and since its side effects
are limited to a known subset of its arguments (as we shall see later), 
an implementation can check that a reference obeys Fortran~90's restrictions 
on argument association and is consequently deterministic.

\subsection{Pure procedure declaration and interface}

If a non-intrinsic procedure is used in a context that requires it to be 
pure, then its interface must be explicit in the scope of that use, 
and both its interface body (if provided) and its definition must contain 
the PURE declaration.  The form of this declaration is 
a directive immediately after the {\it function-stmt\/} or {\it
subroutine-stmt\/} of the procedure interface body or definition:
                                                                 \BNF
pure-directive \IS !HPF$ PURE [procedure-name]
                                                                 \FNB

Intrinsic functions, including HPF intrinsic functions, are always pure 
and require no explicit declaration of this fact;  intrinsic subroutines 
are pure if they are elemental (e.g.\ MVBITS) but not otherwise.
A statement function is pure if and only if all functions that it
references are pure.

\subsubsection{Pure function definition}

To define pure functions, Rule~R1215 of the Fortran~90 standard is changed 
to:
                                                                 \BNF
function-subprogram \IS         function-stmt
                                [pure-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-function-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.2 of the 
Fortran~90 standard:
\begin{constraints}

        \item If a {\it procedure-name\/} is present in the 
{\it pure-directive\/}, it must match the {\it function-name\/} in the 
{\it function-stmt\/}.

        \item In a pure function, a local variable must not have the 
SAVE attribute. (Note that this means that a local variable cannot be 
initialised in a {\it type-declaration-stmt\/} or a
{\it data-stmt\/}, which imply the SAVE attribute.)

        \item A pure function must not use a dummy argument, a global 
variable, or an object that is storage associated with a global variable,
or a subobject thereof, in the following contexts:
        \begin{itemize}
                \item as the assignment variable of an {\it assignment-stmt\/}
or {\it forall-assignment\/};
                \item as a DO variable or implied DO variable, or as a 
{\it subscript-name\/} in a {\it forall-triplet-spec\/};
                \item in an {\it assign-stmt\/};
                \item as the {\it pointer-object\/} or {\it target\/}
of a {\it pointer-assignment-stmt\/};
                \item as the {\it expr\/} of an {\it assignment-stmt\/}
or {\it forall-assignment\/} whose assignment variable is of a derived 
type, or is a pointer to a derived type, that has a pointer component 
at any level of component selection;
                \item as an {\it allocate-object\/} or {\it stat-variable\/}
in an {\it allocate-stmt\/} or {\it deallocate-stmt\/}, or as a
{\it pointer-object\/} in a {\it nullify-stmt\/};
                \item as an actual argument associated with a dummy 
argument with INTENT (OUT) or (INOUT) or with the POINTER attribute.
        \end{itemize}

        \item Any procedure referenced in a pure function, including
one referenced via a defined operation or assignment, must be pure.

        \item In a pure function, a dummy argument or local variable 
must not appear in an {\it align-directive\/}, {\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a pure function, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A pure function must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}
To declare that a function is pure, a {\it pure-directive\/} must be given.

The above constraints are designed to guarantee that a pure function
is free from side effects (i.e.\ modifications of data visible outside
the function), which means that it is safe to reference concurrently, 
as explained earlier.

The second constraint ensures that a pure function does not retain
an internal state between calls, which would allow side-effects between 
calls to the same procedure.

The third constraint ensures that dummy arguments and global variables
are not modified by the function.
In the case of a dummy or global pointer, this applies to both its 
pointer association and its target value, so it cannot be subject to 
a pointer assignment or to an ALLOCATE, DEALLOCATE or NULLIFY
statement.
Incidentally, these constraints imply that only local variables and the
dummy result variable can be subject to assignment or pointer assignment.

In addition, a dummy or global data object cannot be the {\it target\/}
of a pointer assignment (i.e.\ it cannot be used as the right hand side
of a pointer assignment to a local pointer or to the result variable), 
for then its value could be modified via the pointer.

In connection with the last point, it should be noted that an ordinary 
(as opposed to pointer) assignment to a variable of derived type that has 
a pointer component at any level of component selection may result in a 
{\em pointer\/} assignment to the pointer component of the variable.
That is certainly the case for an intrinsic assignment.  In that case
the expression on the right hand side of the assignment has the same type 
as the assignment variable, and the assignment results in a pointer 
assignment of the pointer components of the expression result to the
corresponding components of the variable (see section 7.5.1.5 of the 
Fortran~90 standard).  However, it may also be the case for a 
{\em defined\/} assignment to such a variable, even if the data type of 
the expression has no pointer components;  the defined assignment may still 
involve pointer assignment of part or all of the expression result to the 
pointer components of the assignment variable.  Therefore, a dummy or 
global object cannot be used as the right hand side of any assignment to 
a variable of derived type with pointer components, for then it, or part 
of it, might be the target of a pointer assignment, in violation of the 
restriction mentioned above.

(Incidentally, the last two paragraphs only prevent the reference of 
a dummy or global object as the {\em only\/} object on the right hand
side of a pointer assignment or an assignment to a variable with pointer
components.  There are no constraints on its reference as an operand, 
actual argument, subscript expression, etc.\ in these circumstances).

Finally, a dummy or global data object cannot be used in a procedure 
reference as an actual argument associated with a dummy argument of
INTENT (OUT) or (INOUT) or with a dummy pointer, for then it may be
modified by the procedure reference.  
This constraint, like the others, can be statically checked, since any
procedure referenced within a pure function must be either a pure 
function, which does not modify its arguments, or a pure subroutine, 
whose interface must specify the INTENT or POINTER attributes of its 
arguments (see below).
Incidentally, notice that in this context it is assumed that an actual 
argument associated with a dummy pointer is modified, since Fortran~90 
does not allow its intent to be specified.

Constraint 4 ensures that all procedures called from a pure function 
are themselves pure and hence side effect free, except, in the case of
subroutines, for modifying actual arguments associated with dummy pointers 
or dummy arguments with INTENT(OUT) or (INOUT).  As we have just 
explained, it can be checked that global or dummy objects are not used
in such arguments, which would violate the required side-effect freedom.

Constraints 5 and 6 protect dummy and global data objects from realignment 
and redistribution (another type of side effect).  
In addition, constraint 5 prevents explicit declaration of the mapping 
(i.e.\ alignment and distribution) of dummy arguments and local variables.  
This is because the function may be invoked concurrently, with each 
invocation operating on a segment of data whose distribution is specific 
to that invocation.  Thus, the distribution of a dummy object must be 
`assumed' from the corresponding actual argument.  
Also, it is left to the implementation to determine a suitable mapping 
of the local variables, which would typically depend on the mapping of 
the dummy arguments.

Constraint 7 prevents I/O, whose order would be non-deterministic in 
the context of concurrent execution.  A PAUSE statement requires input
and so is disallowed for the same reason.

\subsubsection{Pure subroutine definition}

To define pure subroutines, Rule~R1219 is changed to:
                                                                 \BNF
subroutine-subprogram \IS       subroutine-stmt
                                [pure-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-subroutine-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.3 of the 
Fortran~90 standard:
\begin{constraints}

        \item If a {\it procedure-name\/} is present in the 
{\it pure-directive\/}, it must match the {\it sub\-rou\-tine-name\/} in the 
{\it subroutine-stmt\/}.

        \item The {\it specification-part\/} of a pure subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item In a pure subroutine, a local variable must not have the 
SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item A pure subroutine must not use a dummy parameter with 
        INTENT(IN), a global variable, or an 
object that is storage associated with a global variable, or a subobject 
thereof, in the following contexts:
        \begin{itemize}
                \item as the assignment variable of an {\it assignment-stmt\/}
or {\it forall-assignment\/};
                \item as a DO variable or implied DO variable, or as a 
{\it subscript-name\/} in a {\it forall-triplet-spec\/};
                \item in an {\it assign-stmt\/};
                \item as the {\it pointer-object\/} or {\it target\/}
of a {\it pointer-assignment-stmt\/};
                \item as the {\it expr\/} of an {\it assignment-stmt\/}
or {\it forall-assignment\/} whose assignment variable is of a derived 
type, or is a pointer to a derived type, that has a pointer component 
at any level of component selection;
                \item as an {\it allocate-object\/} or {\it stat-variable\/}
in an {\it allocate-stmt\/} or {\it deallocate-stmt\/}, or as a
{\it pointer-object\/} in a {\it nullify-stmt\/};
                \item as an actual argument associated with a dummy 
argument with INTENT (OUT) or (INOUT) or with the POINTER attribute.
        \end{itemize}

        \item Any procedure referenced in a pure subroutine, including
one referenced via a defined operation or assignment, must be pure.

        \item In a pure subroutine, a dummy argument or local variable 
must not appear in an {\it align-directive\/}, {\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a pure subroutine, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A pure subroutine must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}
To declare that a subroutine is pure, a {\it pure-directive\/} must be
given.

The constraints for pure subroutines are based on the same principles 
as for pure functions, except that now side effects to dummy arguments 
are permitted.  

\subsubsection{Pure procedure interfaces}
\label{pure-proc-interface}

To define interface specifications for pure procedures, Rule~R1204 is 
changed to:
                                                                \BNF
interface-body \IS      function-stmt
                        [pure-directive]
                        [specification-part]
                        end-function-stmt
                \OR     subroutine-stmt
                        [pure-directive]
                        [specification-part]
                        end-subroutine-stmt
                                                                \FNB
with the following constraint in addition to those in
Section~12.3.2.1 of the Fortran~90 standard:
\begin{constraints}

        \item An {\it interface-body\/} of a pure subroutine must specify
the intents of all non-pointer and non-procedure dummy arguments.

\end{constraints}

The procedure characteristics defined by an interface body must be
consistent with the procedure's definition.
Regarding pure procedures, this is interpreted as follows:
\begin{enumerate}
        \item A procedure that is declared pure at its definition may be
declared pure in an interface block, but this is not required.
        \item A procedure that is not declared pure at its definition must 
not be declared pure in an interface block.
\end{enumerate}
That is, if an interface body contains a {\it pure-directive\/}, then the 
corresponding procedure definition must also contain it, though the 
reverse is not true.
When a procedure definition with a {\it pure-directive\/}
is compiled, the compiler may check that it satisfies the necessary 
constraints.

\subsection{Pure procedure reference}
To define pure procedure references, the following extra constraint is 
added to Section~12.4.1 of the Fortran~90 standard:
\begin{constraints}

        \item In a reference to a pure procedure, a {\it procedure-name\/} 
{\it actual-arg\/} must be the name of a pure procedure.

\end{constraints}

\subsection{Elemental reference of pure procedures}
\label{elem-ref-of-pure-procs}

Fortran 90 introduces the concept of `elemental procedures', which are 
defined for scalar arguments but may also be applied to conforming 
array-valued arguments.  The latter type of reference to an elemental 
procedure is called an `elemental' reference.    For an elemental function, 
each element of the result, if any, is as would have been obtained by
applying the function to corresponding elements of the arguments.
Examples are the mathematical intrinsics, e.g.\ SIN(X).  For an elemental 
subroutine, the effect on each element of an INTENT(OUT) or INTENT(INOUT) 
array argument is as would be obtained by calling the subroutine with 
the corresponding elements of the arguments.  An example is the intrinsic 
subroutine MVBITS.

However, Fortran~90 restricts elemental reference to a subset of 
the intrinsic procedures --- programmers cannot define their own 
elemental procedures.  Obviously, elemental invocation is equivalent 
to concurrent invocation, so extra constraints beyond those for normal 
Fortran procedures are required to allow this to be done safely
(e.g.\ deterministically).  Appropriate constraints in this case are
the same as for function calls in FORALL;  indeed, the latter are 
virtually equivalent to elemental reference of the function in an 
array assignment, given the close correspondence between FORALL and 
array assignment.  Hence, pure procedures may also be referenced 
elementally, subject to certain additional constraints given below.

\subsubsection{Elemental reference of pure functions}

A non-intrinsic pure function may be referenced {\em elementally\/} 
in array expressions, with a similar interpretation to the elemental
reference of Fortran~90 elemental intrinsic functions, provided it
satisfies the additional constraints that:
\begin{enumerate}
        \item Its non-procedure dummy arguments and dummy result are 
scalar and do not have the POINTER attribute.
        \item The length of any character dummy argument or result is 
independent of argument values (though it may be assumed, or depend on the 
lengths of other character arguments and/or a character result).
\end{enumerate}
We call non-intrinsic pure functions that satisfy these constraints 
`elemental non-intrinsic functions'.

The interpretation of an elemental reference of such a function is as 
follows (adapted from Section 12.4.3 of the Fortran~90 standard):
\begin{quotation}

A reference to an elemental non-intrinsic function is an elemental
reference if one or more non-procedure actual arguments are arrays
and all array arguments have the same shape.  If any actual argument 
is a function, its result must have the same shape as that of the 
corresponding function dummy procedure.  A reference to an elemental 
intrinsic function is an elemental reference if one or more actual 
arguments are arrays and all arrays have the same shape.

The result of such a reference has the same shape as the array arguments,
and the value of each element of the result, if any, is obtained by 
evaluating the function using the scalar and procedure arguments and
the corresponding elements of the array arguments.  The elements of
the result may be evaluated in any order.

For example, if \verb@foo@ is a pure function with the following interface:
                                                \CODE
    INTERFACE
      REAL FUNCTION foo (x, y, z, dummy_func)
        !HPF$ PURE foo
        REAL, INTENT(IN) :: x, y, z
        INTERFACE        ! interface for 'dummy_func'
          REAL FUNCTION dummy_func (x)
            !HPF$ PURE dummy_func
            REAL, INTENT(IN) :: x
          END FUNCTION dummy_func
        END INTERFACE
      END FUNCTION foo
    END INTERFACE
                                                \EDOC
and \verb@a@ and \verb@b@ are arrays of shape \verb@(m,n)@ and \verb@sin@
is the Fortran~90 elemental intrinsic function, then:
                                                \CODE
    foo (a, 0.0, b, sin)
                                                \EDOC
is an array expression of shape \verb@(m,n)@ whose \verb@(i,j)@ element
has the value:
                                                \CODE
    foo (a(i,j), 0.0, b(i,j), sin)
                                                \EDOC
\end{quotation}

To define elemental references of elemental non-intrinsic functions, 
the following extra constraints are added after Rule~R1209 
({\it function-reference\/}):
\begin{constraints}

        \item A non-intrinsic function that is referenced elementally 
must be a pure function with an explicit interface, and must satisfy 
the following additional constraints:
        \begin{itemize}
                \item Its non-procedure dummy arguments and dummy result
must be scalar and must not have the POINTER attribute.
                \item The length of any character dummy argument or a 
character dummy result must not depend on argument values (though it may 
be assumed, or depend on the lengths of other character arguments and/or a 
character result).
        \end{itemize}

        \item In an elemental reference of a non-intrinsic function,
a {\it function-name\/} {\it actual-arg\/} must have a result whose shape 
agrees with that of the corresponding function dummy procedure.

\end{constraints}

The reasons for these constraints are explained in the next section.

\subsubsection{Elemental reference of pure subroutines}

A non-intrinsic pure subroutine may be referenced {\em elementally\/}, 
with a similar interpretation to the elemental reference of Fortran~90 
elemental intrinsic subroutines, provided it satisfies the additional 
constraints that:
\begin{enumerate}
        \item Its non-procedure dummy arguments are scalar and do not 
have the POINTER attribute.
        \item The length of any character dummy argument is independent 
of argument values (though it may be assumed, or depend on the lengths of 
other character arguments).
\end{enumerate}
We call non-intrinsic pure subroutines that satisfy these constraints 
`elemental non-intrinsic subroutines'.

The interpretation of an elemental reference of such a subroutine 
is as follows (adapted from Section 12.4.5 of the Fortran~90 standard):
\begin{quotation}

A reference to an elemental non-intrinsic subroutine is an elemental
reference if all actual arguments corresponding to INTENT(OUT) and
INTENT(INOUT) dummy arguments are arrays that have the same shape 
and the remaining non-procedure actual arguments are conformable with 
them.  If any actual argument is a function, its result must have the 
same shape as that of the corresponding function dummy procedure.
A reference to an elemental intrinsic subroutine is an elemental 
reference if all actual arguments corresponding to INTENT(OUT) and 
(INTENT(INOUT) dummy arguments are arrays that have the same shape and 
the remaining actual arguments are conformable with them.

The values of the elements of the arrays that correspond to INTENT(OUT)
and INTENT(INOUT) dummy arguments are the same as if the subroutine were 
invoked separately, in any order, using the scalar and procedure arguments 
and corresponding elements of the array arguments.

\end{quotation}

To define elemental references of elemental non-intrinsic subroutines, 
the following constraints are added after Rule~R1210 ({\it call-stmt\/}):
\begin{constraints}

        \item A non-intrinsic subroutine that is referenced elementally 
must be a pure subroutine with an explicit interface, and must satisfy 
the following additional constraints:
        \begin{itemize}
                \item Its non-procedure dummy arguments must be scalar 
and must not have the POINTER attribute.
                \item The length of any character dummy argument must 
not depend on argument values (though it may be assumed, or depend on 
the lengths of other character arguments).
        \end{itemize}

        \item In an elemental reference of a non-intrinsic subroutine,
a {\it function-name\/} {\it actual-arg\/} must have a result whose shape 
agrees with that of the corresponding function dummy procedure.

\end{constraints}

It is perhaps worth outlining the reasons for the extra constraints 
imposed on pure procedures in order for them to be referenced elementally.  

The dummy result of a function or `output' arguments of a subroutine
are not allowed to have the POINTER attribute because of a Fortran~90
technicality, namely, that under elemental reference the corresponding 
actual arguments must be array variables, and Fortran~90 does not permit 
an array of pointers to be referenced.\footnote{
        See the final constraint after Rule~R613 of the Fortran~90 standard.
Note the difference between an {\em array of pointers\/}, which cannot 
be declared or referenced in Fortran~90, and a {\em pointer array\/},
which can.
}
The `input' arguments of an elemental reference are prohibited from 
having the POINTER attribute for consistency with the output arguments 
or result.  However, this last constraint does not impose 
any real restrictions on an elemental reference, as the corresponding 
actual arguments {\em can\/} be pointers, in which case they are 
`de-referenced' and their targets are associated with the dummy arguments.  
In fact, the only reason for a dummy argument to be a pointer is so that
its pointer association can be changed, which is not allowed for `input'
arguments.  (Incidentally, since a pure function has only `input' 
arguments, there would be no loss of generality in disallowing dummy 
pointers in pure functions generally.)  Note that the prohibition of 
dummy pointers in pure subroutines that are elementally referenced means 
that all their non-procedure dummy arguments can have their intent 
explicitly specified (and indeed this is required by the constraints for 
pure subroutine interfaces---see Section \ref{pure-proc-interface}) which 
assists the checking of argument usage.

In an elemental reference, any actual argument that is a function
must have a result whose shape agrees with that of the corresponding 
function dummy procedure.  That is, elemental usage does not extend to 
function arguments, as Fortran~90 does not support the concept of an `array' 
of functions.
Naively it might appear that a function actual argument that is associated 
with a scalar dummy function could return an array result provided it 
conforms with the other array arguments of the elemental reference.  
However, this is not meaningful under elemental reference, as an 
array-valued function cannot be decomposed into an `array' of scalar 
function references, as would be required in this context.

Finally, the length of any character dummy argument or a character
dummy result cannot depend on argument {\em values\/} (though it can
be assumed, or depend on the lengths of other character arguments and/or
a character result).  This ensures that under elemental reference, all 
elements of an array argument or result of character type will have the 
same length, as required by Fortran~90.

\subsection{Examples of pure procedure usage}

\subsubsection{FORALL statements and constructs}

Pure functions may be used in expressions in FORALL statements and 
constructs, unlike general functions.  
Because a {\it forall-assignment}
may be an {\it array-assignment} the pure function can have an array
result.  
For example:
                                                              \CODE
INTERFACE
  FUNCTION f (x)
    !HPF$ PURE f
    REAL, DIMENSION(3) :: f, x
  END FUNCTION f
END INTERFACE
REAL  v (3,10,10)
...
FORALL (i=1:10, j=1:10)  v(:,i,j) = f (v(:,i,j)) 
                                                              \EDOC

\subsubsection{Elemental references}
Examples of elemental function usage are
                                                              \CODE
INTERFACE 
  REAL FUNCTION foo (x, y, z)
    !HPF$ PURE foo
    REAL, INTENT(IN) :: x, y, z
  END FUNCTION foo
END INTERFACE

REAL a(100), b(100), c(100)
REAL p, q, r

a(1:n) = foo (a(1:n), b(1:n), c(1:n))
a(1:n) = foo (a(1:n), q, r)
a = sin(b)
                                                              \EDOC
An example involving a WHERE-ELSEWHERE construct is
                                                              \CODE
INTERFACE
  REAL FUNCTION f_egde (x)
    !HPF$ PURE
    REAL x
  END FUNCTION f_edge
  REAL FUNCTION f_interior (x)
    !HPF$ PURE
    REAL x
  END FUNCTION f_interior
END INTERFACE

REAL a (10,10)
LOGICAL edges (10,10)

WHERE (edges)
  a = f_egde (a)
ELSE WHERE
  a = f_interior (a)
END WHERE
                                                          \EDOC

Examples of elemental subroutine usage are
                                                                \CODE
INTERFACE 
  SUBROUTINE solve_simul(tol, y, z)
    !HPF$ PURE solve_simul
    REAL, INTENT(IN) :: tol
    REAL, INTENT(INOUT) :: y, z
  END SUBROUTINE
END INTERFACE

REAL a(100), b(100), c(100)
INTEGER bits(10)

CALL solve_simul( 0.1, a, b )
CALL solve_simul( c, a, b )
CALL mvbits( bits, 0, 4, bits, 4) ! Fortran 90 elemental intrinsic
                                                                \EDOC

User-defined elemental procedures have several potential advantages.
They are a convenient programming tool, as the same procedure 
can be applied to actual arguments of any rank.

In addition, the implementation of an elemental function returning an
array-valued result in an array expression is likely to be more 
efficient than that of an equivalent array function.  One reason is 
that it requires less temporary storage for the result (i.e.\ storage 
for a single result versus storage for the entire array of results).  
Another is that it saves on looping if an array expression is 
implemented by sequential iteration over the component elemental 
expressions (as may be done for the `segment' of the array expression 
local to each process).  This is because, in the sequential version, 
the elemental function can be invoked elementally in situ within the 
expression.  The array function, on the other hand, must be executed 
before the expression is evaluated, storing its result in a temporary 
array for use within the expression.  Looping is then required during 
the execution of the array function body as well as the expression 
evaluation.

\subsection{MIMD parallelism via pure procedures}

We have seen that a pure procedure may be invoked concurrently at each
`element' of an array if it is referenced elementally or in a FORALL 
statement or construct (where an `element' may itself be an array in
a non-elemental reference).  In these cases, a limited form of MIMD 
parallelism can be obtained by means of branches within the pure procedure 
which depend on arguments associated with array elements or their 
subscripts (the latter especially in a FORALL context).  For example:
                                                              \CODE
    FUNCTION f (x, i)
      !HPF$ PURE f
      REAL x       ! associated with array element
      INTEGER i    ! associated with array subscript
      IF (x > 0.0) THEN     ! content-based conditional
        ...
      ELSE IF (i==1 .OR. i==n) THEN    ! subscript-based conditional
        ...
      ENDIF
    END FUNCTION

    ...
    REAL a(n)
    INTEGER i
    ...
    FORALL (i=1:n)  a(i) = f( a(i), i)
    ...
    a = f( a, (/i,i=1,n/) )     ! an elemental reference equivalent
                                ! to the above FORALL

                                                              \EDOC
This may sometimes provide an alternative to using
WHERE-ELSEWHERE constructs or sequences of masked FORALLs with their 
potential synchronisation overhead. 

\subsection{Comments}

This section should be moved to the comments chapter of the final draft.

\subsubsection{Pure procedures}

\begin{itemize}

\item The constraints for a pure procedure guarantee
freedom from side-effects, thus ensuring that it can be invoked
concurrently at each
`element' of an array (where an ``element'' may itself be a data-structure, 
including an array).

\item All constraints can be statically checked, thus providing safety
for the programmer.

Of course, a price that must be paid for this additional security is
that the constraints must be quite rigorous, which means that it
is possible to write a function that is side-effect free in behaviour
but which nevertheless fails to satisfy the constraints 
(e.g.\ a function that contains an assignment to a global variable,
but in a branch that is not executed in any invocation of the function
during a particular program execution).

\item It is expected that most High Performance Fortran library 
procedures will conform to the constraints required of pure procedures
(by the very nature of library procedures), and so can be declared pure 
and referenced in FORALL statements and constructs (if they are functions) 
and within user-defined pure procedures.  It is also anticipated that 
most library procedures will not reference global data, whose use may 
sometimes inhibit concurrent execution (see below).

The constraints on pure procedures are limited to those necessary 
for statically checkable side-effect freedom and the elimination 
of saved internal state.  Subject to these restrictions, maximum 
functionality has been preserved in the definition of pure procedures.
This has been done to make elemental reference and function calls in 
FORALL as widely available as possible, and so that quite general library 
procedures can be classified as pure.  

A drawback of this flexibility is that pure procedures permit certain 
features whose use may hinder, and in the worst case prevent, concurrent 
execution in FORALL and elemental references (that is, such references 
may have to be implemented by sequentialisation).  
Foremost among these features are the access of global data, particularly 
distributed global data, and the fact that the arguments and, for a pure 
function, the result may be pointers or data structures with pointer 
components, including recursive data structures such as lists and trees.
The programmer should be aware of the potential performance penalties 
of using such features.

\item An earlier draft of this proposal contained a constraint disallowing 
pure procedures from accessing global data objects, particularly
distributed data objects.
This constraint has been dropped as inessential to the side-effect freedom 
that the HPF committee requested.
However, it may well be that some machines will have great difficulty 
implementing FORALL without this constraint.

\item One of us (JHM) is still in favour of disallowing access to global 
variables for a number of reasons: 
\begin{enumerate}
\item Aesthetically, it is in keeping with the
nature of a `pure' function, i.e. a function in the mathematical
sense, and in practical terms it imposes no real restrictions on the 
programmer, as global data can be passed-in via the argument list; 
\item Without this constraint HPF programs can no longer be implemented 
by pure message-passing, or at least not efficiently, i.e. without
sequentialising FORALL statements containing function calls and greatly
complicating their implementation; 
\item Absence of this restriction may inhibit optimisation of FORALLs
and array assignments, as the optimisation of assigning the {\it expr\/}
directly to the assignment variable rather than to a temporary intermediate
array now requires interprocedural analysis rather than just local 
analysis.
\end{enumerate}

\end{itemize}

\subsubsection{Elemental references}

\begin{itemize}

\item The original draft proposed allowing pure procedures 
to be invoked elementally even if their dummy arguments or results 
were array-valued.  These provisions have been dropped to avoid 
promoting storage order to a higher level in Fortran~90
(i.e.\ to avoid introducing the concept of `arrays-if-arrays', 
which Fortran~90 seems to strenuously avoid!)   In practical terms,
the current proposal provides the same functionality as the original 
one for functions, though not for subroutines.  If a programmer wants 
elemental function behaviour, but also wants the `elements' to be
array-valued, this can be achieved using FORALL.

\item In typical FORALL or elemental implementation, a pure procedure 
would be called independently in each process, and its dummy arguments 
would be associated with `elements' local to that process. 
This is the reason for disallowing data mapping directives for
local and dummy variables within the bodies of such procedures.
Note that, particularly in elemental invocations, the actual arguments
can be distributed arrays which need not be `co-distributed'; if not,
a typical implementation would in general perform all data communications 
prior to calling the procedure, and would then pass-in the required 
elements locally via its argument list.

However, access to large global data structures such as look-up tables
is often useful within functions that are otherwise mathematically pure,
and these are allowed to be distributed.

\end{itemize}

\section{The INDEPENDENT Directive}

\label{do-independent}

\footnote{Version of August 20, 1992
 - Guy Steele, Thinking Machines Corporation, and 
Charles Koelbel, Rice University.  Approved at second reading on
September 10, 1992; however, the INDEPENDENT subgroup was directed to
examine methods of allowing reductions to be performed within
INDEPENDENT constructs.}
The INDEPENDENT directive can procede a DO loop or FORALL statement or
construct.
Intuitively, it asserts to the compiler that the operations in the
following construct
may be executed independently--that is, in any order, or
interleaved, or concurrently--without changing the semantics
of the program.

The syntax of the INDEPENDENT directive is
                                                  \BNF
independent-dir	\IS	!HPF$INDEPENDENT [ (integer-variable-list) ]
                                                  \FNB

\noindent
Constraint: An {\it independent-dir\/} must immediately precede a DO or FORALL
statement.

\noindent
Constraint: If the {\it integer-variable-list\/} is present, then the
variables named must be the index variables of set of perfectly nested
DO loops or indices from the same FORALL header.

The directive is said to apply to the indices named in its {\it
integer-variable-list}, or equivalently to the loops or FORALL indexed
by those variables.
If no {\it integer-variable-list\/} is present, then it is as if it
were present and contained the index variable for the DO or FORALL
imediately following the directive.

When applied to a nest of DO loops, an INDEPENDENT directive is an
assertion by the programmer that no iteration may affect any other
iteration, either directly or indirectly.
This implies that there are no no exits from the construct other than
normal loop termination, and no I/O is performed by the loop.
A sufficient condition for ensuring this is that
during
the execution of the loop(s), no iteration assigns to any scalar
data object which is 
accessed (i.e.\ read or written) by any other iteration.
The directive is purely advisory and a compiler is free
to ignore them if it cannot make use of the information.

For example:
                                                  \CODE
!HPF$INDEPENDENT
      DO I=1,100
        A(P(I)) = B(I)
      END DO
                                                  \EDOC
asserts that the array P does not have any repeated entries (else they
would cause interference when A was assigned).
It also limits how A and B may be storage associated.
(The remaining examples in this
section assume that no variables are storage or sequence associated.)

Another example:
                                                  \CODE
!HPF$INDEPENDENT (I1,I2,I3)
      DO I1 = 1,N1
        DO I2 = 1,N2
          DO I3 = 1,N3
            DO I4 = 1,N4   !The inner loop is not independent!
              A(I1,I2,I3) = A(I1,I2,I3) + B(I1,I2,I4)*C(I2,I3,I4)
            END DO
          END DO
        END DO
      END DO
                                                  \EDOC
The inner loop is not independent because each element of A is
assigned repeatedly.
However, the three outer loops are independent because they access
different elements of A.
It is not relevant that the outer loops read the same elements from B
and C, because those arrays are not assigned.

The interpretation of INDEPENDENT for FORALL is similar to that for
DO: it asserts that no combination of the indices that INDEPENDENT
applies to may affect another combination.
This is only possible if one combination of index values assigns to a
scalar data object accessed by another
combination.
A DO and a FORALL with the same body are equivalent if they both
have the INDEPENDENT directive.
In the case of a FORALL, any of the variables may be mentioned in the
INDEPENDENT directive:
                                                                \CODE
!HPF$INDEPENDENT (I1,I3)
    FORALL(I1=1:N1,I2=1:N2,I3=1:N3) 
      A(I1,I2,I3) = A(I1,I2-1,I3)
    END FORALL
                                                                \EDOC
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.

Graphically, the INDEPENDENT directive can be visualized as
eliminating edges from a precedence graph representing the program.
Figure~\ref{fig-dep} shows the dependences that may normally be
present in a DO an a FORALL.
An arrow from a left-hand-side node (for example, ``lhsa(1)'') 
to a right-hand-side node (e.g. ``rhsb(1)'') means that the RHS
computation may use values assigned in the LHS nodel; thus the
right-hand side must be computed after the left-hand side completes
its store.
Similarly, an arrow from a RHS node to a LHS node means that the LHS
may overwrite a value needed by the RHS computation, again forcing an
ordering.
Edges from the ``BEGIN'' and to the ``END'' nodes represent control
dependences.
The INDEPENDENT directive asserts that the only dependences that a
compiler need enforce are those in Figure~\ref{fig-indep}.
That is, the programmer who uses INDEPENDENT is certifying that if the
compiler only enforces these edges, then the resulting program will be
equivalent to the one in which all the edges are present.
Note that the set of asserted dependences is identical for INDEPENDENT
DO and FORALL constructs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Here come the pictures!
%

{

%length for use in pictures
\setlength{\unitlength}{0.03in}

%nodes used in all pictures
\newsavebox{\nodes}
\savebox{\nodes}{
    \small\sf
    \begin{picture}(80,105)(10,-2.5)
    \put(50.0,100){\makebox(0,0){BEGIN}}
    \put(20.0,80.0){\makebox(0,0){rhsa(1)}}
    \put(50.0,80.0){\makebox(0,0){rhsa(2)}}
    \put(80.0,80.0){\makebox(0,0){rhsa(3)}}
    \put(20.0,60.0){\makebox(0,0){lhsa(1)}}
    \put(50.0,60.0){\makebox(0,0){lhsa(2)}}
    \put(80.0,60.0){\makebox(0,0){lhsa(3)}}
    \put(20.0,40.0){\makebox(0,0){rhsb(1)}}
    \put(50.0,40.0){\makebox(0,0){rhsb(2)}}
    \put(80.0,40.0){\makebox(0,0){rhsb(3)}}
    \put(20.0,20.0){\makebox(0,0){lhsb(1)}}
    \put(50.0,20.0){\makebox(0,0){lhsb(2)}}
    \put(80.0,20.0){\makebox(0,0){lhsb(3)}}
    \put(50.0,0){\makebox(0,0){END}}
    \put(50.0,100){\oval(25,5)}
    \put(20.0,80.0){\oval(20,5)}
    \put(50.0,80.0){\oval(20,5)}
    \put(80.0,80.0){\oval(20,5)}
    \put(20.0,60.0){\oval(20,5)}
    \put(50.0,60.0){\oval(20,5)}
    \put(80.0,60.0){\oval(20,5)}
    \put(20.0,40.0){\oval(20,5)}
    \put(50.0,40.0){\oval(20,5)}
    \put(80.0,40.0){\oval(20,5)}
    \put(20.0,20.0){\oval(20,5)}
    \put(50.0,20.0){\oval(20,5)}
    \put(80.0,20.0){\oval(20,5)}
    \put(50.0,0){\oval(25,5)}
    \put(50,97.5){\vector(-2,-1){30}}
    \put(50,97.5){\vector(0,-1){15}}
    \put(50,97.5){\vector(2,-1){30}}
    \put(20,17.5){\vector(2,-1){30}}
    \put(50,17.5){\vector(0,-1){15}}
    \put(80,17.5){\vector(-2,-1){30}}
    \end{picture}
}

\begin{figure}

\begin{minipage}{2.70in}
\CODE
FORALL ( i = 1:3 )
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END FORALL
\EDOC

\centering
\begin{picture}(80,105)(10,-2.5)
\small\sf
%save the messy part of the picture & reuse it
\newsavebox{\web}
\savebox{\web}{
    \begin{picture}(60,15)(0,0)
    \put(0,15){\vector(0,-1){15}}
    \put(0,15){\vector(2,-1){30}}
    \put(0,15){\vector(4,-1){60}}
    \put(30,15){\vector(-2,-1){30}}
    \put(30,15){\vector(0,-1){15}}
    \put(30,15){\vector(2,-1){30}}
    \put(60,15){\vector(0,-1){15}}
    \put(60,15){\vector(-2,-1){30}}
    \put(60,15){\vector(-4,-1){60}}
    \end{picture}
}
\put(10,-2.5){\usebox\nodes}
\put(20,62.5){\usebox\web}
\put(20,42.5){\usebox\web}
\put(20,22.5){\usebox\web}
\end{picture}
\end{minipage}
%
\hfill
%
\begin{minipage}{2.70in}
\CODE
DO i = 1, 3
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END DO
\EDOC

\centering
\begin{picture}(80,105)(10,-2.5)
\small\sf
%save the messy part of the picture & reuse it
\newsavebox{\chain}
\savebox{\chain}{
    \begin{picture}(20,70)(0,0)
    \put(2.5,2.5){\oval(5,5)[bl]}
    \put(2.5,0){\vector(1,0){5}}
    \put(7.5,2.5){\oval(5,5)[br]}
    \put(10,2.5){\vector(0,1){32.5}}
    \put(10,35){\line(0,1){32.5}}
    \put(12.5,67.5){\oval(5,5)[tl]}
    \put(12.5,70){\vector(1,0){5}}
    \put(17.5,67.5){\oval(5,5)[tr]}
    \end{picture}
}
\put(10,-2.5){\usebox\nodes}
\put(20,77.5){\vector(0,-1){15}}
\put(20,57.5){\vector(0,-1){15}}
\put(20,37.5){\vector(0,-1){15}}
\put(25,15){\usebox\chain}
\put(50,77.5){\vector(0,-1){15}}
\put(50,57.5){\vector(0,-1){15}}
\put(50,37.5){\vector(0,-1){15}}
\put(55,15){\usebox\chain}
\put(80,77.5){\vector(0,-1){15}}
\put(80,57.5){\vector(0,-1){15}}
\put(80,37.5){\vector(0,-1){15}}
\end{picture}
\end{minipage}

\caption{Dependences in DO and FORALL without
INDEPENDENT assertions}
\label{fig-dep}
\end{figure}

\begin{figure}

%Draw the picture once, use it twice
\newsavebox{\easy}
\savebox{\easy}{
    \small\sf
    \begin{picture}(80,105)(10,-2.5)
    \put(10,-2.5){\usebox\nodes}
    \put(20,77.5){\vector(0,-1){15}}
    \put(20,57.5){\vector(0,-1){15}}
    \put(20,37.5){\vector(0,-1){15}}
    \put(50,77.5){\vector(0,-1){15}}
    \put(50,57.5){\vector(0,-1){15}}
    \put(50,37.5){\vector(0,-1){15}}
    \put(80,77.5){\vector(0,-1){15}}
    \put(80,57.5){\vector(0,-1){15}}
    \put(80,37.5){\vector(0,-1){15}}
    \end{picture}
}

\begin{minipage}{2.70in}
\CODE
!HPF$ INDEPENDENT
FORALL ( i = 1:3 )
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END FORALL
\EDOC

\centering
\usebox\easy
\end{minipage}
%
\hfill
%
\begin{minipage}{2.70in}
\CODE
!HPF$ INDEPENDENT
DO i = 1, 3
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END DO
\EDOC

\centering
\usebox\easy
\end{minipage}

\caption{Dependences in DO and FORALL with
INDEPENDENT assertions}
\label{fig-indep}
\end{figure}

}

%
%
% End of pictures
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The compiler is justified in producing
a warning if it can prove that one of these assertions is incorrect.
It is not required to do so, however.
A program containing any false assertion of this type is not
standard-conforming, and the compiler may take any action it deems necessary.

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.

\section{Other Proposals}

The following are proposals made for modification or replacement of the 
above sections.

\subsection{A Proposal for MIMD Support in HPF}

\label{mimd-support}

\subsubsection{Abstract}

\footnote{Version of July 18, 1992 - Clemens-August Thole, GMD I1.T.
In the interest of time, these features were not considered for inclusion 
in the first round of HPFF.}
This proposal tries to supply sufficient language support in order 
to deal with loosely sysnchronous programs, some of which have been 
identified in my "A vote for explicit MIMD support".
This is a proposal for the support of MIMD parallelism, which extends
Section~\ref{do-independent}. 
It is more oriented
towards the CRAY - MPP Fortran Programming Model and the PCF proposal. 
The fine-grain synchronization of PCF is not proposed for implementation.
Instead of the CRAY-mechanims for assigning work to processors an 
extension of the ON-clause is used.
Due to the lack of fine-grain synchronization the constructs can be
executed
on SIMD or sequential architectures just by ignoring the additional
information.

\subsubsection{Summary of the current situation of MIMD support as part of
HPF}

According to the Charles Koelbel's (Rice) mail dated March 20th "Working
Group 4 -
Issues for discussion" MIMD-support is a topic for discussion within
working
group 4. 

Dave Loveman (DEC) has produced a document on FORALL statements 
(inorporated in Sections~\ref{forall-stmt} and \ref{forall-construct})
which
summarizes the discussion. Marc Snir proposed some extensions. These
constructs allow to describe SIMD extensions in an extended way compared
to array assignments. 

A topic for working papers is the interface of HPF Fortran to program units
which execute in SPMD mode. Proposals for "Local Subroutines" have been
made
by Marc Snir and Guy Steele
(Chapter~\ref{foreign}). Both proposals
define local subroutines as program units, which are executed by all
processors independent of each other. Each processor has only access
to the data contained in its local memory. Parts of distributed data
objects
can be accessed and updated by calls to a special library. Any
message-passing
library might be used for synchronization and communication.
This approach does not really integrate MIMD-support into HPF programming.

The MPP Fortran proposal by Douglas M. Pase, Tom MacDonald, Andrew Meltzer
(CRAY)
contained the following features in order to support integrated MIMD
features:
\begin{itemize}
   \item  parallel directive
   \item  shared loops 
   \item  private variables
   \item  barrier synchronization
   \item  no-barrier directive for removing synchronization
   \item  locks, events, critical sections and atomic update
   \item  functions, to examine the mapping of data objects.
\end{itemize}

Steele's "Proposal for loops in HPF" (02.04.92) included a proposal for a 
directive "!HPF$ INDEPENDENT( integer_variable_list)", which specifies
for the next set of nested loops, that the loops with the specified
loop variables can be executed independent from each other.
(Sectin~\ref{do-independent} is a short version of this proposal.) 

Charles Koelbel gave an overview on different styles for parallel loops
in "Parallel Loops Position Paper". No specific proposal was made.

Min-You Wu "Proposal for FORALL, May 1992" extended Guy Steele's 
"!HPF$ INDEPENDENT" proposal to use the directive in a block style.

Clemens-August Thole "A vote for explicit MIMD support" contains 3 examples
from different application areas, which seem to require MIMD support for
efficient execution. 

\paragraph{Summary}

In contrast to FORALL extensions MIMD support is currently not
well-established
as part of HPF Fortran. The examples in "A vote for explicit MIMD support"
show clearly the need for such features. Local subroutines do not fulfill
the requirements because they force to use a distributed memory programming
model,
which should not be necessary in most cases.

With the exception of parallel sections all interesting features
are contained in the MPP-proposal. I would like to split the discussion
on specifying parallelism, synchronization and mapping into three different
topics. Furthermore I would like to see corresponding features to be
expessed
in the style of of the current X3H5 proposal, if possible, in order to
be in line with upcoming standards.

\subsubsection{Proposal for MIMD support}

In order to support the spezification of MIMD-type of parallelism the
following
features are taken from the "Fortran 77 Binding of X3H5 Model for 
Parallel Programming Constructs": 
\begin{itemize}
    \item   PARALLEL DO construct/directive
    \item   PARALLEL SECTIONS worksharing construct/directive
    \item   NEW statement/directive
\end{itemize}

These constructs are not used with PCF like options for mapping or 
sysnchronisation but are combined with the ON clause for mapping operations
onto the parallel architecture. 

\paragraph{PARALLEL DO}

\subparagraph{Explicit Syntax}

The PARALLEL DO construct specifies parallelism among the 
iterations of a block of code. The PARALLEL DO construct has the same
syntax as a DO statement. For a directive approach the directive
!HPF$ PARALLEL can be used in front of a do statement.
After the PARALLEL DO statement a new-declaration may be inserted.

A PARALLEL DO construct might be nested with other parallel constructs. 

\subparagraph{Interpretation}

The PARALLEL DO is used to specify parallel execution of the iterations of
a block of code. Each iteration of a PARALLEL DO is an independent unit
of work. The iterations of PARALLEL DO must be data independent. Iterations
are data independent if the storage sequence accociated with each variable
are array element that is assigned a value by each iteration is not
referenced
by any other iteration. 

A program is not HPF conforming, if for any iteration a statement is
executed,
which causes a transfer of control out of the block defined by the PARALLEL
DO construct. 

The value of the loop index of a PARALLEL DO is undefined outside the scope
of the PARALLEL DO construct. 

\paragraph{PARALLEL SECTIONS}

The parallel sections construct is used to specify parallelism among
sections
of code.

\subparagraph{Explicit Syntax}

                                                              \CODE
        !HPF$ PARALLEL SECTIONS
        !HPF$ SECTION
        !HPF$ END PARALLEL SECTIONS
                                                              \EDOC
structured as
                                                              \CODE
        !HPF$ PARALLEL SECTIONS
        [new-declaration-stmt-list]
        [section-block]
        [section-block-list]
        !HPF$ END PARALLEL SECTIONS
                                                              \EDOC
where [section-block] is
                                                              \CODE
        !HPF$ SECTION
        [execution-part]
                                                              \EDOC

\subparagraph{Interpretation}

The parallel sections construct is used to specify parallelism among
sections
of code. Each section of the code is an independent unit of work. A program
is not standard conforming if during the execution of any parallel sections
construct a transfer of control out of the blocks defined by the Parallel
Sections construct is performed. 
In a standard conforming program the sections of code shall be data 
independent. Sections are data independent if the storage sequence
accociated 
with each variable are array element that is assigned a value by each
section
is not referenced by any other section. 

\paragraph{Data scoping}

Data objects, which are local to a subroutine, are different between 
distinct units of work, even if the execute the same subroutine.

\paragraph{NEW statement/directive}

The NEW statement/directive allows the user to generate new instances of 
objects with the same name as an object, which can currently be referenced.

\subparagraph{Explicit Syntax}

A [new-declaration-stmt] is
                                                                \CODE
       !HPF$ NEW variable-name-list
                                                                \EDOC

\subparagraph{Coding rules}

A [varable-name] shall not be
\begin{itemize} 
\item    the name of an assumed size array, dummy argument, common block, 
function or entry point
\item    of type character with an assumed length
\item    specified in a SAVE of DATA statement
\item    associated with any object that is shared for this parallel
construct.
\end{itemize}

\subparagraph{Interpretation}
 
Listing a variable on a NEW statement causes the object to be explicitly
private for the parallel construct. For each unit of work of the parallel 
construct a new instance of the object is created and referenced with the
specific name. 

\subsection{Nested WHERE statements}

\label{nested-where}

\footnote{Version of September 15, 1992 - Guy Steele, Thinking Machines 
Corporation.  This section has not been discussed.}
Here is the text of a proposal once sent to X3J3:
\begin{quote}
Briefly put, the less WHERE is like IF, the more difficult it is to
translate existing serial codes into array notation.  Such codes tend to
have the general structure of one or more DO loops iterating over array
indices and surrounding a body of code to be applied to array elements.
Conversion to array notation frequently involves simply deleting the DO
loops and changing array element references to array sections or whole
array references.  If the loop body contains logical IF statements, these
are easily converted to WHERE statements.  The same is true for translating
IF-THEN constructs to WHERE constructs, except in two cases.  If the IF
constructs are nested (or contain IF statements), or if ELSE IF is used,
then conversion suddenly becomes disproportionately complex, requiring the
user to create temporary variables or duplicate mask expressions and to use
explicit .AND. operators to simulate the effects of nesting.

Users also find it confusing that ELSEWHERE is syntactically and
semantically analogous to ELSE rather than to ELSE IF.

We propose that the syntax of WHERE constructs be extended and
changed to have the form
                                                                \BNF
where-construct       \IS  where-construct-stmt
 				    [ where-body-construct ]...
 				  [ elsewhere-stmt
 				    [ where-body-construct ]... ]...
 				  [ where-else-stmt
 				    [ where-body-construct ]... ]
 				  end-where-stmt
 
 	where-construct-stmt  \IS  WHERE ( mask-expr )
 
 	elsewhere-stmt        \IS  ELSE WHERE ( mask-expr )
 
 	where-else-stmt       \IS  ELSE WHERE
 
 	end-where-stmt        \IS  END WHERE
 
 	mask-expr             \IS  logical-expr
 
 	where-body-construct  \IS  assignment-stmt
 			      \IS  where-stmt
 			      \IS  where-construct
                                                                \FNB                                                     	

\noindent Constraint: In each assignment-stmt, the mask-expr and the variable
being defined must be arrays of the same shape.  If a
where-construct contains a where-stmt, an elsewhere-stmt,
or another where-construct, then the two mask-expr's must
be arrays of the same shape.
 
The meaning of such statements may be understood by rewrite rules.  First
one may eliminate all occurrences of ELSE WHERE:
                                                                \CODE
WHERE (m1)		
    xxx			
ELSE WHERE (m2)		
    yyy				
END WHERE
	                                                            \EDOC
becomes
                                                                \CODE
WHERE (m1)
    xxx
ELSE
    WHERE (m2)
        yyy
    END WHERE
END WHERE
                                                                \EDOC
where xxx and yyy represent any sequences of statements, so long as the
original WHERE, ELSE WHERE, and END WHERE match, and the ELSE WHERE is the
first ELSE WHERE of the construct (that is, yyy may include additional ELSE
WHERE or ELSE statements of the construct).  Next one eliminates ELSE:
                                                                \CODE
WHERE (m)
    xxx
ELSE
    yyy
END WHERE				WHERE (.NOT. temp)
                                                                \EDOC
becomes
                                                                \CODE
temp = m
WHERE (temp)
    xxx
END WHERE
WHERE (.NOT. temp)
    yyy
END WHERE
                                                                \EDOC

Finally one eliminates nested WHERE constructs:
                                                                \CODE
WHERE (m1)
    xxx
    WHERE (m2)
        yyy
    END WHERE
    zzz
END WHERE
                                                                \EDOC
becomes
                                                                \CODE
temp = m1
WHERE (temp)
    xxx
END WHERE
WHERE (temp .AND. (m2))
    yyy
END WHERE
WHERE (temp)
    zzz
END WHERE
                                                                \EDOC
and similarly for nested WHERE statements.

The effects of these rules will surely be a familiar or obvious possibility
to all the members of the committee; I enumerate them explicitly here only
so that there can be no doubt as to the meaning I intend to support.

Such rewriting rules are simple for a compiler to apply, or the code may
easily be compiled even more directly.  But such transformations are
tedious for our users to make by hand and result in code that is
unnecessarily clumsy and difficult to maintain.

One might propose to make WHERE and IF even more similar by making two
other changes.  First, require the noise word THERE to appear in a WHERE
and ELSE WHERE statement after the parenthesized mask-expr, in exactly the
same way that the noise word THEN must appear in IF and ELSE IF statements.
(Read aloud, the results might sound a trifle old-fashioned--"Where knights
dare not go, there be dragons!"--but technically would be as grammatically
correct English as the results of reading an IF construct aloud.)  Second,
allow a WHERE construct to be named, and allow the name to appear in ELSE
WHERE, ELSE, and END WHERE statements.  I do not feel very strongly one way
or the other about these no doubt obvious points, but offer them for your
consideration lest the possibilities be overlooked.
\end{quote}

Now, for compatibility with Fortran 90, HPF should continue to
use ELSEWHERE instead of ELSE, but this causes no ambiguity:

      WHERE(...)
	...
      ELSE WHERE(...)
	...
      ELSEWHERE
	...
      END WHERE

is perfectly unambiguous, even when blanks are not significant.
Since X3J3 declined to adopt the keyword THERE, it should not be
used in HPF either (alas).

\alternative A
\subsection{
A Proposal for EXECUTE-ON Directive in HPF
}

\label{on-clause}

\footnote{Version of 
September 14, 1992
--
Tin-Fook Ngai,
Hewlett-Packard Laboratories.
This section has not been disussed.}
The proposed EXECUTE-ON directive is used to suggest where an iteration of
a DO construct or an indexed parallel assignment should be executed.  The
directive informs the compiler which data access should be local and
which data access may be remote.  

\subsubsection{Syntax}
                                                                \BNF
on-clause \IS !HPF$ EXECUTE (subscript-list) ON align-spec 
                [; LOCAL array-name-list]
                                                                \FNB

\noindent Constraint:
Each point in the index space must be executed on only one template node.

\subsubsection{Usage}

The EXECUTE-ON directive must immediately precede the corresponding DO
loop body, array assignment, FORALL statement, FORALL construct or
individual assignment statement in a FORALL construct.

\subsubsection{Interpretation}

The subscript-list identifies a distinct iteration index or an indexed
parallel assignment.  The align-spec identifies a template node.  The
EXECUTE-ON directive suggests that the iteration or parallel assignment
should be executed on the processor to where the template node is
mapped.  The optional LOCAL directive informs the compiler that all
data accesses to the specified array-name-list can be handled as local
data accesses if the related HPF data mapping directives are honored.

\subsubsection{Examples}

\paragraph{Example 1}
                                                                \CODE
      REAL A(N), B(N)
!HPF$ TEMPLATE T(N)
!HPF$ ALIGN WITH T:: A, B
!HPF$ DISTRIBUTE T(CYCLIC(2))

      !HPF$ INDEPENDENT            
      DO I = 1, N/2 
      !HPF$ EXECUTE (I) ON T(2*I); LOCAL A, B, C
      ! we know that P(2*I-1) and P(2*I) is a permutation
      ! of 2*I-1 and 2*I
        A(P(2*I - 1)) = B(2*I - 1) + C(2*I - 1)    
        A(P(2*I)) = B(2*I) + C(2*I)
      END DO
                                                                \EDOC

\paragraph{Example 2}
                                                                \CODE
      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B

      !HPF$ EXECUTE (I,J) ON T(I+1,J-1)
      FORALL (I=1:N-1, J=2:N)   A(I,J) = A(I+1,J-1) + B(I+1,J-1)
                                                                \EDOC

\paragraph{Example 3}
                                                                \CODE
      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B

      !HPF$ EXECUTE (I,J) ON T(I,J)       
      ! applies to the entire FORALL construct
      FORALL (I=1:N-1, J=2:N) 
          A(I,J) = A(I+1,J-1) + B(I+1,J-1)
          B(I,J) = A(I,J) + B(I+1,J-1)
      END FORALL
                                                                \EDOC

\paragraph{Example 4}
                                                                \CODE
      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B

      FORALL (I=1:N-1, J=2:N) 
      !HPF$ EXECUTE (I,J) ON T(I,J)
      ! applies only to the following assignment
          A(I,J) = A(I+1,J-1) + B(I+1,J-1)
          B(I,J) = A(I,J) + B(I+1,J-1)
      END FORALL
                                                                \EDOC

\paragraph{Example 5}
                                                                \CODE
      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B

      !HPF$ EXECUTE (I,J) ON T(I+1,J-1)
      A(1:N-1,2:N) = A(2:N,1:N-1) + B(2:N,1:N-1)
                                                                \EDOC
   
\paragraph{Example 6} 

The original program for this example is due to Michael Wolfe of Oregon 
Graduate Institute.

This program performs matrix multiplication \(C = A \times B\)
In each step, array B is rotated by row-blocks, multiplied
diagonal-block-wise in parallel with A, results are accumulated in C 

Note that without the EXECUTE-ON and LOCAL directive, the compiler
will have a hard time to figure out all A, B and C accesses are 
actual local, thus unable to generate the best efficient code 
(i.e. communication-free and no runtime checking in the parallel 
loop body).
 
                                                                \CODE
      REAL A(N,N), B(N,N), C(N,N)
!HPF$ REALIGNABLE B

!* A,B,C are distributed by row blocks
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN (:,:) WITH T:: A, B, C      
!HPF$ DISTRIBUTE T(BLOCK,*)

      NOP = NUMBER_OF_PROCESSORS()
      IB = N/NOP

      DO IT = 0, NOP-1

!* assuming warp around realignment
!HPF$ REALIGN B(I,J) WITH T(I-IT*IB,J)  

        !HPF$ INDEPENDENT
        DO IP = 0, NOP-1     
          !HPF$ EXECUTE (IP) ON T(IP*IB+1,1); LOCAL A, B, C
          ITP = MOD( IT+IP, NOP )

          DO I = 1, IB
            DO J = 1, N
              DO K = 1, IB
                C(IP*IB+I,J) = C(IP*IB+I,J) +             &
                  A(IP*IB+I,ITP*IB+K)*B(ITP*IB+K,J)
              ENDDO  !* K
            ENDDO  !* J
          ENDDO  !* I
        ENDDO  !* IP

      ENDDO  !* IT
                                                                \EDOC

\subsubsection{Commentary}

The following is a discussion between Henk Sips and Tin-Fook Ngai from 
the mailing list.  It is included to clarify some issues in the preceeding.

\begin{enumerate}
\item Sips: The execution model of HPFF (not completely approved yet) states: 
\begin{quote}
The code compiled by an HPF compiler ought do no worse than code
compiled using the owner compute rule.
\end{quote}
This is more relaxed than saying "it uses the owner compute rule". Your
EXECUTE ON is much more specific towards fixing execution on a specified
processor. 

Ngai: What are you objecting to? The EXECUTE ON is a directive.

\item Sips: A template is not executed, so one can't say EXECUTE x ON T. 
Something like 
EXECUTE\_ON\_HOME T should be adopted (Since templates are currently no
objects one could even deny this)

Ngai: Agree.  I never feel comfortable with the key words I used.  I don't have
objection to ``EXECUTE x ON\_HOME T''.  Any other suggestions are also
welcome.

\item Sips: Adopting EXECUTE x ON on DO loops without any indepence requirements, as
your proposal seems to allow, can yield all kind of intricate
synchronization schemes, when iterations are not independent (or must be
assumed to be dependent). This seems to go further than the first simple
step, which HPFF ought to be.

Ngai: Clearly, the proposed feature is primarily intended for INDEPENDENT DO,
FORALL and other parallel indexed assignments.  Before making the
proposal, I have also thought about ordinary DO loops as you pointed out
here. Code generation seems not a problem: If the user choose to specify
execution location of an iteration of an ordinary DO loops, simple
compilation requires only one synchronication at the end of each iteration
to ensure the DO sequential semantics. This naive compilation looks dumb
but the user may still gain due to the already data distribution.  (A
smarter compiler of course can do a better job but definitely is not
required.)  That is why I don't restrict EXECUTE ON to INDEPENDENT DOs and
make the rule simpler.

\item Sips: Binding iterations to templates can currently only be done statically,
since 
the current draft does not allow dynamic templates. So iterations
boundaries must be known at compile time. One has to apply the subroutine
trick to allow this, which is not very neat.

Ngai: That is the intention of the proposal:  Only static binding is allowed.
Even the loop index is bounded by runtime variable, the binding to
template node is still static.

\item Sips: Allowing EXECUTE x ON on groups of statements, gives a scoping issue, so
there should also be something like END EXECUTE x ON, do undo the
annotation. 

Ngai: The current proposal seems sufficient in this issue.  The scope for single
statement (FORALL statement, single statement in FORALL construct, and array
assignment statement) is clear.  For groups of statements, EXECUTE ON can
only applies to either the entire body within a FORALL construct or the
entire iteration of a DO loop.

\item Sips: Again we have complicated scoping problems. How about this example:
                                                                \CODE
!HPF$ TEMPLATE T1(N), T2(N)

DO I=1,N
    !HPF$ EXECUTE (I) ON T1(I)
    C(I) = D(I)
    DO J=1,N
      !HPF$ EXECUTE (J) ON T2(J)
      A(I,J) =  A(I,J) + B(I,J) 
    ENDDO
ENDDO
                                                                \EDOC
This example satisfies the constraint only if by entering the J-loop, the
I-index is dereferenced from the assertion just after the I-loop. Although
logical, it might be confusing to users. However, in the program
                                                                \CODE
!HPF$ TEMPLATE T1(N), T2(N)
DO I=1,N
    !HPF$ EXECUTE (I) ON T1(I)
    C(I) = D(I)
    DO J=1,N
        A(I,J) =  A(I,J) + B(I,J) 
    ENDDO
ENDDO
                                                                \EDOC
there is no such dereferencing. 

Ngai: Good examples.  This bug surely needs to be fixed.  Here is my solution:
\begin{itemize}
\item For nested EXECUTE ON directives, only the immediate enclosed EXECUTE ON
  directive is effective.
\end{itemize}
In the former example, the statement ``C(I) = D(I)" will be executed on the
home of T1(I) while the statement ``A(I,J) =  A(I,J) + B(I,J)" will be
executed on home of T2(J) for all I.  In the latter case, the entire
I-loop body that includes the DO J loop is executed on the home of T1(I).

\item Sips: The wrap feature of templates will probably be deleted from the draft.
The same thing (shifting data each iteration) can reached by using CSHIFT
or the subroutine trick and making the template as large as the ieteration
space.

Ngai: I and Wolfe discussed the example (Example 6 in the proposal) long before
our revision on the wrap feature.  Sorry for any confusion from this
example.  (However, this example also illustrates the use of wrap in data
distribution -- we should come up with a cleaner solution next meeting.)

\item Sips: We cannot do separate compilation in some examples:
                                                                \CODE
!HPF$ TEMPLATE T1(N)
  DO I=1,N
    !HPF$ EXECUTE (I) ON T1(I)
    C(I) = D(I)
    DO J=1,N
      A(I,J) = B(I,J)
    ENDDO
  ENDDO
                                                                \EDOC
Here A(I,J) is calculated in T(I). If we encapsulate the J-loop into a
subroutine we get something like:
                                                                \CODE
!HPF$ TEMPLATE T1(N)
  DO I=1,N
    !HPF$ EXECUTE (I) ON T1(I)
    C(I) = D(I)
    CALL FOO(A(I,:),B(I,:))
  ENDDO

...

SUBROUTINE FOO(AA,BB)
!HPF$ ALIGN AA,BB with *
    DO J=1,N
      AA(J) = BB(J)
    ENDDO
                                                                \EDOC
The dummy arguments AA and BB are aligned to the incoming array sections.
Normally, without any EXECUTE\_ON, the subroutine would execute AA(J), which
is equivalent to A(I,J), on home A(I,J). However, with an EXECUTE\_ON in the
main program there is no way the subroutine can know that AA(J) should be
executed on T(I). The consequence is that any subroutine call is to *undo*
the EXECUTE\_ON on entry and {\em redo} the EXECUTE_ON on return.

(Ngai did not respond publically.)
\end{enumerate}

\alternative B
\subsection{Proposal for a Statement Grouping Syntax and ON Clause}

\footnote{Version of October 5, 1992 -- Clemens-August Thole, GMD-I1.T,
Sankt Augustin.
This section has not been discussed.}
I agree with Tin-Fook, that something like the on-clause should be 
contained in HPF. I brought a proposal with me to the last HPF meeting 
which was distributed by Chuck, but neither the FORALL working group
nor the plenary had time to discuss the proposal.

I would appreciate comments on the various features.

\subsubsection{Introduction}

This proposal introduces an extension to HPF to group several 
statements in order to be able to specify properties for a whole block
of statement at once. A block of statements is called HPF-section.
HPF-sections can be used to describe properties for independent execution
between blocks of statements aswell as the mapping of their execution.

For the specification of a specific mapping of the execution of statements
or HPF-sections the ON-clause is introduced. A subset of a template is used
as reference object onto which the statements are mapped in an canonical
manner. The careful selection of the reference template allows to specify,
how the execution of the code is mapped onto the parallel architecture.

\subsubsection{HPF-sections}

The HPF directives SECTIONS, SECTION, and END SECTIONS are used to specify
grouping of statements. SECTIONS and END SECTIONS specify the beginning
and end of a list of HPF-sections and SECTION the beginning of the next 
HPF-section. The syntax is as follows:
                                                                \BNF
hpf-block \IS        !HPF$ SECTION
                [HPF-section-list]
        !HPF$ END SECTIONS

hpf-section \IS        !HPF$ SECTION
                [execution-part]
                                                                \FNB
\noindent Constraint: For any {\em hpf-section} under no circumstances a 
transfer of control
is performed during the execution of the code outside of its 
{\em execution-part}.

\paragraph{Example}
                                                                \CODE
        !HPF$ SECTIONS
        !HPF$ SECTION
                A = A + B
                B = C + D
        !HPF$ SECTION
                E = B
                IF (E.GT.F) GOTO 10
                        E = 0D0
         10     CONTINUE
        !HPF$ END SECTIONS
                                                                \EDOC
This example specifies a list of two HPF-sections. The control statement in
the second HPF-section is valid because after the transfer of control the
execution continues in the same HPF-section.

\subsubsection{ON-clause}

The ON-clause specifies a subsection of a template, which is used as a reference
object for the execution of the next statement, construct, of HPF-section.
If the left-hand-side of an assignment coinsides in shape with the reference
object, the evaluation of the right-hand-side and the assignment for 
a specific element of the left-hand-side is performed at that processor, onto
which the corresponding element of the reference object is mapped.

\paragraph{Syntax}

Add the following rules:
                                                                \BNF
executable-construct \IS        !HPF$ ON on-spec
                executable-construct

hpf-section \IS        !HPF$ ON on-spec
                hpf-section
        
on-spec \IS        align-spec
                                                                \FNB
The {\it executable-construct} of {\it hpf-section} is called on-clause-target.

\paragraph{Constraints}
\begin{enumerate}
\item No {\it executable-construct} may be used as object of the on-clause, which
   generates any transfer of control out of the construct itself. This
   includes the entry-statement. 
\item {\it Statement-block}s used in constructs must fulfill the constraints of
   HPF-sections.
\item The shape of the {\it on-spec} must cover in each dimension the shape of
   of any left-hand-side of an assignment statement, which is target of an
   on-clause. If a "*" is used in the {\it on-spec}, this dimension is skipped
   for constructing the shape of the {\it on-spec}.
\item If an on-clause is contained in the on-clause-target, the new {\it on-spec}
   must be a subsection of the {\it on-spec} of the outer on-clause.
\end{enumerate}

\paragraph{Example}
                                                                \CODE
                REAL, DIMENSION(n) :: a, b, c, d
        !HPF$   TEMPLATE grid(n)
        !HPF$   ALIGN WITH grid :: a, b, c, d

        !HPF$   ON grid(2:n)
                a(1:n-1) = a(2:n) + b(2:n) + c(2:n)
                                                                \EDOC
The on-clause indicates, that the evaluation of the right-hand-side is 
performed on that processors, which hold the data elements of the 
right-hand-side. For the assignment to the left-hand-side data movement is
necessary.

\paragraph{Interpretation}

The interpretation of the on-clause depends on the type of the on-clause-target.

If the on-clause-target is an assignment statement the {\it on-spec} is used to
determine where the assignment statement is executed. If the shape of the 
right-hand-side is identically to the shape of {\it on-spec}, the computation for
a specific element of the assignment statement is performed where the 
corresponding element of the {\it on-spec} is mapped to. If the shape of the 
{\it on-spec} is larger, the compiler may use any sufficient larger subsection.
The use of "*" in the {\it on-spec} specifies, that the same computations are
mapped onto the corresponding line of processors and several processors
will do the same update. This may save communication operations.
The the case of the where-statement, the forall-statement, and the 
forall-construct the same mapping is applied to the evaluation of the 
conditions and each assignment.

If the on-clause is placed in front of the if-construct, that case-construct,
or the do-construct, the {\it on-spec} is used for the evaluations of the 
conditions as well as the loop bounds and the execution of the statement-blocks,
which are part of the construct. For the statement-blocks the interpretation 
rules for HPF-sections apply.

With respect to the allocate, deallocate, nullify, and I/O related statements
the {\it on-spec} is used for the evaluation of the parameters of the statements
and the evaluation of I/O objects. 

In the case of subroutine calls and functions the {\it on-spec} is used for the
evaluation of the parameters. It determines also the mapping of the resulting 
object. The {\it on-spec} determines also the set of processors, which will be
used for the evaluation of the subroutine. 

In the case of HPF-sections the on-clause is applied to each statement of the
execution part. Control transfer statements are allowed in this case and the 
constraints ensure, that the context on the same {\it on-spec} is not lost.

\paragraph{Additional example}
                                                                \CODE
        REAL, DIMENSION(n,n) :: a, b, c, d
!HPF$   TEMPLATE grid(n,n)
!HPF$   ALIGN WITH grid :: a, b, c, d

!HPF$   ON grid(2:n,2:n)
        DO i=2,n
!HPF$       ON grid(i,2:n)
            DO j=2,n
!HPF$           ON grid(i,j)
                a(i-1,j-1) = a(i,j) + b(i,j)*c(i,j)
            ENDDO
        ENDDO
                                                                \EDOC

\paragraph{Comment}

The compiler should be able to adjust the span of the loops to the local 
extent 
due to the restrictions on the specifiers of the sections of the {\it 
on-spec}.

\subsection{ALLOCATE in FORALL}

\label{forall-allocate}

\footnote{Version of July 28, 1992 
- Guy Steele, Thinking Machines Corporation.
At the September 10-11 meeting, this was not included as part of the
FORALL because it seemed too big a leap from the allowed assignment
statements.}
Proposal:  ALLOCATE, DEALLOCATE, and NULLIFY statements may appear
	in the body of a FORALL.

Rationale: these are just another kind of assignment.  They may have
	a kind of side effect (storage management), but it is a
	benign side effect (even milder than random number generation).

Example:
                                                            \CODE
      TYPE SCREEN
        INTEGER, POINTER :: P(:,:)
      END TYPE SCREEN
      TYPE(SCREEN) :: S(N)
      INTEGER IERR(N)
      ...
!  Lots of arrays with different aspect ratios
      FORALL (J=1:N)  ALLOCATE(S(J)%P(J,N/J),STAT=IERR(J))
      IF(ANY(IERR)) GO TO 99999
                                                            \EDOC

\subsection{Generalized Data References}

\label{data-ref}

\footnote{Version of July 28, 1992 
- Guy Steele, Thinking Machines Corporation.
This was not acted on at the September 10-11 meeting because the
FORALL subgroup wanted to minimize changes to the Fortran~90 standard.}
Proposal:  Delete the constraint in section 6.1.2 of the Fortran 90
	standard (page 63, lines 7 and 8):
\begin{quote}
	Constraint: In a data-ref, there must not be more than one
		part-ref with nonzero rank.  A part-name to the right
		of a part-ref with nonzero rank must not have the
		POINTER attribute.
\end{quote}

Rationale: further opportunities for parallelism.

Example:
                                                                     \CODE
TYPE(MONARCH) :: C(N), W(N)
      ...
! Munch that butterfly
C = C + W * A%P		! Illegal in Fortran 90
                                                                      \EDOC

\subsection{FORALL with INDEPENDENT Directives}
\label{begin-independent}

\footnote{Version of July 21, 1992) - Min-You Wu.
This was rejected at the FORALL subgroup meeting on September 9, 1992,
because it only offered syntactic sugar for capabilities already in
the FORALL INDEPENDENT.  It was also suggested that the BEGIN
INDEPENDENT syntax
should be reserved for other uses, such as MIMD features.}
This proposal is an extension of Guy Steele's INDEPENDENT proposal.
We propose a block FORALL with the directives for independent 
execution of statements.  The INDEPENDENT directives are used
in a block style.  

The block FORALL is in the form of
                                                         \CODE
      FORALL (...) [ON (...)]
        a block of statements
      END FORALL
                                                         \EDOC
where the block can consists of a restricted class of statements 
and the following INDEPENDENT directives:
                                                         \CODE
!HPF$BEGIN INDEPENDENT
!HPF$END INDEPENDENT
                                                         \EDOC
The two directives must be used in pair.  
A sub-block of statements 
parenthesized in the two directives is called an {\em asynchronous} 
sub-block or {\em independent} sub-block.  
The statements that are 
not in an asynchronous sub-block are in {\em synchronized} sub-blocks
or {\em non-independent} sub-block.  
The synchronized sub-block is 
the same as Guy Steele's synchronized FORALL statement, and the 
asynchronous sub-block is the same as the FORALL with the INDEPENDENT 
directive.  
Thus, the block FORALL
                                                          \CODE
      FORALL (e)
        b1
!HPF$BEGIN INDEPENDENT
        b2
!HPF$END INDEPENDENT
        b3
      END FORALL
                                                           \EDOC
means roughly the same as
                                                           \CODE
      FORALL (e)
        b1
      END FORALL
!HPF$INDEPENDENT
      FORALL (e)
        b2
      END FORALL
      FORALL (e)
        b3
      END FORALL
                                                          \EDOC
														  
Statements in a synchronized sub-block are tightly synchronized.
Statements in an asynchronous sub-block are completely independent.
The INDEPENDENT directives indicates to the compiler there is no 
dependence and consequently, synchronizations are not necessary.
It is users' responsibility to ensure there is no dependence
between instances in an asynchronous sub-block.
A compiler can do dependence analysis for the asynchronous sub-blocks
and issue an error message when there exists a dependence or a warning
when it finds a possible dependence.

\subsubsection{What does ``no dependence between instances" mean?}

It means that no true dependence, anti-dependence,
or output dependence between instances.
Examples of these dependences are shown below:
\begin{enumerate}
\item True dependence:
                                                            \CODE
      FORALL (i = 1:N)
        x(i) = ... 
        ...  = x(i+1)
      END FORALL
                                                            \EDOC
Notice that dependences in FORALL are different from that in a DO loop.
If the above example was a DO loop, that would be an anti-dependence.

\item Anti-dependence:
                                                            \CODE
      FORALL (i = 1:N)
        ...  = x(i+1)
        x(i) = ...
      END FORALL
                                                            \EDOC

\item Output dependence:
                                                            \CODE
      FORALL (i = 1:N)
        x(i+1) = ... 
        x(i) = ...
      END FORALL
                                                            \EDOC
\end{enumerate}

Independent does not imply no communication.  One instance may access 
data in the other instances, as long as it does not cause a dependence.  
The following example is an independent block:
                                                            \CODE
      FORALL (i = 1:N)
!HPF$BEGIN INDEPENDENT
        x(i) = a(i-1)
        y(i-1) = a(i+1)
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC

\subsubsection{Statements that can appear in FORALL}

FORALL statements, WHERE-ELSEWHERE statements, some intrinsic functions 
(and possibly elemental functions and subroutines) can appear in the
FORALL:
\begin{enumerate}
\item FORALL statement
                                                            \CODE
      FORALL (I = 1 : N)
        A(I,0) = A(I-1,0)
        FORALL (J = 1 : N)
!HPF$BEGIN INDEPENDENT
          A(I,J) = A(I,0) + B(I-1,J-1)
          C(I,J) = A(I,J)
!HPF$END INDEPENDENT
        END FORALL
      END FORALL
                                                            \EDOC

\item WHERE
                                                            \CODE
      FORALL(I = 1 : N)
!HPF$BEGIN INDEPENDENT
        WHERE(A(I,:)=B(I,:))
          A(I,:) = 0
        ELSEWHERE
          A(I,:) = B(I,:)
        END WHERE
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC
\end{enumerate}

\subsubsection{Rationale}

\begin{enumerate}
\item A FORALL with a single asynchronous sub-block as shown below is 
the same as a do independent (or doall, or doeach, or parallel do, etc.).
                                                            \CODE
      FORALL (e)
!HPF$BEGIN INDEPENDENT
        b1
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC
A FORALL without any INDEPENDENT directive is the same as a tightly 
synchronized FORALL.  We only need to define one type of parallel 
constructs including both synchronized and asynchronous blocks.  
Furthermore, combining asynchronous and synchronized FORALLs, we 
have a loosely synchronized FORALL which is more flexible for many 
loosely synchronous applications.

\item With INDEPENDENT directives, the user can indicate which block
needs not to be synchronized.  The INDEPENDENT directives can act 
as barrier synchronizations.  One may suggest a smart compiler 
that can recognize dependences and eliminate unnecessary 
synchronizations automatically.  However, it might be extremely 
difficult or impossible in some cases to identify all dependences.  
When the compiler cannot determine whether there is a dependence, 
it must assume so and use a synchronization for safety, which 
results in unnecessary synchronizations and consequently, high 
communication overhead.
\end{enumerate}

\end{document}