Search

Summary: Fat‐tree is one of the most commonly used topologies in the interconnection networks of modern supercomputers and datacenters. In a traditional fat‐tree, k‐ary n‐tree for instance, the degree of root switches is less than that of other switches. Fat‐tree is a folded version of a Clos network. A Clos network uses the same degree switches in all stages. However, fat‐tree or Clos network has a high switch cost and great packet latency. This paper introduces a Mirrored K‐Ary N‐Tree (MiKANT) network and presents switch fault‐tolerant routing algorithms for it. Compared with k‐ary n‐trees and Clos networks, MiKANT connects more compute nodes with fewer switches and links so that it can be implemented at a lower hardware cost, it uses switches that have the same number of ports to keep the regularity, and it shortens the average distance to reduce the packet latency for achieving higher communication performance. We give three simple deadlock‐free switch fault‐tolerant routing algorithms for MiKANT and evaluate their performance. The simulation results show that the proposed algorithms achieve much higher performance than the shortest path routing algorithm. Although MiKANT uses fewer switches and links than fat‐tree, the simulation result shows that it has an almost the same successful routing ratio as the fat‐tree for the switch fault tolerance. [ABSTRACT FROM AUTHOR]

The recursive dual-net is a newly proposed interconnection network for massive parallel computers. The recursive dual-net is based on recursive dual-construction of a symmetric base network. A k-level dual-construction for k > 0 creates a network containing (2n0)2k/2 nodes with node-degree d0 + k, where n0 and d0 are the number of nodes and the node-degree of the base network, respectively. The recursive dual-net is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Disjoint-paths routing and fault-tolerant routing are fundamental and critical issues for the performance of an interconnection network. In this paper, we propose efficient algorithms for disjoint-paths and fault-tolerant routings on the recursive dual-net. [ABSTRACT FROM AUTHOR]

The hypercube, or n-cube, has been widely used as the interconnection network in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. This paper introduces a new interconnection network, namely dual-cube, for large-scale parallel computers and describes the algorithms for efficient collective communications in dual-cube. The dual-cube network mitigates the problem of increasing number of links in the large-scale hypercube network while retains hypercube’s topological properties. Design of efficient routing algorithms for collective communications is the key issue for any interconnection network. In this paper, we show that the collective communications can be done in dual-cube with almost the same communication times as in hypercube. [ABSTRACT FROM AUTHOR]