STAR-CUBE: A Special Purpose Interconnection Network for Signal Processing

Abstract

Both Hypercube and star graph networks possess desirable properties like regularity, vertex and edge symmetric, maximally fault-tolerant etc, though, some of the attractive features of one are not found in the other. In this paper, we propose and study a composite architecture, which is a combination of these two architectures and call it Star-Cube. The most important characteristic of the proposed star-cube network is that, it can be incremented in smaller steps. This is an advantage for FFT implementation as an architecture with reasonable number of nodes can be made out of this star-cube graph that will give more processor utilization than either star-graph or Hypercube architecture individually. It provides some of the desirable properties of both the networks such as reduced diameter and degree. The degree and diameter of the proposed network falls in-between its individual constituents that make it suitable for Fast Fourier Transform (FFT) type of processing. The proposed Star-Cube network has simple routing algorithms amenable to networks with faults. Other parameters such as average distance, number of links, fault-tolerance, etc, are computed. To show its performance, a Fast Fourier Transform algorithm is considered for implementation in this hybrid network where a hierarchical ranking scheme is adopted for assigning node addresses. We estimate the speedup and efficiency for the Star-cube graph. It is observed that our proposed star-cube interconnection network gives reasonable speedup as compared to hypercube and star graph as FFT processor.

Indexing terms:

• Hypercube
• Star graph
• Average-distance
• Degree
• Diameter
• Fault-tolerance
• Routing
• Fast Fourier Transform
• Speedup

Additional information

Notes on contributors

Raja Datta

Raja Datta completed his BE in Electronics and Telecommunication Engg from Regional Engineering College, Silchar, India in the year 1988. He did his M Tech in the specialisation of Computer Engineering from Indian Institute of Technology, Kharagpur, India. Since 1990 he is working as a faculty member in North Eastern Regional Institute of Science and Technology, Arunachal Pradesh, India, where he is holding the position of Assistant Professor in the Department of Computer Science and Engg. Presently he is pursuing his PhD degree in IIT Kharagpur. His areas of interest are computer architecture, Computer Networks, Optical WDM Networks and Mobile Computing.

Prabir Kumar Biswas

P K Biswas completed his B Tech (Hons), MTech and PhD from the Department of E & ECE, IIT Kharagpur, India in the years 1985, 1989 and 1991 respectively. From 1985 to 1987 he was with Bharat Electronics Ltd., Ghaziabad. Since 1991 he has been working as a faculty member in the Department of Electronics and Electrical Communication Engg., Indian Institute of Technology, Kharagpur, where he is presently holding the position of Associate Professor. His areas of interest include Pattern Recognition, Computer Vision, Video Compression, Parallel and Distributed Processing and Computer Networks.