Computing global combine operations in the multi-port postal model
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 336-343
- https://doi.org/10.1109/spdp.1993.395514
Abstract
Consider a message-passing system of n processors and 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 /spl lambda/ 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 set out during round r-/spl lambda/+1, provided r-/spl lambda/+1/spl ges/1 We describe an optimal algorithm that requires the least number of communication rounds and minimizes the time spent by each processor in sending an receiving messages.Keywords
This publication has 16 references indexed in Scilit:
- Efficient Global Combine OperationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Global combine on mesh architectures with wormhole routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Process Groups: a mechanism for the coordination of and communication among processes in the Venus collective communication libraryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The Network Architecture of the Connection Machine CM-5Journal of Parallel and Distributed Computing, 1996
- AN OPTIMAL ALGORITHM FOR COMPUTING CENSUS FUNCTIONS IN MESSAGE-PASSING SYSTEMSParallel Processing Letters, 1993
- LogP: towards a realistic model of parallel computationPublished by Association for Computing Machinery (ACM) ,1993
- Intensive hypercube communication Prearranged communication in link-bound machinesJournal of Parallel and Distributed Computing, 1990
- Paris: An approach to integrated high‐speed private networksInternational Journal of Communication Systems, 1988
- New models and algorithms for future networksPublished by Association for Computing Machinery (ACM) ,1988
- New gossips and telephonesDiscrete Mathematics, 1975