All-to-all personalized communication in multidimensional torus and mesh networks
SCIE
SCOPUS
- Title
- All-to-all personalized communication in multidimensional torus and mesh networks
- Authors
- Suh, YJ; Shin, KG
- Date Issued
- 2001-01
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGI
- Abstract
- All-to-all personalized communication commonly occurs in many important parallel algorithms, such as FFT and matrix transpose. This paper presents new algorithms for all-to-all personalized communication or complete exchange in multidimensional torus- or mesh-connected multiprocessors. For an R x C torus or mesh where R less than or equal to C, the proposed algorithms have time complexities of O(C) message startups and O(RC(2)) message transmissions. The algorithms for three- or higher-dimensional tori or meshes follow a similar structure. Unlike other existing message-combining algorithms in which the number of nodes in each dimension should be a power-of-two and square. the proposed algorithms accommodate non-power-of-two tori or meshes where the number of nodes In each dimension need not be power-of-two and square. In addition, destinations remain fixed over a larger number of steps in the proposed algorithms, thus making them amenable to optimizations. Finally, the data structures used are simple, hence making substantial savings of message-rearrangement time.
- Keywords
- collective communication; all-to-all personalized communication; complete exchange; direct exchange; message-combining; interprocessor communication; COLLECTIVE COMMUNICATION; WORMHOLE; ALGORITHMS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/19722
- DOI
- 10.1109/71.899938
- ISSN
- 1045-9219
- Article Type
- Article
- Citation
- IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, vol. 12, no. 1, page. 38 - 59, 2001-01
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.