Reducing communication by honoring multiple alignments
David A. Garza-Salazar, W. Böhm · 1995
Data Decomposition involves the mapping of array to processors of a Distributed Memory Machine goal to obtain the best possible performance of a elements with the program by keeping communication costs-low while exploiting 'parallelism.Data decomposition is typically divided into two subproblems: alignment and partitioning.Alignment deals with the relative allocation of different arrays.Partitioning is concerned with the actual distribution of the array elements among processors.Conflicting alignments may cause communication.This paper presents a technique for reducing communication by honoring multiple alignments and applies this approach in a distributed memory implementation of the strict functional language Sisal..Multiple alignment leads to recomputation and replication of array elements, which is safe in a functional, and hence side effect free, setting.We present performance improvements of up to 80~o for one dimensional arrays, and up to 50% for two dimension al arrays, compared to single alignment implementations on a cluster of workstations.