All to-all communication with minimum start-up costs in 2D/3D toriand meshes |
| |
Authors: | Young-Joo Suh Valamanchili S. |
| |
Affiliation: | Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI; |
| |
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 2d×2d torus or mesh, the algorithms for all-to-all personalized exchange have time complexity of O(23d). An important property of the algorithms is the O(d) time due to message start-ups, compared with O(2d) for current algorithms. 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(24d) algorithms in a 2d×2d×2d3D torus or mesh. These algorithms also retain the important property of O(d) time due to message start-ups |
| |
Keywords: | |
|
|