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

The implementation of fat-tree interconnection networks is prevalent in high-performance parallel computing. However, the traditional fat-tree structure requires a considerable amount of switches and links to connect computing nodes, resulting in a significant increase in hardware costs for large-scale high-performance systems. This study proposes two innovative hybrid topologies, the k-ary n-tree k-cube (KANTC) and the Mirrored k-ary n-tree k-cube (MiKANTC), to address the aforementioned issue. The proposed topologies merge the characteristics of the hypercube and fat-tree structures. Instead of the traditional direct connection of k computing nodes to an edge-level switch, the edge-level switches in the fat-tree are substituted with k-cubes. This results in the formation of k^n−2 k-cubes at the edge level, where each k-cube links k switches to the upper level of the k-ary n-tree, while the remaining switches link to the compute nodes. Hence, all the cubes are capable of interconnecting k(2^k−k) compute nodes. Shortest path-based routing algorithms are proposed for these hybrid topologies, and several link fault tolerant routing algorithms are developed to enhance the fault tolerance of the entire topology. The proposed hybrid topologies are then evaluated in terms of path diversity, cost, and performance. The results demonstrates that the proposed KANTC and MiKANTC topologies exhibit improved performance, with up to 84% reduction in the number of switches and 78% reduction in links in large parallel systems when k = n = 8, compared to the conventional fat-tree topology. Additionally, these hybrid topologies display enhanced path diversity compared to traditional fat-tree.