(j3.2006) Integration of co-arrays with the intrinsic shift functions

[Craig Rasmussen]

On Jul 13, 2007, at 11:00 AM, Aleksandar Donev wrote:

> On Friday 13 July 2007 07:59, Bill Long wrote:
>
>>  If Aleks wants to think of the co-dimensions as additional planes  
>> in a
>> higher dimension array, that's also fine.
> Just to make it clear: The standard clearly does not look at them  
> in any
> particular way and I prefer it that way. I mentioned the  
> "additional planes"
> view because it emphasizes the independence of the different co- 
> arrays on
> each image. In Fortran different dimensions of an array are  
> independent. Of
> course, we have ways to convert contiguous arrays into a different  
> rank
> view---this would not be appropriate for co-arrays.
>
> Early on there was discussion of co-triplet specifications. I want  
> to see them
> eventually, but they had complications too big for this revision.  
> One of the
> issues is that it would need to be settled how to view such arrays  
> when they
> are actual arguments. For example, what is the shape of A(1:5,2:4) 
> [1:5]?
> Since we have not added them in this revision we don't need to  
> fight over
> "global" views of co-arrays...there simply isn't one in the  
> standard at all.
>

Like you and Bill, I had thought that we could punt on the "global  
view" of a co-array declaration.  However, I have identified at least  
one point in the standard that requires a global view, that is the  
shift intrinsics.  The beauty of the data-parallel model is that all  
elements are independent, thus, operations on a data-parallel object  
can be fulfilled without regard to component ordering or storage  
location.  So a reduction or where mask doesn't depend on the array  
global view.

But as pointed out, the shift intrinsics require a global view so we  
have to, at the very least, start thinking about a global view, or  
frankly we should just deprecate the data-parallel features of  
Fortran 90.

To start off, I'll define a couple of terms and then present one  
possible global view of a co-array declaration.  The definitions have  
been borrowed from the very thorough paper, "An Approach to Data  
Distributions in Chapel" by Diaconescu and Zima.

TERMS

global index set: The finite set of names identifying the components  
of an array.

distribution: A specification of the global mapping from the index  
set of an array to individual images, as well as the local  
arrangement of indices and data within the images.

So what we need to define is essentially the inverse of a  
distribution.  That is, a standard mapping from a co-array  
declaration to a global index set.  But consider for now the index  
set {1:12}  (I'm using {} notation to indicate the "global view").   
What should the distribution be for a co-array of rank 1 and co-rank  
1, assuming local size of 3 and num_images() of 4?  A very natural  
distribution is

     {1:3} -> (1:3)[1], {4:6} -> (1:3)[2], ... {10:12} -> (1:3)[4]

Complications arise when the rank and co-rank are not the same.   
After thinking about this for awhile, I propose the following mapping  
(shown for 2D but easily extended to other dimensions):

     For A(m,n)[mp,np], the global index set ("global view") is  
{1:m*mp,1:n*np}.  Should the rank and co-rank differ, expand the rank  
of the smaller by adding additional dimensions of size 1 and apply  
the standard mapping as before.  For example,

     A(m)[mp,np] -> A(m,1)[mp,np]

The challenge for the next standard is to figure out how to allow for  
user-defined distributions.  (Alek's, if you have a better idea than  
the one I've just described please suggest it.)

The alternative is to ignore the issue altogether and allow Fortran  
to degenerate into an assembly language for parallel programming.  I  
suggest that this is counter to the spirit of Fortran.  By simply  
defining a standard distribution (perhaps the one I've suggested  
above) and applying it to the shift intrinsics, we can maintain the  
spirit of Fortran as a high level programming language, but now a  
high-level parallel programming language.  The essential beauty of  
what we can provide to the programmer is really the best of both  
worlds: the ability to program at a high level of abstraction or to  
drop down to the "assembly level", if it is required to explicitly  
manage separate images and the data residing on them (just as  
assembly programmers explicitly manage data transfer between  
registers and the local store).

Regards,
Craig