Document Type
Article
Date
1993
Keywords
asynchronous communication, link and node contention, loosely synchronous communication, runtime and static scheduling
Language
English
Disciplines
Computer Sciences
Description/Abstract
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-to-many 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.
Recommended Citation
Ranka, Sanjay and Wang, Jyu-Chun, "Static and Runtime Scheduling of Unstructured Communication" (1993). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 28.
https://surface.syr.edu/lcsmith_other/28
