Time-step optimal broadcasting in 3-D meshes with minimum total communication distance
In this paper we propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 3-dimensional mesh (3-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 3-D mesh is partitioned into eight submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. The proposed approach can be generalized to a cl-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations. (C) 2000 Academic Press.
broadcast meshes communication distance divide-and-conquer optimization problems wormhole routing