Optimal all-ports collective communication algorithms for the k-ary n-cube interconnection networks

The need for collective communication procedures such as One-to-All broadcast, All-to-All broadcast arises in many parallel or distributed applications. Many of these communication procedures have been studied for many topologies of interconnection networks such as hypercubes, meshes, De Bruijn, sta...

Full description

Saved in:
Bibliographic Details
Published in:Journal of systems architecture 2004-03, Vol.50 (4), p.221-231
Main Author: Touzene, Abderezak
Format: Article
Language:English
Subjects:
Algorithms
Broadcast
Communication
Decision trees
Edge-disjoint spanning trees
Fault tolerance
Interconnect
Interconnection networks
Optimization
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The need for collective communication procedures such as One-to-All broadcast, All-to-All broadcast arises in many parallel or distributed applications. Many of these communication procedures have been studied for many topologies of interconnection networks such as hypercubes, meshes, De Bruijn, star graphs and butterflies. In this paper we propose a construction of multiple edge-disjoint spanning trees for the k-ary n-cube which can be used to derive an optimal and fault tolerant broadcasting algorithm. We propose also an optimal All-to-All broadcasting algorithm. We consider the k-ary n-cube as a point-to-point interconnection, using store-and-forward, all-port assumption and a linear communication model.
ISSN:1383-7621
1873-6165
DOI:10.1016/j.sysarc.2003.09.003