A framework for integrating data alignment, distribution, and redistribution in distributed memory multiprocessors

Parallel architectures with physically distributed memory provide a cost-ef fective scalability to solve many large scale scientific problems. However, these systems are very difficult to program and tune. In these systems, th e choice of a good data mapping and parallelization strategy can dramatical ly improve the efficiency of the resulting program. In this paper, we prese nt a framework for automatic data mapping in the context of distributed mem ory multiprocessor systems. The framework is based on a new approach that a llows the alignment, distribution, and redistribution problems to be solved together using a single graph representation. The Communication Parallelis m Graph (CPG) is the structure that holds symbolic information about the po tential data movement and parallelism inherent to the whole program. The CP G is then particularized for a given problem size and target system and use d to find a minimal cost path through the graph using a general purpose lin ear 0-1 integer programming solver. The data layout strategy generated is o ptimal according to our current cost and compilation models.