Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm

Abstract

In this paper, we propose a flexible interconnection network, called hierarchical dual-net (HDN), with low node degree and short diameter for constructing a large scale of supercomputer. The HDN is constructed based on a symmetric product graph (base network). A k-level hierarchical dual-net, HDN(B,k,S), contains (2N₀)^2k/(2 × Π^k_i=1s_i) nodes, where S={G'₁,G'₂,...,G'_k}, G'_i is a super-node and s_i = |G'_i| is the number of nodes in the super-node at the level i for 1 ≤ i ≤ k, and N₀ is the number of nodes in the base network B. The node degree of HDN(B,k,S) is d₀+k, where d₀ is the node degree of the base network. The HDN structure is better than existing networks such as hypercube and 2D/3D torus with respect to the degree and diameter. Another benefit of the HDN is that we can select suitable super-nodes to control the growing speed of the number of nodes for constructing a supercomputer of the desired scale. We investigate the topological properties of the HDN and compare them to that of other networks and give efficient routing and broadcasting algorithms for the hierarchical dual-net.