TY - JOUR
T1 - Scattering and Gathering Messages in Networks of Processors
AU - Bhatt, Sandeep N.
AU - Pucci, Geppino
AU - Ranade, Abhiram
AU - Rosenberg, Arnold L.
PY - 1993/8
Y1 - 1993/8
N2 - 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.
AB - 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.
KW - Bufferless communication
KW - communication primitives
KW - communication schedules
KW - distributed scheduling
KW - interconnection networks
KW - message routing
KW - one-to-all personalized communication
UR - http://www.scopus.com/inward/record.url?scp=0027649208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027649208&partnerID=8YFLogxK
U2 - 10.1109/12.238484
DO - 10.1109/12.238484
M3 - Article
AN - SCOPUS:0027649208
SN - 0018-9340
VL - 42
SP - 938
EP - 949
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 8
ER -