This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and con...This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and connects many such clusters by means of a Kautz digraph at the cost of only one additional arc being added to any node in each Mobius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topo- logical properties of Mobius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communi- cation. Additionally, KMcube provides other attractive prop- erties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Mobius-like graphs with the similar diameter to a Mobius cube. Moreover, other hybrid graphs of Kautz digraph and Mobius cubes are proposed and compared.展开更多
基金This work was partially supported by the National Natural Science Foundation of China （Grant Nos. 61170284, 60903206, 61070216, and 71071160）, the China Postdoctoral Science Foundation （20100480898 and 201104439）, the Science Study Foundation of Doctorial Subject for High Schools （20114307110011）, the Hunan Provincial Innova- tion Foundation for Postgraduate （CX2010B022）, and the NUDT Innovation Foundation for Postgraduate （B100501）.
文摘This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and connects many such clusters by means of a Kautz digraph at the cost of only one additional arc being added to any node in each Mobius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topo- logical properties of Mobius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communi- cation. Additionally, KMcube provides other attractive prop- erties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Mobius-like graphs with the similar diameter to a Mobius cube. Moreover, other hybrid graphs of Kautz digraph and Mobius cubes are proposed and compared.
