The number of Internet-connected devices grows very rapidly, with even fears of running out of available IP addresses. It is clear that the number of sensors follows this trend, thus inducing large sensor networks. It is insightful to make the comparison with the huge number of processors of modern supercomputers. In such large networks, the problem of node faults necessarily arises, with faults often happening in clusters. The tolerance to faults, and especially cluster faults, is thus critical. Furthermore, thanks to its advantageous topological properties, the torus interconnection network has been adopted by the major supercomputer manufacturers of the recent years, thus proving its applicability. Acknowledging and embracing these two technological and industrial aspects, we propose in this paper a node-to-node routing algorithm in an $n$ -dimensional $k$ -ary torus that is tolerant to faults. Not only is this algorithm tolerant to faulty nodes, it also tolerates faulty node clusters. The described algorithm selects a fault-free path of length at most $n(2k+\lfloor k/2\rfloor -2)$ with an $O\left(n^2{k}^2\right|F\left|\right)$ worst-case time complexity with $F$ the set of faulty nodes induced by the faulty clusters.

Supercomputers are today made up of hundreds of thousands of nodes. The interconnection network is responsible for connecting all these nodes to each other. Different interconnection networks have been proposed; high performance topologies have been introduced as a replacement for the conventional topologies of recent decades. A high order, a low degree and a small diameter are the usual properties aimed for by such topologies. However, this is not sufficient to lead to actual hardware implementations. Network scalability and topology simplicity are two critical parameters, and they are two of the reasons why modern supercomputers are often based on torus interconnection networks (e.g., Fujitsu K, IBM Sequoia). In this paper we first describe a new topology, torus-connected cycles (TCCs), realizing a combination of a torus and a ring, thus retaining interesting properties of torus networks in addition to those of hierarchical interconnection networks (HINs). Then, we formally establish the diameter of a TCC, and deduce a point-to-point routing algorithm. Next, we propose routing algorithms solving the Hamiltonian cycle problem, and, in a two dimensional TCC, the Hamiltonian path one. Correctness and complexities are formally proved. The proposed algorithms are time-optimal.

Modern supercomputers include hundreds of thousands of processors and they are thus massively parallel systems. The interconnection network of a system is in charge of mutually connecting these processors. Recently, the torus has become a very popular interconnection network topology. For example, the Fujitsu K, IBM Blue Gene/L, IBM Blue Gene/P, and Cray Titan supercomputers all rely on this topology. The pairwise disjoint-path routing problem in a torus network is addressed in this paper. This fundamental problem consists of the selection of mutually vertex disjoint paths between given vertex pairs. Proposing a solution to this problem has critical implications, such as increased system dependability and more efficient data transfers, and provides concrete implementation of green and sustainable computing as well as security, privacy, and trust, for instance, for the Internet of Things (IoT). Then, the correctness and complexities of the proposed routing algorithm are formally established. Precisely, in an n-dimensional k-ary torus ( $n<k$ , $k\ge 5$ ), the proposed algorithm connects c ( $c\le n$ ) vertex pairs with mutually vertex-disjoint paths of lengths at most $2k(c-1)+n\lfloor k/2\rfloor$ , and the worst-case time complexity of the algorithm is $O\left(n{c}^4\right)$ . Finally, empirical evaluation of the proposed algorithm is conducted in order to inspect its practical behavior.

Modern supercomputers are massively parallel systems: they embody thousands of computing nodes and sometimes several millions. The torus topology has proven very popular for the interconnect of these high‐performance systems. Notably, this network topology is employed by the supercomputer ranked number one in the world as of November 2020, the supercomputer Fugaku. Given the high number of compute nodes in such systems, efficient parallel processing is critical to maximise the computing performance. It is well known that cycles harm the parallel processing capacity of systems: for instance, deadlocks and starvations are two notorious issues of parallel computing that are directly linked to the presence of cycles. Hence, network decycling is an important issue, and it has been extensively discussed in the literature. We describe in this paper a decycling algorithm for the 3‐dimensional k‐ary torus topology and compare it with established results, both theoretically and experimentally. (This paper is a revised version of Antoine Bossard (2020)).

Recent supercomputers embody hundreds of thousands of compute nodes, and sometimes millions; as such, they are massively parallel systems. Node interconnection is thus critical to maximise the computing performance, and the torus topology has come out as a popular solution to this crucial issue. This is the case, for example, for the interconnection network of the Fujitsu Fugaku, which was ranked world no. 1 until May 2022 and is the world no. 2 at the time of the writing of this article. Here, the number of dimensions used by the network topology of such torus-based interconnects stays rather low: it is equal to three for the Fujitsu Fugaku’s interconnect. As a result, it is necessary to greatly increase the arity of the underlying torus topology to be able to connect the numerous compute nodes involved, and this is eventually at the cost of a higher network diameter. Aiming at avoiding such a dramatic diameter rise, topologies can also combine several layers: such interconnects are called hierarchical interconnection networks (HIN). We propose, in this paper, which extends an earlier study, a novel interconnect topology for massively parallel systems, torus-connected toroids (TCT), whose advantage compared to existing topologies is that while it retains the torus topology for its desirable properties, the TCT network topology combines it with an additional layer, toroids, in order to significantly lower the network diameter. We both theoretically and empirically evaluate our proposal and quantitatively compare it to conventional approaches, which the TCT topology is shown to supersede.