91205-S:  Automatic Data Alignment and Distribution for Loosely 
Synchronous Problems in an Interactive Programming Environment

Ken Kennedy, Ulrich Kremer

April, 1991

An approach to distributed memory parallel programming that has recently 
become popular is one where the programmer explicitly specifies the data 
layout using language extensions, and a compiler generates all the 
communication. While this frees the programmer from the tedium of 
thinking about message-passing, no assistance is provided in determining 
the data layout scheme that gives a satisfactory performance on the 
target machine.  We wish to provide automatic data alignment and 
distribution techniques for a large class of scientific computations, 
known in the literature as loosely synchronous problems.

We propose an interactive software tool that allows the user to select 
regions of the sequential input program, then responds with a data 
decomposition scheme and diagnostic information for the selected region. 
The proposed tool allows the user to obtain insights into the 
characteristics of the program executing on a distributed memory machine 
and the behavior of the underlying compilation system without actually 
compiling and executing the program on the machine.

An empirical study of actual application programs will show whether 
automatic techniques are able to generate data decomposition schemes that 
are close to optimal. If automatic techniques will fail to do so, we want 
to answer the questions (1) how user interaction can help to overcome the 
deficiencies of automatic techniques, and (2) whether, in particular, 
there is a data-parallel programming style that allows automatic 
detection of efficient data alignment and distribution schemes.