Compiling regular FORALL statement based on data distribution
directives 

(Draft)

Introduction

Data distribution directives, such as ALIGN, DISTRIBUTE, proposed in
High Performance Fortran [1] provided a convenient way to describe
array location on a distributed memory machine. With the help of these
directives, a DAD (Distributed Array Descriptor) [2] can be generated
for each regular reference in FORALL statement and then used to
translate this kind of FORALL statement in a global addressed program
into Fortran DO construct with collective communication in a SPMD node
program.

In this report, we introduce the major issues in translating the
FORALL statement, using the actual program compiled in our framework
of a HPF compiler as examples.

Regular FORALL reference

Given a FORALL statement:

FORALL forall-header forall-assignment-stmt
                
The forall-header is of the following BNF form:
                
forall-header is forall-triplet-sec-list [, scalar-mask-expr]
                
while the forall-assignment-stmt is: forall-assignment-stmt is
variable = expr
                
The variable in above can also be called as left-hand-side (LHS) part
of the assign statement, while the expr called right-hand-side (RHS)
part. The expr will be further composed of possible multiple
variables.
                
We call the variables appeared in forall-triplet-sec-list as forall
index. Usually, these index will be used as the subscript of the array
variables accessed in the forall assignment statement.  We call the
forall reference of the variables as a regular reference if all of the
forall index used in a linear expression of the variable address, and
there is no array indirect addressing.

DAD

Distributed array descriptor

Run-time library

PCRC interface.


Program analyzing

General speaking, the compiler can be divided into two phases: program
analyzing phase and program transforming phase. In program analyzing
phase, the following items are examined to prepare basic information
for the next phase:

processor information, including rank and size in each rank;

template information, also including rank and size in each rank;

distributing information for each template;

aligning information for each distributed array;

variable reference in each FORALL statement;

The first four items are reflected in PROCESSOR, TEMPLATE, DISTRIBUTE
and ALIGN statement separately. And their corresponding translation in
node program are straightforward, mainly for generating DAD for each
array declaration in the source program, which can be found in [3],
and later in this report as examples.

The fifth item is the focus in this section. And we only concerned
regular forall reference in this report.

Communication patterns

Given a Forall statement as in 

FORALL forall-triplet-sec-list [,
scalar-mask-expr]       variable = expr

and translating it into Fortran DO construct to be executed on a
sequential machine, the "owner computes" rule is used to assign the
computation to each node processor, which means the processor who
"own" the LHS will execute the actual calculation for that part. We
may also let the "owner" of the LHS to evaluate the optional
scalar-mask-expr. Then the forall statement can be viewed as

FORALL forall-triplet-sec-list          LHS= RHS
        
If both LHS and RHS are on the same processor, there is no
communication needed, the computation can be carried on directly.
Unfortunately, this is not always the case. When the corresponding
data in the LHS and RHS indicated by the forall index is located in
different machines, communication is necessary.

We can specify the communication patens used in the FORALL construct
according to the forall index reference in the LHS and RHS.

An regular forall reference may be a scalar or an array element, so we
may have the following possible combinations:

The LHS variable is a scalar: This does not comply the constrains of
the forall statement, multiple assignment may happen. (If all the RHS
are also scalar, it is just the same as one single assignment.)

If the LHS variable is an array element.

In this case, there are still two possibilities: it is a partitioned
array or a un-partitioned array.

If the array is not partitioned among the processors, the communication patterns needed are simple, it may be either no communication or sending a single copy to multiple processors.

For example:

FORALL (i=1:n)  A(i)=B(i)
        
If A is a non-partitioned array and B is a partitioned array, then
broadcasting is needed.

If the array is a partitioned one. Then the communication needed is
dependent on the reference pattern of the forall index. Possible
communications include:

No communication

The LHS and RHS array elements needed to do calculation are located on
the same machine.

Shift
The data movement is along one or more dimensions.

Remap 

The data movement is among different dimension of the array or
not unified in the same dimension.

Scatter

Data is duplicated to different positions.  

The simplest case of above movement can be show in figure. 1

Data movement

During the analyzing phase, the compiler will determine what kind of
communication is used in the forall statement.

So a simple algorithm for program analysis can be written as:

for each processor statement record processor rank and size 
for each template statement record template dimension and size 
for each align statement record array to be distributed. 
for each forall and procedure call statement do {
recursively analysis each array reference, 
detecting communication pattern needed
build up the transformation reference queue
}


Detecting shift or remap

decide the communication pattern 

reduce the dimension, detect communication.
