ALL-TO-ALL COMMUNICATION WITH MINIMUM START-UP COSTS IN 2D 3D TORI AND MESHES/

All-to-all communication patterns occur in many important parallel alg orithms. This paper presents new algorithms for all-to-all communicati on 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 a t the expense of larger message sizes. The unique feature of these alg orithms is that they are the first algorithms that we know of that ope rate 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 persona lized 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 si zes. Finally. the 2D algorithms for all-to-all personalized exchange a re 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) tim e due to message start-ups.