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

In this paper, we propose a flexible interconnection network, called hierarchical dual-net (HDN), with low node degree and short diameter for constructing a supercomputer of large scale. 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×Π_i=1^k s_i) nodes, where S = {s_i|1 ≤ i ≤ k} is the set of integers with each s_i representing the number of nodes in a 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 benefit of the HDN is that we can select suitable s_i 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.