Computing global combine operations in the multi-port postal model

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Consider a message-passing system of n processors each holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n distributed pieces of data and to make the result known to all the processors. We model the message-passing system using the parameter k for the k-port model and the parameter λ for the communication latency in the postal model. In this general model, each processor during each round r can send messages to any set of k processors and receive messages from any other set of k processors, which were sent out during round r-λ+1, provided r-λ+1≥1. We describe an optimal algorithm that requires the least number of communication rounds and minimizes the time spent by each processor in sending and receiving messages.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
Editors Anon
PublisherPubl by IEEE
Pages336-343
Number of pages8
ISBN (Print)081864222X
StatePublished - 1993
Externally publishedYes
EventProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA
Duration: Dec 1 1993Dec 4 1993

Publication series

NameProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

Other

OtherProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
CityDallas, TX, USA
Period12/1/9312/4/93

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

Dive into the research topics of 'Computing global combine operations in the multi-port postal model'. Together they form a unique fingerprint.

Cite this