DATA AND TASK ALIGNMENT IN DISTRIBUTED-MEMORY ARCHITECTURES

Different alignments of multidimensional arrays on a meshconnected SIM D architecture result in different communication patterns during paral lel program execution. In this paper a compile-time selection of data alignment that minimizes communication cost is discussed. First, it is shown that the selection is computationally as hard as a subclass of the well-known problem of finding the closest vector in a lattice. The NP-hardness of the latter problem is proven. Then, two algorithms for exact minimum solution(s) are discussed. Although the complexity of t hese algorithms is exponential, for small lattices often generated by parallel scientific computation the execution times of these algorithm s may be acceptable. A polynomial-time algorithm for finding an approx imate solution is also described. Finally, improvement in communicatio n cost resulting from alignments for randomly generated graphs are pre sented. (C) 1994 Academic Press, Inc.