Subject: A proposal for FORALL

From: [email-masked] (Min-You Wu)
Date: Mon, 4 May 92 07:34:56 EDT

Proposal for FORALL in HPF

Min-You Wu
SUNY at Buffalo
[email-masked]
May 1992

We propose a block forall with the directives for independent 
execution of statements.  This proposal is based on Guy Steele's 
proposal and we will use his definitions without repeating.

The block forall is in the form of

      forall (...)
        a block of statements
      end forall

where the block can consists of a restricted class of statements 
and the following INDEPENDENT directives:

!HPF$INDEPENDENT
!HPF$ENDINDEPENDENT

The two directives must be used in pair.  A sub-block of statements 
parenthesized in the two directives is called an asynchronized
sub-block.  Other statements are in synchronized sub-blocks.  
The synchronized sub-block is the same as Guy Steele's synchronized 
forall statement, and the asynchronized sub-block is the same as the 
forall with the INDEPENDENT directives.  Thus, the block forall

      forall (e)
        b1
!HPF$INDEPENDENT
        b2
!HPF$ENDINDEPENDENT
        b3
      end forall

means exactly the same as

      forall (e)
        b1
      end forall
!HPF$INDEPENDENT
      forall (e)
        b2
      end forall
      forall (e)
        b3
      end forall

An asynchronized sub-block directly followed by another asynchronized 
sub-block means there is a synchronization between the two sub-blocks:

      forall (e)
!HPF$INDEPENDENT
        b1
!HPF$ENDINDEPENDENT
!HPF$INDEPENDENT
        b2
!HPF$ENDINDEPENDENT
      end forall

is the same as

!HPF$INDEPENDENT
      forall (e)
        b1
      end forall
!HPF$INDEPENDENT
      forall (e)
        b2
      end forall

Statements in a synchronized sub-block are tightly synchronized.
Statements in an asynchronized sub-block are completely independent.
It is users' responsibility to ensure there is no dependency 
between instances in an asynchronized sub-block.

There is no restriction on the type of statements in an asynchronized 
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.  
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.

Reduction

A reduction statement is synchronous and cannot appear in an
asynchronized sub-block unless it is the last statement in the 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:

      forall (i=1:N) 
        x = (+= a(i))
      end forall

Whenever it is possible that a memory location will be multiply 
assigned, the problem can be resolved by using a reduction operator, 
or its value will be arbitrary.  Here is an example:

      forall (i=1:N)
        b(i/c) = (+= a(i))
      end forall

We list some possible reduction operators as follows:

+=      Sum of values  
*=      Product of values 
&=      Logical AND 
|=      Logical OR 
^=      Logical XOR
<?=     Minimum of values 
>?=     Maximum of values 

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

      forall (i=1:N) 
        b(i) = (+= a(1:i)) 
      end forall

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:

      forall (i=1:N) 
!HPF$INDEPENDENT
        a(i) = i
!HPF$ENDINDEPENDENT
      end forall
      b = SUM(a)
      forall (i=1:N) 
!HPF$INDEPENDENT
        c(i) = a(i) + b
!HPF$ENDINDEPENDENT
      end forall

(2) With reduction operator:

      forall (i=1:N) 
!HPF$INDEPENDENT
        a(i) = i
        b = (+= a(i)) 
!HPF$ENDINDEPENDENT
!HPF$INDEPENDENT
        c(i) = a(i) + b
!HPF$ENDINDEPENDENT
      end forall

Notes:

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

      forall (i=1:N) 
        x = SUM(a(i))
      end forall

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

Rationale:

1. A forall with a single asynchronized sub-block is the same as a 
doindependent (or doall, or doeach, etc.), as shown below:

      forall (e)
!HPF$INDEPENDENT
        b1
!HPF$ENDINDEPENDENT
      end forall

A forall without any INDEPENDENT directive is the same as a tightly 
synchronized forall.  In this way, we need to define only one type 
of parallel constructs.  Furthermore, combining asynchronized and 
synchronized foralls, we have a loosely synchronized forall which
is more flexible.

2. With INDEPENDENT directives, the user can indicate which block
needs not to be synchronized.  One may suggest a smart compiler 
that can recognize the dependency and eliminate unnecessary 
synchronizations automatically.  However, it might be extremely 
difficult or impossible in some cases to identify all dependencies.  
When the compiler cannot determine whether there is a dependency, 
it must assume so and use a synchronization for safety, which 
results in unnecessary synchronizations and consequently, high 
communication overhead.