Time-Step Optimal Broadcasting in 3-D Meshes with Minimum Total Communication Distance

Authors: Cang S.; Wu J.

Source: Journal of Parallel and Distributed Computing, Volume 60, Number 8, August 2000 , pp. 966-997(32)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

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. Copyright 2000 Academic Press.

Keywords: broadcast; communication distance; divide-and-conquer; meshes; optimization problems; wormhole routing

Language: English

Document Type: Research article

Affiliations: Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, Florida, 33431

Publication date: 2000-08-01