All-to-all communication with minimum start-up costs in 2D/3D tori and meshes
SCIE
SCOPUS
- Title
- All-to-all communication with minimum start-up costs in 2D/3D tori and meshes
- Authors
- Suh, YJ; Yalamanchili, S
- Date Issued
- 1998-05
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- Abstract
- All-to-all communication patterns occur in many important parallel algorithms. This paper presents new algorithms for all-to-all communication patterns (all-to-all broadcast and all-to-all personalized exchange) for wormhole switched 2D/3D torus-and mesh-connected multiprocessors. The algorithms use message combining to minimize message start-ups at the expense of larger message sizes. The unique feature of these algorithms is that they are the first algorithms that we know of that operate in a bottom-up fashion rather than a recursive, top-down manner. For a 2(d) x 2(d) torus or mesh, the algorithms for all-to-all personalized exchange have time complexity of O(2(3d)). An important property of the algorithms is the O(d) time due to message start-ups, compared with O(2(d)) for current algorithms [15], [18]. This is particularly important for modern parallel architectures where the start-up cost of message transmissions still dominates, except for very large block sizes. Finally. the 2D algorithms for all-to-all personalized exchange are extended to O(2(4d)) algorithms in a 2(d) x 2(d) x 2(d) 3D torus or mesh. These algorithms also retain the important property of O(d) time due to message start-ups.
- Keywords
- interprocessor communication; parallel algorithms; collective communication; all-to-all communication; all-to-all broadcast; all-to-all personalized exchange; complete exchange; WORMHOLE
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/25764
- DOI
- 10.1109/71.679215
- ISSN
- 1045-9219
- Article Type
- Article
- Citation
- IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, vol. 9, no. 5, page. 442 - 458, 1998-05
- 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.