Computing Global Combine Operations in the Multiport Postal Model

Amotz Bar-Noy, Baruch Schieber, Jehoshua Bruck, Ching Tien Ho

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

Consider a message-passing system of n processors, in which each processor holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n pieces of data and to make the result known to all the n processors. This operation is frequently used in many message-passing systems and is typically referred to as global combine, census computation, or gossiping. This paper explores the problem of global combine in the multiport postal model. This model is characterized by three parameters: n—the number of processors, k—the number of ports per processor, and λ—the communication latency. In this model, in every round r, each processor can send k distinct messages to k other processors, and it can receive k messages that were sent from k other processors λ-1 rounds earlier. This paper provides an optimal algorithm for the global combine problem that requires the least number of communication rounds and minimizes the time spent by any processor in sending and receiving messages.

Original languageEnglish (US)
Pages (from-to)896-900
Number of pages5
JournalIEEE Transactions on Parallel and Distributed Systems
Volume6
Issue number8
DOIs
StatePublished - Aug 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Census computation
  • distributed systems
  • global combine
  • gossiping
  • message-passing systems
  • multiple ports
  • parallel computers
  • postal model

Fingerprint Dive into the research topics of 'Computing Global Combine Operations in the Multiport Postal Model'. Together they form a unique fingerprint.

Cite this