KMcube: the compound of Kautz digraph and Möbius cube

摘要

This paper introduces a novel interconnection network called KMcube (Kautz-Möbius cube). KMcube is a compound graph of a Kautz digraph and Möbius cubes. That is, it uses the Möbius 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 Möbius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topological properties of Möbius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communication. Additionally, KMcube provides other attractive properties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Möbius-like graphs with the similar diameter to a Möbius cube. Moreover, other hybrid graphs of Kautz digraph and Möbius cubes are proposed and compared.