Mapping between Petersen Star Network and Hierarchical Petersen Network: Hierarchical Network Embedding

Abstract

The demand for big data in data science and deep learning has been constantly increasing in recent years. In particular, deep learning using big data requires a high-performance computer. Interconnection networks for the design of high-performance computers are being consistently researched. The Petersen star network (PSN) and hierarchical Petersen network (HPN) are hierarchical interconnection networks (HINs) designed based on the Petersen graph and a small network cost. PSN(n) has 10n nodes and n+2 degrees, whereas HPN has 10n nodes and a degree of 5. When graph G is embedded in graph H, the algorithm developed in G can be simulated or reused in H. The evaluation measures for embedding include expansion, dilation, and congestion. First, previous studies on embedding are investigated and summarized. Second, the node and edge mapping functions between the two graphs are proposed. According to the proposed functions, it is shown that HPN(n) can be embedded into PSN(n) with an expansion of 1, dilation of n?1, congestion of 1, average dilation of 0.4n, and average congestion of 1. Furthermore, it is shown that PSN(n) can be embedded into HPN(n) with an expansion of 1, a dilation of n+4, a congestion of 0.5n, an average dilation of 0.5n, and an average congestion of 0.5n. The results of this study can be extended to prove the upper and lower limits of dilation and congestion with respect to the network characteristics.