Design and analysis of the Dual-Torus Network

Abstract

In this paper, we propose a new topology called the Dual Torus Network (DTN) which is constructed by adding interleaved edges to a torus. The DTN has many advantages over meshes and tori such as better extendibility, smaller diameter, higher bisection width, and robust link connectivity. The most important property of the DTN is that it can be partitioned into sub-tori of different sizes. This is not possible for mesh and torus-based systems. The DTN is investigated with respect to allocation, embedding, and fault-tolerant embedding. It is shown that the sub-torus allocation problem in the DTN reduces to the sub-mesh allocation problem in the torus. With respect to embedding, it is shown that a topology that can be embedded into a mesh with dilation delta can also be embedded into the DTN with less dilation. In fault-tolerant embedding, a fault-tolerant embedding method based on rotation, column insertion, and column skip is proposed. This method can embed any rectangular grid into its optimal square DTN when the number of faulty nodes is fewer than the number of unused nodes. In conclusion, the DTN is a scalable topology well-suited for massively parallel computation.