CRPC-TR93319-S

Title:	  Slicing Analysis and Indirect Accesses to Distributed Arrays

Authors:  R. Das, J. Saltz, R. v. Hanxleden*

Date:	  August 1993

* student author


Keywords:
  Distributed memory, Irregular applications, Inspector-Executor,
  Slicing, Fortran D, High Performance Fortran

Abstract:

An increasing fraction of the applications targeted by parallel
computers makes heavy the use of indirection arrays for indexing data
arrays.  Such irregular access patterns make it difficult for a
compiler to generate efficient parallel code.  Previously developed
techniques addressing this problem are limited in that they are only
applicable for a single level of indirection.  However, many codes
using sparse data structures access their data through multiple levels
of indirection.

This paper presents a method for transforming programs using multiple
levels of indirection into programs with at most one level of
indirection, thereby braodening the range of applications that a
compiler can parallelize efficiently.  A central concept of our
algorithm is to perform program slicing on the subscript expressions
of the indirect array accesses.  Such slices peel off the levels of
indirection, one by one, and create opportunities for aggregated data
prefetching in between.  A slice graph eliminates redundant
preprocessing and gives an ordering in which to compute the slices.
We present our work in the context of High Performance Fortran; an
implementation in a Fortran D prototype compiler is in progress.

Appeared in:  Proceedings of the Sixth Workshop on Languages and
 	      Compilers for Parallel Computing, Portland, OR