Subject: Revised proposal for FORALL with INDEPENDENT directives

From: [email-masked] (Min-You Wu)
Date: Sun, 19 Jul 92 15:34:23 EDT

\documentstyle[11pt]{article}
\textwidth 6.4in
\textheight 8in
\parskip 0.15in
\begin{document}

\topmargin 0in
\oddsidemargin 0in
\baselineskip .25in 

\begin{center}
{\Large Proposal for FORALL with INDEPENDENT Directives}

(Revised July 19, 1992)

Min-You Wu  \\
SUNY at Buffalo \\
[email-masked] \\

\end{center}

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
\begin{verbatim}
      FORALL (...) [ON (...)]
        a block of statements
      END FORALL
\end{verbatim}
where the block can consists of a restricted class of statements 
and the following INDEPENDENT directives:
\begin{verbatim}
!HPF$BEGIN INDEPENDENT
!HPF$END INDEPENDENT
\end{verbatim}
The two directives must be used in pair.  There is a synchronization 
at each of these directives.  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
\begin{verbatim}
      FORALL (e)
        b1
!HPF$BEGIN INDEPENDENT
        b2
!HPF$END INDEPENDENT
        b3
      END FORALL
\end{verbatim}
means roughly the same as
\begin{verbatim}
      FORALL (e)
        b1
      END FORALL
!HPF$INDEPENDENT
      FORALL (e)
        b2
      END FORALL
      FORALL (e)
        b3
      END FORALL
\end{verbatim}

Statements in a synchronized sub-block are tightly synchronized.
Statements in an asynchronous sub-block are completely independent.
The INDEPENDENT directives do not change the semantics of FORALL.
It only 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 issues an error message when there exists a dependence or a warning
when it finds a possible dependence.

% what is independent?
% use local data only
% access non-local data, but no dependence --- this one
% there are dependences, but can execute in any order

\noindent
{\bf What does mean "no dependence between instances"?}

It means that no true dependence, anti-dependence,
output dependence, or control dependence between instances.
Examples of these dependences are shown below:

\noindent
1) true dependence
\begin{verbatim}
      FORALL (i = 1:N)
        x(i) = ... 
        ...  = x(i+1)
      END FORALL
\end{verbatim}
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.

\noindent
2) anti-dependence:

\begin{verbatim}
      FORALL (i = 1:N)
        ...  = x(i+1)
        x(i) = ...
      END FORALL
\end{verbatim}

\noindent
3) output dependence:
\begin{verbatim}
      FORALL (i = 1:N)
        x(i+1) = ... 
        x(i) = ...
      END FORALL
\end{verbatim}

\noindent
4) control dependence:

\begin{verbatim}
      FORALL (i = 1:N)
        IF (x(i+1) .EQ. 0) THEN
          x(i) = ...
        END IF
      END FORALL
\end{verbatim}
     
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:

\begin{verbatim}
      FORALL (i = 1:N)
!HPF$BEGIN INDEPENDENT
        x(i) = a(i-1)
        y(i-1) = a(i+1)
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
{\bf Statements that can appear in FORALL}

There is no restriction on the type of statements in an asynchronous 
sub-block.  That is, FORALL statements, DO loops, WHILE loops, 
WHERE-ELSEWHERE statements, IF-THEN-ELSE statements, CASE statements, 
subroutine and function calls, etc. can appear, as long as there is
no dependence.  On the other hand, the statements that can appear in a 
synchronized sub-block are restricted.  The degree of restrictions will 
be determined later.  At least the following statements are allowed:
assignment statements, FORALL statements, DO loops, WHERE statements 
(not WHERE-ELSEWHERE), IF statements (not IF-THEN-ELSE), reduction 
statements (see below), and some intrinsic functions (and elemental 
functions and subroutines).

Some examples are given below for the asynchronous sub-blocks:

\noindent
1) FORALL statement
\begin{verbatim}
      FORALL (I = 1 : N)
        A(I,0) = A(I-1,0)
!HPF$BEGIN INDEPENDENT
        FORALL (J = 1 : N)
          A(I,J) = A(I,0) + B(I-1,J-1)
          C(I,J) = A(I,J)
        END FORALL
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
2) DO loop
\begin{verbatim}
      FORALL (I = 1 : N)
