Decomposition of total exchange for multidimensional interconnects

Author

Dimakopoulos, Vassilios V. ; Dimopoulos, Nikitas J.

Author_Institution

Dept. of Electr. & Comput. Eng., Victoria Univ., BC, Canada

Volume

1

fYear

1996

fDate

12-16 Aug 1996

Firstpage

17

Abstract

Total exchange is an important collective communication problem in multiprocessor interconnection networks. It involves the dissemination of distinct messages from every node to every other node. We present a novel theory for solving the problem in any multidimensional (cartesian product) network. We construct a general algorithm and provide optimality conditions. It is seen that many of the popular topologies, including hypercubes, k-ary n-cubes and general tori satisfy these conditions. The results we present here apply to the single-port model

Keywords

multiprocessor interconnection networks; hypercubes; k-ary n-cubes; multidimensional interconnects; multiprocessor interconnection networks; single-port model; total exchange; Broadcasting; Communication standards; Hypercubes; Linear algebra; Multidimensional systems; Multiprocessor interconnection; Multiprocessor interconnection networks; Network topology; Scattering; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing, 1996. Vol.3. Software., Proceedings of the 1996 International Conference on

Conference_Location

Ithaca, NY

ISSN

0190-3918

Print_ISBN

0-8186-7623-X

Type

conf

DOI

10.1109/ICPP.1996.537138

Filename

537138