Subject: revised FORALL proposal with INDEPENDENT directives

From: [email-masked] (Min-You Wu)
Date: Sat, 25 Jul 92 12:21:25 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 25, 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 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.

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

It means that no true dependence, anti-dependence,
or output 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}

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}

FORALL statements, WHERE-ELSEWHERE statements, some intrinsic functions 
(and possibly elemental functions and subroutines) can appear in the FORALL:

\noindent
1) FORALL statement
\begin{verbatim}
      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
\end{verbatim}

\noindent
2) 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}

Moreover, I would like to propose to include IF statements and DO loops 
in FORALL:

\noindent
3) 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
4) DO loop
\begin{verbatim}
      FORALL (I = 1 : N)
!HPF$BEGIN INDEPENDENT
        DO J = 1, C(I) 
          A(I) = A(I) * B(I)
        END DO 
!HPF$END INDEPENDENT
      END FORALL
\end{verbatim}

\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}