CRPC-TR92301-S

Title:	  Compiler Support for Machine Independent Parallelization of
	  Irregular Problems

Author:	  R. v. Hanxleden*

Date:	  November 1992

* student author

Keywords:
  Distributed memory, MIMD, SIMD, Irregular applications, Fortran D,
  High Performance Fortran  

Abstract:

The Fortran D group at Rice University aims at providing a machine
independent data parallel programming style, in which the applications
programmer uses a dialect of sequential Fortran and high level
distribution annotations.  Extracting parallelism from these
applications typically is straightforward, but making efficient use of
this parallelism for irregular applications, such as molecular
dynamics or unstructured meshes, is a challenge due to the limited
compile-time knowledge about data access patterns.

It is my thesis that the spatial locality of the underlying problems
can be used as a basis of compiler support for parallelizing such
applications.  Value-based decompositions are an extension of Fortran
D to express the spatial locality of an application and to assist the
compiler in computing a distribution with both a balanced
computational workload and high data access locality.  A communication
data flow framework detects opportunities to combine messages, move
them into less frequently executed code regions, or even eliminate
them.  Loop flattening is a code transformation to overcome SIMD
specific control flow limitations when executing nested loops with
varying inner loop bounds, which are typical for irregular problems.