CaltechAUTHORS
  A Caltech Library Service

Computing global combine operations in the multiport postal model

Bar-Noy, Amotz and Bruck, Jehoshua and Ho, Ching-Tien and Kipnis, Shlomo and Schieber, Baruch (1995) Computing global combine operations in the multiport postal model. IEEE Transactions on Parallel and Distributed Systems, 6 (8). pp. 896-900. ISSN 1045-9219. http://resolver.caltech.edu/CaltechAUTHORS:BARieeetpds95

[img]
Preview
PDF
See Usage Policy.

519Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BARieeetpds95

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


Item Type:Article
Additional Information:© Copyright 1995 IEEE. Reprinted with permission. Manuscript received June 8, 1994; revised Oct. 19, 1994. Jehoshua Bruck was supported in part by the National Science Foundation Young Investigator Award CCR-9457811; by the Sloan Research Fellowship; by a grant from the IBM Almaden Research Center, San Jose, California; and by a grant from the AT&T Foundation.
Subject Keywords:Census computation, distributed systems, global combine, gossiping, message-passing systems, multiple ports, parallel computers, postal model
Record Number:CaltechAUTHORS:BARieeetpds95
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BARieeetpds95
Alternative URL:http://dx.doi.org/10.1109/71.406965
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5556
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:25 Oct 2006
Last Modified:26 Dec 2012 09:13

Repository Staff Only: item control page