Title
Static and Runtime Algorithms for All-to-Many Personalized Communication on Permutation Networks
Document Type
Article
Date
1992
Keywords
loosely synchronous communication, permutation networks, personalized communications, runtime scheduling, SPMD, 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. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. We discuss several algorithms and study their effectiveness from the view of static scheduling as well as runtime scheduling. An approximate analysis shows that with n processors and assuming that every processor sends and receives d messages to random destinations, our algorithm can perform the scheduling in O(dn ln d) time on an average, and use an expected number of d + log d partial permutations to carry out the communication. We present experimental results of our algorithms on the CM-5.
Recommended Citation
Ranka, Sanjay; Wang, Jhy-Chun; and Fox, Geoffrey C., "Static and Runtime Algorithms for All-to-Many Personalized Communication on Permutation Networks" (1992). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 1.
https://surface.syr.edu/lcsmith_other/1
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
