Broadcasting on wormhole-routed 2D tori with arbitrary size

Author

Hou, Yomin ; Wang, Chien-Min ; Tsai, Ming-Jer ; Hsu, Lih-Hsing

Author_Institution

Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan

fYear

1998

fDate

14-16 Dec 1998

Firstpage

334

Lastpage

341

Abstract

For distributed memory parallel computers, broadcast operations are widely used in a variety of applications. In this paper we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 2D torus with arbitrary size. The underlying network is assumed to support only the dimension-ordered unicast. By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can greatly reduce the number of message-passing steps. In addition, it can be proved to be depth contention-free. The performance study in this paper clearly shows the advantage of the proposed algorithm

Keywords

broadcasting; distributed algorithms; distributed memory systems; message passing; multiprocessor interconnection networks; network routing; algorithm performance; arbitrary size all-port wormhole-routed 2D torus; broadcasting; depth contention-free algorithm; dimension-ordered unicast; distance insensitivity; distributed memory parallel computers; efficient algorithm; message-passing steps; Broadcasting; Computer worms; Concurrent computing; Councils; Information science; Multiprocessor interconnection networks; Network topology; Reactive power; Routing; Switches;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 1998. Proceedings. 1998 International Conference on

Conference_Location

Tainan

ISSN

1521-9097

Print_ISBN

0-8186-8603-0

Type

conf

DOI

10.1109/ICPADS.1998.741093

Filename

741093