!HPF$BEGIN INDEPENDENT
        DO J = 1, N 
          A(I) = A(I) * B(I)
        END DO 
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
3) WHILE loop
\begin{verbatim}
      FORALL (I = 1 : N)
!HPF$BEGIN INDEPENDENT
        WHILE (A(I) < BIG) DO
          A(I) = A(I) * B(I)
        END DO 
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
4) IF-THEN-ELSE
\begin{verbatim}
      FORALL ( I = 1 : N )
!HPF$BEGIN INDEPENDENT
        IF ( A(I) < EPS ) THEN                
          A(I) = 0.0                          
          B(I) = 0.0                          
        ELSE
          TMP(I) = B(I)
          B(I) = A(I)                       
          A(I) = TMP(I)
        END IF
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
5) WHERE
\begin{verbatim}
      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
\end{verbatim}

\noindent
6) subroutine CALL
\begin{verbatim}
      FORALL(I = 1 : N)
!HPF$BEGIN INDEPENDENT
        A(I) = C(I)
        CALL FOO(A(I))
!HPF$END INDEPENDENT
      END FORALL

      SUBROUTINE FOO(x)
      real :: x
      x = x * 10 + x 
      RETURN
      END
\end{verbatim}

\noindent
Another example for subroutine CALL:

\begin{verbatim}
      FORALL(I = 1 : N)
        A(I) = C(I)
!HPF$BEGIN INDEPENDENT
        CALL FOO(B(I), A(I-1), A(I+1))
!HPF$END INDEPENDENT
      END FORALL

      SUBROUTINE FOO(x, y, z)
      real :: x, y, z
      x = (y + z) / 2
      RETURN
      END
\end{verbatim}

\noindent
{\bf Reduction}

A reduction statement is synchronized and cannot appear in an
asynchronous sub-block.

We propose to use special operators for the reduction operations.
As an example, the following FORALL statement provides a sum 
reduction over a(i) and assigns the result to a scalar variable,
with `+=' as a sum reduction operator:
\begin{verbatim}
      FORALL (i=1:N) 
        x = (+= a(i))
      END FORALL
\end{verbatim}

We list some possible reduction operators as follows:
\begin{verbatim}
+=      Sum of values  
*=      Product of values 
&=      Logical AND 
|=      Logical OR 
^=      Logical XOR
<?=     Minimum of values 
>?=     Maximum of values 
\end{verbatim}

Here is an example for multiple reduction:

\begin{verbatim}
      FORALL (i=1:N)
        b(i/c) = (+= a(i))
      END FORALL
\end{verbatim}

Using the reduction operators, we can also provide scan functions.

\begin{verbatim}
      FORALL (i=1:N) 
        b(i) = (+= a(1:i)) 
      END FORALL
\end{verbatim}

Using reduction operators but reduction intrinsics allows reduction 
operations in the FORALL body without exiting from the FORALL.  See 
the following example:

(1) With intrinsic function:
\begin{verbatim}
      FORALL (i=1:N) 
!HPF$BEGIN INDEPENDENT
        a(i) = i
!HPF$END INDEPENDENT
      END FORALL
      b = SUM(a)
      FORALL (i=1:N) 
!HPF$BEGIN INDEPENDENT
        c(i) = a(i) + b
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

(2) With reduction operator:
\begin{verbatim}
      FORALL (i=1:N) 
!HPF$BEGIN INDEPENDENT
        a(i) = i
!HPF$END INDEPENDENT
        b = (+= a(i)) 
!HPF$BEGIN INDEPENDENT
        c(i) = a(i) + b
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\noindent
Notes for reduction:

With the reduction defined above, only limited operators can be defined.  
We do not have `MAXLOC', `MINLOC', etc.  Another solution is 
using some reduction functions similar to intrinsic functions.  
For example:

\begin{verbatim}
      FORALL (i=1:N) 
        x = SUM(a(i))
      END FORALL

      FORALL (i=1:N) 
        x = MAXLOC(a(i))
      END FORALL
\end{verbatim}

However, users may be confused with the current intrinsic function SUM 
and MAXLOC.

\vspace{.1in}
\noindent
{\bf Rationale}

1. 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.).
\begin{verbatim}
      FORALL (e)
!HPF$BEGIN INDEPENDENT
        b1
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}
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.

2. 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{document}