Hierarchical Dual-Net: A Flexible Interconnection Network and Its Routing Algorithm
Yamin Li, Shietung Peng, Wanming Chu · 2011
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 (2N0)2k/(2×Πi=1ksi) nodes, where S = {si|1 ≤ i ≤ k} is the set of integers with each sirepresenting the number of nodes in a super-node at the level i for 1 ≤ i ≤ k, and N0is the number of nodes in the base network B. The node degree of HDN(B, k, S) is d0+ k, where d0is the node degree of the base network. The benefit of the HDN is that we can select suitable sito 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.