A transformational approach to compiling Sisal for distributed memory architectures

This paper is concerned with the efficient execution of array computation on Distributed Memory Architectures by applying compiler-directed program and data transformations. By translating a subset of a single-assignment language, Sisal, into a linear algebraic framework it is possible to transform a program so as to reduce load imbalance and non-local memory access. A new test is presented which allows the construction of transformations to reduce load imbalance. By a new expression of data alignment, transformations to reduce non-local access are derived. Three criteria for partitioning are given as well as a systematic method to map the data and computation to the processors. Finally a new pre-fetching procedure, which prevents redundant non-local accesses, is presented.