A Branch-and-Bound Algorithm for Array Distributions

An important problem facing parallelizing compilers for distributed memory mimd machines is that of distributing data across processors. This distribution affects the amout of data movements among processors that is required to execute the computations of the input program. This work proposes a branch--and--bound based method to automatically compute a distribution for the arrays of the input program. The method is able to arrange redistributions of data during program execution. To test the proposed method, we have embedded it into an experimental parallelizing compiler for an Intel iPSC=860. Results with this compiler for example like the Livermore Loop Kernels show that the computed data distributions are very good. 1 Introduction Distributed memory mimd computers (DMMs) offer a cost effective performance because they are less expensive to build than shared memory machines and are scalable to a large number of processors. Unfortunately, these machines are not easy to porgram becaus..