Static and Runtime Algorithms for All-to-Many Personalized Communication on Permutation Networks

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