Scheduling of Unstructured Communication on the Intel iPSC/860

In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention as well as link contention. We discuss the theoretical complexity of these algorithms and study their effectiveness both from the view of static scheduling and from runtime scheduling. Experimental results for our algorithms are presented on the iPSC/860. 1 Introduction Experience with parallel computing has shown that a "good" mapping is a critical part of executing a program on massively parallel processing machines. The mapping typically can be performed statically or dynamically. For most regular and synchronous problems, this mapping can be performed at the time of compilation by giving directives in the language to decompose the data and its corresponding computations (based on the owner computes rule) [5]. This typically results in regular collective communication between processors. Many..