Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol.18 No.6, pp.959-980 (November 2002)


Multi-Node Multicast in Multi-Dimensional Wormhole
Tori and Meshes With Load Balance

Ming-Hour Yang*, Yu-Chee Tseng* and Ming-Shian Jian
Department of Computer Science and Information Engineering
National Central University
Chungli, 320 Taiwan
*Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, 300 Taiwan
E-mail: yctseng@csie.nctu.edu.tw

This paper considers the multi-node multicast problem in a multi-dimensional wormhole-routed torus/mesh, where there is an arbitrary number of source nodes, each intending to multicast a message to an arbitrary set of destinations. This problem requires a large amount of bandwidth and, thus, typically incurs heavy contention and congestion. Evenly balancing the traffic load around the network is critical to achieving good performance. We show how to use a network-partitioning approach to achieve this goal. Simulation results show significant improvement over existing results in 3D tori and meshes. This work is an extension of our earlier work [22] from 2D tori/meshes to higher dimensional ones.

Keywords: collective communication, interconnection network, load balance, mesh, multicast, parallel processing, torus, wormhole routing

Full Text () Retrieve PDF document (200211_06.pdf)

Received September 3, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makoto Takizawa and Myongsoon Park.