Generalized-Star Cube: A New Class of Interconnection Topology for Massively Parallel Systems

摘要

In this paper, another version of the star cube called the generalized-star cube, GSC(n, k, m), is presented as a three level interconnection topology. GSC(n, k, m) is a product graph of the (n, k)-star graph and the m-dimensional hypercube (m-cube). It can be constructed in one of two ways: to replace each node in an m-cube with an (n, k)-star graph, or to replace each node in an (n, k)-star graph with an m-cube. Because there are three parametersm, n, and k, the network size of GSC(n, k, m) can be changed more flexibly than the star graph, star-cube, and (n, k)-star graph. This paper describes the topology of the GSC(n, k, m), gives a formal shortest-path routing algorithm, and examines the topological properties of the GSC(n, k, m), such as the node degree, diameter, average distance, and cost. Also, the regularity and node symmetry of the GSC(n, k, m) are derived.