Time-Step Optimal Broadcasting in 3-D Meshes with Minimum Total Communication Distance
✍ Scribed by Songluan Cang; Jie Wu
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 440 KB
- Volume
- 60
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
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 d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations. 2000