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

摘要

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 stair-cube interconnection network gives reasonable speedup as compared to hypercube and star graph as FFT processor. Keywods hypercube; star graph; average-distance; degree; diameter; faun-tolerance; routing; fast fourier transform; speedup