Abstract
The operations of scattering and gathering in a network of processors involve one processor of the network–call it Po —communicating with all other processors. In scattering, Po sends (possibly) distinct messages to all other processors; in gathering, the other processors send (possibly) distinct messages to P o. We consider networks that are trees of processors. We present algorithms for scattering messages from and gathering messages to the processor that resides at the root of the tree. The algorithms are: 1) quite general, in that the messages transmitted can differ arbitrarily in length; 2) quite strong, in that they send messages along noncolliding paths, hence do not require any buffering or queuing mechanisms in the processors; and 3) quite efficient: The algorithms for scattering in general trees are optimal, the algorithm for gathering in a path is optimal, and the algorithms for gathering in general trees are nearly optimal. Our algorithms can easily be converted, via the use of spanning trees, to efficient algorithms for scattering and gathering in networks of arbitrary topologies.
| Original language | English |
|---|---|
| Pages (from-to) | 938-949 |
| Number of pages | 12 |
| Journal | IEEE Transactions on Computers |
| Volume | 42 |
| Issue number | 8 |
| DOIs | |
| State | Published - Aug 1993 |
Keywords
- Bufferless communication
- communication primitives
- communication schedules
- distributed scheduling
- interconnection networks
- message routing
- one-to-all personalized communication