A broadcast algorithm for all-port wormhole-routed torus networks

Author

Tsai, Yih-Jia ; McKinley, Philip K.

Author_Institution

Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA

fYear

1995

fDate

6-9 Feb 1995

Firstpage

529

Lastpage

536

Abstract

A new approach to broadcast in wormhole-routed two- and three-dimensional torus networks is proposed. The approach extends the concept of dominating sets from graph theory by accounting for the relative distance-insensitivity of the wormhole routing switching strategy and by taking advantage of an allport communication architecture. The resulting broadcast operation is based on a tree structure that uses multiple levels of extended dominating nodes (EDN). Performance results are presented that confirm the advantage of this method over recursive doubling

Keywords

graph theory; multiprocessor interconnection networks; network routing; all-port wormhole-routed torus networks; allport communication architecture; broadcast algorithm; dominating sets; extended dominating nodes; graph theory; performance results; recursive doubling; switching strategy; tree structure; Broadcasting; Communication switching; Computer networks; Computer science; Concurrent computing; Delay; Graph theory; Routing; Tree data structures; Unicast;

fLanguage

English

Publisher

ieee

Conference_Titel

Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the

Conference_Location

McLean, VA

Print_ISBN

0-8186-6965-9

Type

conf

DOI

10.1109/FMPC.1995.380471

Filename

380471