One-to-all broadcast algorithm for constant degree 4 Cayley graphs

Broadcasting in interconnection networks is crucial because of its multiple utilization in linear algebra problems, neural networks, optimization problems and other fields alike. Many global communication algorithms have been studied for different topologies of interconnection networks such as hyper...

Full description

Saved in:
Bibliographic Details
Published in:Parallel computing 1999-03, Vol.25 (3), p.249-264
Main Authors: Benmaiza, Mohamed, Touzene, Abderezak
Format: Article
Language:English
Subjects:
Broadcasting algorithm
Cayley graphs
Communication model
Interconnection network
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Broadcasting in interconnection networks is crucial because of its multiple utilization in linear algebra problems, neural networks, optimization problems and other fields alike. Many global communication algorithms have been studied for different topologies of interconnection networks such as hypercubes, meshes, De Bruijn graphs, and Star graphs. In a recent paper, Vadapalli and Srimani proposed a new class of constant degree 4 Cayley graphs along with an optimal routing algorithm. We extended this work by proposing an efficient one-to-all broadcasting algorithm for constant degree 4 Cayley graphs of dimension n presented in this paper. The proposed algorithm is based on the construction of edge-disjoint spanning trees of height 2 n and uses pipelining techniques. Communication is assumed to be full-duplex and based on store-and-forward techniques. We also assume a communication model with linear communication times. Based on these assumptions, we show that the performances of the proposed algorithm depend only on the dimension of the graph and are near optimal in terms of propagation delay.
ISSN:0167-8191
1872-7336
DOI:10.1016/S0167-8191(98)00109-4