Document Type

Article

Date

1992

Embargo Period

11-2011

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.

Creative Commons License


This work is licensed under a Creative Commons Attribution 3.0 License.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.