Scattering and Gathering Messages in Networks of Processors

Sandeep N. Bhatt, Geppino Pucci, Abhiram Ranade, Arnold L. Rosenberg

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

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 languageEnglish
Pages (from-to)938-949
Number of pages12
JournalIEEE Transactions on Computers
Volume42
Issue number8
DOIs
StatePublished - Aug 1993

Keywords

  • Bufferless communication
  • communication primitives
  • communication schedules
  • distributed scheduling
  • interconnection networks
  • message routing
  • one-to-all personalized communication

Fingerprint

Dive into the research topics of 'Scattering and Gathering Messages in Networks of Processors'. Together they form a unique fingerprint.

Cite this