Static and Runtime Scheduling of Unstructured Communication
Sanjay Ranka, Jyu-Chun Wang · Syracuse University Libraries (Syracuse University) · 1993
With the advent of new routing methods, the distance to which a message is sent is becoming relatively less and less important. Thus assuming no link contention, permutation seems to be an efficient collective communication primitive. All-tomany communication is required for solving a large class of irregular and loosely synchronous problems on distributed memory MIMD machines. 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 and/or link contention. We discuss several algorithms and study their effectiveness both from the view of static scheduling as well as runtime scheduling. Experimental results for our algorithms are presented on the iPSC/860. Index Terms - Asynchronous communication, link and node contention, loosely synchronous communication, runtime and static scheduling. 1 Introduction Experience with parallel computing has shown th...