new document

[Gary Sabot]

FORALL Proposal for Base Document (2/4/93)
Gary Sabot
Doc No: X3J11.1/93-008 


INTRO:

The purpose of the FORALL construct is to provide a convenient syntax for
simultaneous assignments to large groups of array elements.  In the
formulation given below, there is nothing that it can do that can't be done
by other constructs in the base document.  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.  This can be more concise
in some cases.  The price paid for this is the loss of transparency in
performance: the approximate cost of the underlying operations required by
a particular FORALL is not immediately apparent.




FORALL DEFINED:

General Form of Element Array Assignment:

forall-statement:
   forall( iterator {,iterator}* ) statement

iterator: 
   forall-declarator = integer-expression

The effect is that a new shape is created based on the bounds of the
integer expressions, and the various forall-declarators are declared as
parallel int (long?) variables in that shape, and are initialized with the
corresponding pcoords.  The forall's statement is then executed.  

Example:

    
shape [1000][2000]S;
....
void subr(float:S *v, float:S *w, float:S *x, float:S *y)
{
  /* copy all of of w to v*/
  forall(i=1000,j=2000) {
    [i][j]*v = [i][j]*w;
  }
  /* copy a section of y to x */
  forall(i=100,j=200) {
    [i+2][j+10]*x = [i+3][j+14]*y;
  }
}



This is defined to be equivalent to the following rewrite in which the
iterators are defined based on calls to pcoord.

shape [1000][2000]S;

....
void subr(float:S *v, float:S *w, float:S *x, float:S *y)
{
  /* copy all of of w to v*/
  {
    shape [1000][2000]S2;
      with(S2) {
        int:S2 i=pcoord(0), j=pcoord(1);
        [i][j]*v = [i][j]*w;
    }
  }


  /* copy a section of y to x */
  {
    shape [100][200]S2;
    with(S2) {
      int:S2 i=pcoord(0), j=pcoord(1);
      [i+2][j+10]*x = [i+3][j+14]*y;
    }
  }
}


As part of the rewrite, FORALL introduces a new shape and user code within
the FORALL can rely on the "current shape" being changed to that new shape.

Note that FORALL invariably mixes computation and communication, because
FORALL statements invariably make use of left indexing with the iterators
on the left side.  It is likely that compilers will recognize where this is
not necessary and produce a better translation.  For example, no
communication is necessary when copying all of v to w (the compiler must
create the iterators in the same shape as the v and w, and then must
recognize that the left indexing is a no-op.)  The same compiler technology
applies to this as does to the compilation of HPF and CM Fortran's FORALL.
Nevertheless, a user who needs total control over when communication will
and will not take place will likely avoid FORALL because of its lack of
transparency.


OTHER EXAMPLES:

Matrix Multiply:

shape [m][n]S1;
shape [m][l]S2;
shape [l][n]S3;
...
void f(shape S1, shape S2, shape S3, double:S1 *a, double:S2 *b, double:S3 *c)
{
  int m = dimof(S1,0);
  int l = dimof(S2,1);
  int n = dimof(S3,1);
  forall(i=m,j=n,k=l) {
    [i][j]*a += [i][k]*b * [k][j]*c; 
  }
}


Transpose:

void trans(double:current *x)
{
  int dim = dimof(*x,0);
  forall(i=dim,j=dim) [i][j]*x = [j][i]*x;
}


Transpose with two executable statements in forall::

void trans(double:current *x)
{
  int dim = dimof(*x,0);
  forall(i=dim,j=dim) {
    double:shapeof(i) t;
    t = [j][i]*x;
    [i][j]*x = t;
  }
}

/*  Note that the second transpose above includes multiple statements within a
    forall, but there are so synchronization ambiguities.  FORALL semantics are
    defined by a rewrite rule so that the base language semantics (operator by
    operator synchronization) are in effect.  */


Set diagonal values of square matrix to zero:

void diag(double:current *x)
{
  int dim = dimof(*x,0);
  forall(i=dim) 
    [i][i]*x = 0;
}


Same thing, but done inefficiently

void diag(double:current *x)
{
  int dim = dimof(*x,0);
  forall(i=dim,j=dim) 
    where (i==j)
      [i][j]*x = 0;
}



POSSIBLE EXTENSIONS:

This document proposes a FORALL with minimal functionality in order to
keep things simple.  If we decide that we do want to add a FORALL to the
base document, there are a number of extensions we might want to explore.

An obvious extension would be new syntax to define iterator values to take
values based on a stop/start/stride rather than just taking on values from
pcoord.  Without that, the FORALL user must calculate values based on the
indexes as I did in the first example with:

    [i+2][j+10]x = [i+3][j+14]y;

The base FORALL described in this document can be defined by a rewrite rule
and does not introduce any ambiguities about synchronization.  One FORALL
extension would be introduce a FORALL variant (either with pragma or a new
FORALL-MIMD type of statement) as a hook to call MIMD procedures or pure
procedures that the user guarantees to have reduced synchronization
requirements.  A number of different FORALL variants have been proposed for
HPF and they can lead to more efficient execution on both serial and
parallel target machines.