Paper Info
Title
A Novel Low Cost Interconnection Architecture Based on the Generalized Hypercube
Abstract
The generalized hypercube (GH) is one key interconnection network with excellent topological properties. It contains many other interconnection topologies, such as the hypercube network, the complete graph, the mesh network, and the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq1-2941207.gif"/></alternatives></inline-formula> -ary <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq2-2941207.gif"/></alternatives></inline-formula> -cube network. It can also be used to construct some data center networks, such as HyperX, BCube, FBFLY, and SWCube. However, the construction cost of GH is high since it contains too many links. In this paper, we propose a novel low cost interconnection architecture called the exchanged generalized hypercube (EGH). We study the properties of EGH, such as the number of edges, the degree of vertices, connectivity, diameter, and diagnosability. Then, we give a routing algorithm to find the shortest path between any two distinct vertices of EGH. Furthermore, we design an algorithm to give disjoint paths between any two distinct vertices of EGH. In addition, we propose two local diagnosis algorithms: LDT <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$_{EGH}$</tex-math><alternatives><mml:math><mml:msub><mml:mrow/><mml:mrow><mml:mi>E</mml:mi><mml:mi>G</mml:mi><mml:mi>H</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="wang-ieq3-2941207.gif"/></alternatives></inline-formula> and LDWB <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$_{EGH}$</tex-math><alternatives><mml:math><mml:msub><mml:mrow/><mml:mrow><mml:mi>E</mml:mi><mml:mi>G</mml:mi><mml:mi>H</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="wang-ieq4-2941207.gif"/></alternatives></inline-formula> in EGH under PMC model and MM model, respectively. Simulation results demonstrate that even if the proportion of faulty vertices in EGH is up to 25 percent, the probability that these two diagnosis algorithms can successfully determine the status of vertices is more than 90 percent. As far as the number of edges is concerned, the analysis shows that the construction cost of EGH is much less than that of GH. We could regard this work as the basis for proposing future new high performance topologies.
Year
DOI
Venue
2020
10.1109/TPDS.2019.2941207
IEEE Transactions on Parallel and Distributed Systems
Keywords
DocType
Volume
Hypercubes,Routing,Network topology,Topology,Program processors,Fault tolerance
Journal
31
Issue
ISSN
Citations 
3
1045-9219
2
PageRank 
References 
Authors
0.36
0
5
Name
Order
Citations
PageRank
Guijuan Wang1133.54
Cheng-Kuan Lin241.73
Jianxi Fan371860.15
Cheng Baolei4105.56
Xiaohua Jia54609303.30