Broadcasting Algorithms for the Star-connected Cycles Interconnection network

Document Type

Article

Publication Date

3-1995

Publication Title

Journal of Parallel and Distributed Computing

Volume

25

First page number:

209

Last page number:

222

Abstract

The star-connected cycles (SCC) graph was recently proposed as an alternative to the cube-connected cycles (CCC) graph, using a star graph to connect cycles of nodes rather than a hypercube. This paper presents an analysis of broadcasting algorithms for SIMD and MIMD SCCs, covering both one-port and multiple-port versions. We show that O(n log n) one-port broadcasting algorithms that have been proposed for the n-star cannot be efficiently extended to the case of the n-SCC graph. However, a simple but rather inefficient algorithm requiring O(n2) steps in the n-star graph can run in O(n) time in the n-SCC if a proper combination of parallelism and transmission rates in the links connecting the nodes is selected. The result is that broadcasting in the n-SCC can be accomplished efficiently, requiring a running time better than or equal to that of an n-star containing (n − 1) times fewer nodes.

Keywords

Computer algorithms; Parallel computers; Wireless sensor nodes

Disciplines

Controls and Control Theory | Electrical and Computer Engineering | Electrical and Electronics | Electromagnetics and Photonics

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.


Search your library

Share

COinS