Design of new routing algorithm and embedding for Hierarchical Hypercube Networks

Abstract

Mesh, hypercube, HHN, bubbls-sort, star, transposition, and macro-star graphs have been proposed as interconnection networks used in high-performance parallel computer structures. A hypercube expresses a node with n binary numbers, and has an edge between 1-bit other nodes. A hypercube is an excellent network from a graph-theoretic point of view, such as node symmetry, fault tolerance, recursive scalability, and Hamiltonian cycles. However, compared to the increase in the number of nodes, the number of edges increases proportionally, so the network cost is not good. The HHN graph was proposed as a network that improved the network cost by improving the disadvantages of the hypercube. HHN graph uses hypercube as a basic module. The HHN graph is a network that has improved network cost by designing it to have a hierarchical structure based on a hypercube. HHN graphs have a simple routing algorithm with fewer branches and fewer links than hypercubes. Although HHN's routing algorithm has a simple advantage, it has a disadvantage that the path length is long via unnecessary nodes. In this study, we propose a new routing algorithm that improves the path length of the HHN graph and analyze its efficiency. The improved routing algorithm proposed in this study has the result of improving the existing algorithm by 30% on average. In addition, we analyze the embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods for the embedding of hierarchical Hypercube networks in the hypercube to minimize the dilation and the expansion costs.

Keywords: interconnection network, parallel processing, routing algorithm, embedding algorithm, dilation analysis

DOI: 10.54941/ahfe1004204