Document Type
Article
Date
1995
Keywords
bounded traffic, many-to-many communication, traffic, message size variance
Language
English
Disciplines
Computer Sciences
Description/Abstract
This paper presents solutions for the problem of many-to-many personalized communication, with bounded incoming and outgoing traffic, on a distributed memory parallel machine. We present a two-stage algorithm that decomposes the many-to-many communication with possibly high variance in message size into two communications with low message size variance. The algorithm is deterministic and takes time 2tµ (+ lower order terms) when t >= O(p2; + p tau/µ). Here t is the maximum outgoing or incoming traffic at any processor, tau is the startup overhead and µ is the inverse of the data transfer rate. Optimality is achieved when the traffic is large, a condition that is usually satisfied in practice on coarse-grained architectures. The algorithm was implemented on the Connection Machine CM-5. The implementation used the low latency communication primitives (active messages) available on the CM-5, but the algorithm as such is architecture-independent. An alternate single-stage algorithm using distributed random scheduling for the CM-5 was implemented and the performance of the two algorithms were compared.
Recommended Citation
Ranka, Sanjay; Shankar, Ravi V.; and Alsabti, Khaled A., "Many-to-many Personalized Communication with Bounded Traffic" (1995). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 15.
https://surface.syr.edu/lcsmith_other/15
