Irregular Personalized Communication on Distributed Memory Machines

In this paper we present several algorithms for performing all-to-many personalized communication on distributed memory parallel machines. We assume that each processor sends a different message (of potentially different size) to a subset of all the processors involved in the collective communication. The algorithms are based on decomposing the communication matrix into a set of partial permutations. We study the effectiveness of our algorithms both from the view of static scheduling and from runtime scheduling. Index Terms: Loosely synchronous communication, node contention, non-uniform message size, personalized communications, runtime scheduling, static scheduling. 1 Introduction Load balancing and reduction of communication are two important issues for achieving good performance on distributed memory parallel computers. It is important to map the program such that the total execution time is minimized; the mapping typically can be performed statically or dynamically. For most r..