Optimal Algorithms for All-to-All Personalized Communication on Rings and Two Dimensional Tori
✍ Scribed by Chi Chung Lam; C.-H. Huang; P. Sadayappan
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 254 KB
- Volume
- 43
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
All-to-all personalized communication is a basic communication operation in a parallel computing environment. In this operation, each processor sends a distinct message to every other processor. It is used in several parallel algorithms, such as for the fast Fourier transform. This paper presents new algorithms to perform all-to-all personalized communication on ring-and torusstructured networks of p processors, where p = 4k and p ≥ 8 for rings, and p = 4k × 4k and p ≥ 64 for two-dimensional tori. The algorithms optimally utilize all communication links and complete the operation in p 2 /8 and p √ p p p/8 communication steps for rings and two-dimensional tori, respectively.