Hybrid interconnection topologies for high performance and low hardware cost based on hypercube and k-ary n-tree

Junhong Li, Yaodong Wang, Yamin Li


In the field of high-performance parallel computing, interconnection networks based on fat-tree topology have been widely used. A leaf-level switch can be connected to k computing nodes through k links for a traditional fat-tree structure. If a large-scale high-performance also uses traditional fat-tree, it requires a large number of switches and links to connect computing nodes, which will significantly increase the hardware cost. In this regard, this paper proposes two hybrid topologies to solve this problem by combining fat-tree and hypercube, named k-ary n-tree k-cube (KANTC) and Mirrored k-ary n-tree k-cube (MiKANTC). Instead of connecting k compute nodes to a leaf switch directly, we replace all the leaf-level switches of the k-ary n-tree with k-cubes. In this way, the leaf level will have k^{n-2} k-cubes, where each cube will select k switches to connect to the upper level of the k-ary n-tree, and the rest of the switches will be used to connect to the compute nodes. Each cube can connect k(2^k-k) compute nodes. We give routing algorithms based on shortest path, and evaluated path diversity, cost, performance for KANTC and MiKANTC. The results show that the KANTC and MiKANTC can save 84% of switches and 78% of links in massively parallel systems when k=n=8, compared to fat trees, and both KANTC and MiKANTC have higher path diversity than fat-tree.


interconnection network; fat-tree; hypercube; hardware cost; routing algorithm; path diversity

Full Text:



  • There are currently no refbacks.