Automatic Array Alignment as a Step in Hierarchical Program Transformation

We present an original approach to automatic array alignment, the step in the hierarchical transformation system aimed at the efficient execution of shared memory programs on distributed memory machines. Our array alignment algorithm deals with a broad set of intra-dimension and inter-dimension alignment preferences, including offsets, strides, permutations, embeddings, and their combinations. We discuss the algorithm and the tests performed on the Connection Machine CM-2. 1 Introduction The trade-off between code portability and high performance is a significant problem facing software implemented for parallel machines. We have proposed a multilayered refinement of high level, expressive parallel programs to be performed in a sequence of source-to-source program transformation steps [1]. In this paper we describe the memory transformation step. The memory transformation is applied to data parallel programs which assume shared memory. The transformation is expected to speed-up the pro..