STATIC AND RUN-TIME ALGORITHMS FOR ALL-TO-MANY PERSONALIZED COMMUNICATION ON PERMUTATION NETWORKS

With the advent of new routing methods, the distance that a message is sent is becoming relatively less and less important. Thus, assuming n o link contention, permutation seems to be an efficient collective com munication primitive. In this paper, we present several algorithms for decomposing all-to-many personalized communication into a set of disj oint partial permutations. We discuss several algorithms and study the ir effectiveness from the view of static scheduling as well as run-tim e scheduling. An approximate analysis shows that with n processors, an d assuming that every processor sends and receives d messages to rando m destinations, our algorithm can perform the scheduling in O(dn ln d) time, on average, and can 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.