Woo-Young Kim, Hyeong Ok Lee (2023). Design of new routing algorithm and embedding for Hierarchical Hypercube Networks. In: Artificial Intelligence, Social Computing and Wearable Technologies. AHFE Open Access, vol. 113, pp. 316–321. https://doi.org/10.54941/ahfe1004204
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.
As the need for developing high-performance parallel computers increases day by day, research on interconnection networks that have an important impact on the performance of these parallel computers has also been actively conducted.
The interconnection network is represented by a non-directional graph representing each processor as a node and a communication channel as an edge between processors. The interconnection network proposed so far can be divided into a mash class expressed as k×n, a hypercube class expressed as 2ˆn, and a star graph class expressed as n. Measures for evaluating inter- connection networks include branching, connectivity, symmetry, diameter, average distance, fault diameter, network cost, broadcasting, embedding, etc.
The hypercube network has the advantages of symmetry in nodes and edges, and a simple recursive structure, making it easy to provide the net- work structure required in various applications. Thus, it is widely used in existing research and commercial systems. Moreover, from the perspective of embedding, there are advantages in that other network structures such as rings, trees, pyramids, and meshes can be efficiently embedded. However, there is a drawback in that the diameter and the average distance between nodes are not short compared to the branching factor. To overcome these
Design of New Routing Algorithm and Embedding for Hierarchical Hypercube Networks 317
problems, new networks such as Hypernet, HCN (Hierarchical Cubic Net- work), and HHN (Hierarchical Hypercube Networks) have been proposed, which improve the network of the hypercube from the perspective of network costs by manipulating the adjacency of nodes and edges.
The HNN (Hierarchical Hypercube Networks) is a graph proposed as a new topology for large-scale parallel computers. It is a hierarchical intercon- nection network based on the hypercube and has a smaller node branching factor and fewer links than a hypercube with a similar number of nodes. Therefore, it is an excellent interconnection network for composing large- scale parallel computers and is a superior network compared to the widely distributed hypercube for large-scale parallel systems. When setting up routing algorithms, it uses simple routing algorithms.
However, it is inefficient because it has many unnecessary routing paths by constructing a path based on the simple routing algorithm.
Therefore, in this paper, we propose a routing algorithm with an improved average distance compared to the simple routing algorithm. Although the worst-case path value is the same, the average distance value has improved as shown in <Table 3>.
Chapter 2 will discuss the structure and characteristics of the HHN net- work, Chapter 3 will discuss the problems with the HHN’s simple routing algorithm, Chapter 4 will present an improved routing algorithm for HHN, and finally, we will draw conclusions.
Related Research In HHN (Hierarchical Hypercube Networks), the edges that connect nodes within a hypercube, called a cluster, are referred to as internal edges, and the edges that connect between clusters are called external edges. Figure 1 shows the structure of the HHN, from the lowest level of the hypercube to the two-dimensional level of the HHN, in a hierarchical manner.
The definition of HHN(m:n,h) is as follows (m≤n): m: the number of clusters, 2ˆm n: nˆ-dimensional hypercube
Equation reproduced from the original PDF.
Each node is composed of
Equations and mathematical formulas are available in the original paper PDF.
binary digits, and the node address is denoted by (Ah, · · · , A1, A0). The number of nodes is 2m+nh, the branching factor is n + h, the number of edges is
n + h
2m+nh−1, the diameter is m + m
hn + h, and the average distance is m+nh
2 + h −
2 +1 2m −(h−1)( n 2+1) 2n Internal edges are formed by the definition of the hypercube, and external edges occur according to the following two conditions.
1. For 1 ≤ j < h, if Aj̸ = A0, then the node (· · · , Aj+1, Aj, Aj−1, · · · , A1, A0) is connected to the node
0 |Ah is the concatenation of the two numbers AH 0 H and Ah Simple Routing Algorithm and Problems of HHN
In HHN m : n, h
, let’s assume two arbitrary nodes as u=(Ah, · · · , A1, A0) and v=(Bh, · · · , B1, B0). The routing from node u to node v is as follows: If j < h, the path is
· · · , Aj+1, A0, Aj−1, · · · , A1, Aj
Equations and mathematical formulas are available in the original paper PDF.
Equation reproduced from the original PDF.
Ah, Ah−1, · · · , A1, A0
Ah, Ah−1, · · · , A1, AH
0 Bh
→
Ah, Ah−1, · · · , A1, AH
0 Ah
Here, →represents the internal routing path within the cluster, and →rep- resents the external routing path between clusters.
For instance, consider the routing path from u = (0010, 0100, 0011, 1001) to v = (0110, 0011, 1000, 0111) within HHN(4; 4, 3). The routing path based on the simple routing algorithm is as follows (the number next to →represents the number of bits during internal routing): (0010, 0100, 0011, 1001) →4 (0010, 0100, 0011. 0110) →(0110, 0100, 0011, 0010) →1(0110, 0100, 0011, 0011) →(0110, 0011, 0011, 0100) →2(0110. 0011, 0011, 1000) →(0110, 0011, 1000, 0011) →1(0110, 0011, 1000, 0111). So, examining the routing values, it involves eight internal routings and three external routings, making the total number of routings eleven. That is, there are eleven routing paths from node u to node v.
As seen in the above example, it’s suboptimal but simple routing algorithms were proposed that are adjusted according to the order of descending levels from the top-level (B_h) to the bottom level of the destination node v. Due to this simple routing algorithm, unnecessary routing path values are generated, and it fails to obtain optimal routing path values proportional to the smaller number of links compared to the hypercube. Therefore, an improved routing algorithm is proposed in the next chapter.
Improved Routing Algorithm for HHN Let’s assume two arbitrary u = (Ah, · · · , A1, A0) , v = (Bh, · · · , BL, B0). In this context, ⇒denotes the routing within the hypercube, →denotes the external link routing, and tuples represent each element constituting nodes u and v.
The improved routing algorithm determines the path according to the following three steps: Step 1: XOR(⊕) the corresponding values in the row and column, each made up of tuples, from nodes u and v in a matrix. Use the number of 1’s as an element of the matrix.
Step 2: Pair selection - Pair: Tuple values of the row and column of the selected element - p: The number of ⊕1s of the tuple values paired as matrix elements.
Design of New Routing Algorithm and Embedding for Hierarchical Hypercube Networks 319
- D (diagonal): The constituents of the matrix are diagonally as follows:
Equation reproduced from the original PDF.
- Ak: The tuple value at the highest level among the elements with the same value.
1. Find p = 0 among the constituents of D and select it as a pair. Remove the column and row containing the selected element.
2. Find p = 0 in all areas excluding D and select it as a pair. Remove the column and row containing the selected element. However, if there is a value of p = 0, select the value of Ak.
3. Add 1 to each value located on the diagonal D. 4. Select the smallest remaining value among the B0 column and remove its column and row. However, if there are the same values, select the value of Ak.
5. Select the smallest values in all areas other than the paired values, pair them in order, and remove their columns and rows, from column B0 to Bh. If there are the same values among the given column values, select the value of Ak.
6. After all are selected as pairs, subtract 1 added to the diagonal D, and start routing as in step 3.
Step 3: Routing - Start routing from A_0 of the start node u in the order of pairing as follows: if A_0 is paired in the order as follows, it routes. else if p = 0 for the value of diagonal D, it does not route because it’s the same position.
else if A_0 is paired with P = 0 and is not diagonal D, it routes internally(⇒) to the given value of column B_x paired with A_0 and externally(→) to the same level value, and swaps it. However, if that value is the lowest level value (B_0) of node v, it exchanges it with the upper level value of A_0, which has not been routed among node u, externally(→).
The process continues to repeat until it reaches the destination node v. For example, when considering the routing path from u=(0010, 0100, 0011, 1001) to v=(010, 0011, 1000, 0111) in HHN(4;4,3), the process from step 1 to step 2 by the improved routing algorithm proposed in this paper is shown in Table 1. In addition, the part marked with the point (.) relatively shows the state selected between nodes by a simple routing algorithm The process of the routing path by step 3 is as follows. (The number next to ⇒refers to the number of bits for internal routing.).
(0010, 0100, 0011, 1001) ⇒1 (0010, 0100, 0011, 1000) →( 0010, 0100, 1000, 0011) →(0010, 0011, 1000, 0100) ⇒1 (0010, 0011, 1000, 0110) →(0110, 0011, 1000, 0010) ⇒2 (0110, 0011, 1000, 0111) Therefore, if you look at the route value, the total number of internal rout- ing 4 times and external routing 3 times is 7. In other words, the number of routing path values from the u node to the v node was reduced by 4 times, and the routing path value of about 36% was improved.
320 Kim and Lee
Table 1. Process of steps1 and 2 of improved i.
Table available in the original PDF paper.
⊕
0110 0011 1000 0111
0010 1. 2 2
0100 1 2. 2
0011 2 0 1.
1001 4. 2 1
Table 2 shows the comparison of the routing result values of the two algo- rithms for two nodes u=(0100, 0100, 0011, 1001) and v=(010, 0011, 1000, 0111).
Table 2. Comparison of path values of two algorithms in a given examplei.
Table available in the original PDF paper.
Sortation Simple Routing Algorithm
Improved routing algorithms ex Internal Routing Value 8 4 External Routing Value 3 3 Total routing path value 11 7(36%)
In the worst case, for example, when routing to nodes u = (1111, 1111, 1111, 1111) and v = (0000, 0000, 0000, 0000, 0000), both routing algo- rithms show a total of 19 routing times, with 16 internal routes and 3 external routes also, HHN (2;2;2), HHN (3;3;2), HHN (4;4;3), Table 3 shows the results of comparing the average path value of the improved routing algo- rithm to the path value of the simple routing algorithm for any two nodes in HHN (5;5;4).
However, HHN (2;2;2) and HHN (3;3;2) referenced all values of node v after fixing one value of node u due to too many cases, and HHN (5;5;4) was extracted from one value of node u by 1/100 of the number of node v, 355,554).
Table 3. Comparison of path values of algorithms in HHN (2;2;2), HHN (3;3;2), HHN (4;4;3), and HHN (5;5;4)i.
Table available in the original PDF paper.
Sortation Simple Routing Algorithm Improved routing algorithms average distance average distance Improvement value
Therefore, as shown in Table 3, comparing the routing path values of the simple routing algorithm and the improved routing algorithm shows that the
Design of New Routing Algorithm and Embedding for Hierarchical Hypercube Networks 321
improved routing algorithm of this paper improves the average distance value by 32% in the case of HHN(3;3;2) compared to the simple routing algorithm.
CONCLUSION
The HHN(m;n;h) graph is a hierarchical interconnection network based on a hypercube, and it is an interconnection network that constitutes a large- scale parallel computer because it has smaller node branches and smaller links than a similar hypercube. Therefore, in this paper, a new routing algorithm is proposed as an improvement over a simple routing algorithm.
When comparing the improved routing algorithm and the simple routing algorithm proposed in this paper, the average distance value of the simple routing algorithm is the same in the worst case, but in the case of HHN(3;3;2), the average distance value of the improved routing algorithm is improved by 32% to 4. A future research challenge is to find the optimal routing algorithm.
ACKNOWLEDGMENT
This research was funded by National Research Foundation of KOREA(NRF) grant funded by the Korea government(MSIT) (No. 2020R1A2C1012363).
MIST: Ministry of Science and ICT (Corresponding Author: Hyeong Ok Lee).
REFERENCES
K. Ghose and K. R. Desai “Hierarchical Cubic Networks.” IEEE Trans. Parallel Distributed syst, Vol. 6 No. 4, pp. 427–435, 1995. K. Hwang, and J. Ghosh, “Hypernet: A communication efficient architecture
for constructing massively parallel computers.” IEEE Trans. Comput. C-36 12 (Dec. 1987), 1450–1466. F. T. Leighton, Introduction to Parallel Algorithms and Architectures; Arrays, Hypercubes, Morgan Kaufmann Publishers, 1992. V. E. Mendia nad D. Sarkar, “Optimal Broadcasting on the Star Graph,” IEEE Trans,
Parallel Distributed syst, Vol. 3, No. 4, pp. 389–396, 1992. Sang Kyun Yun and Kye Ho Park, Hierarchical Hypercube Networks (HHN) for Massively parallel Computers. Journal of Parallel and Distributed Computin 37, 194_199(1996) article no. 0119. H. Lee, M. Kang, D. Kim, D. Seo and Y. Li, “Epidemic Vulnerability Index for
Effective Vaccine Distribution against Pandemic,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2022. H. Lee and D. Seo, “FedLC: Optimizing Federated Learning in Non-IID Data via Label-Wise Clustering,” IEEE Access, Vol. 11, pp. 42082–42095, 2023.
LISTED IN THE AHFE DIGITAL BOOKSTORE CATALOGUE
Explore the complete digital volume
Artificial Intelligence, Social Computing and Wearable Technologies
Read this individual research paper free through the original publisher, or explore the full digital proceedings book.
ISBN 978-1-958651-89-6
Explore this ISBN in the AHFE Bookstore ↗Listed in the July 2026 bookstore catalogue; search by ISBN to confirm current availability · Digital book purchase optional