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. doi:10.1109/71.406965. https://resolver.caltech.edu/CaltechAUTHORS:BARieeetpds95
![]()
|
PDF
See Usage Policy. 531kB |
Use this Persistent URL to link to this item: https://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 | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
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 | ||||||
Issue or Number: | 8 | ||||||
DOI: | 10.1109/71.406965 | ||||||
Record Number: | CaltechAUTHORS:BARieeetpds95 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:BARieeetpds95 | ||||||
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: | 08 Nov 2021 20:27 |
Repository Staff Only: item control page