Bo-Ok Seong, Jimin Ahn, Myeongjun Son, Hyeongok Lee (2022). Three-degree graph and design of an optimal routing algorithm. In: Artificial Intelligence and Social Computing. AHFE Open Access, vol. 28, pp. 221–229. https://doi.org/10.54941/ahfe1001466
Learning, as well as the importance of a high-performance computer is significantly emerging. In parallel computing, we denote the concept of interconnection between the single memory and multiple processors as multi-processor. In a similar context, multi-computing signifies the connection of memory-loaded processors through the communication link. The relationship between the performance of multi-computing and the processor’s linkage structure is extremely proximate. Let the connection structure of the processor be an interconnection network. The interconnection network can be modeled through a classical graph consisting of node and edge. In this regard, a multi-computing processor is expressed as a node, communication link as an edge. When categorizing the suggested interconnection network through the criteria of the number of nodes, it can be classified as follows: Mesh class type consisted of the n×k nodes (Torus, Toroidal mesh, Diagonal mesh, Honeycomb mesh), Hypercube class type with 2^n nodes (Hypercube, Folded hypercube, Twisted cube, de Breijin), and Star graph class type (Star graph, Bubblesort star, Alternating group, Macro-star, Transposition) with n! nodes. The mesh type structure is a planar graph that is widely being utilized in the domains such as VLSI circuit design and base station installing (covering) problems in a mobile communication network. Mesh class types are comparatively easier to design and could potentially be implemented in algorithmic domains in a practical manner. Therefore, it is considered as a classical measure that is extensively preferred when designing a parallel computing network system. This study suggests the novel mesh structure De3 with the degree of three and designs an optimal routing algorithm as well as a parallel route algorithm (병렬경로알고리즘) based on the diameter analysis. The address of the node in the De3 graph is expressed with n-bit binary digits, and the edge is noted with the operator %. We built the interval function (구간 함수) that computes the locational property of the corresponding nodes to derive an optimal routing path from node u to node v among the De3 graph structure. We represent the optimal routing algorithm based on the interval function, calculating and validating the diameter of the De3 graph. Furthermore, we propose the algorithm that establishes the node disjoint parallel path which addresses a non-overlap path from node u to v. The outcome of this study proposes a novel interconnection network structure that is applicable in the routing algorithm optimization by limiting the communication links to three while the number of nodes These results implicate the viable operation among the high-performance edge computing system in a cost-efficient and effective manner.
In recent years, with the explosive growth of data volumes due to the deve- lopment of IT technology, the number of high-performance computers is increasing due to escalating demands in diverse domains such as Big data analysis and artificial intelligence technology. Likewise, high-performance computer technology that operates multiple processing devices is also expan- ding, including attempts to increase the efficiency of CPU-centered processing units, GPU, and many-core processors. High-performance computers are evolving throughout the rapidly changing era, offering satisfaction to new market demands and diverse requirements on application domains.
A parallel computer is a computer system that subdivides a given job into multiple tasks and processes the corresponding task by allocating them to hardware resources (e.g., multiple cores) in a parallel fashion. Parallel com- puters are mainly divided into shared-memory multiprocessors and message passing computers. In a shared-memory multiprocessor system, the memory system directly affects the overall performance. The critical attribute of the message passing computer is the interconnection network, which refers to the connection structure between processors considering the locational pro- perty, which is one of the factors that determine the performance of a parallel processing system. Therefore, research on interconnection networks is con- sidered fundamental in order to improve the performance and control the execution of parallel processing computers.
The network cost is a widely implemented metric to quantitatively assess the interconnection network, mathematically defined as a multiplication between the degree and the diameter where degree refers to the hardware cost and diameter denotes the software cost. In order to construct an efficient
network structure with the minimum usage of network cost, the cardinality of both the degree and diameter should be reduced. However, the relationship between the degree and diameter shows a negative correlation, and this trade- off hinders the achievement of decreasing the network cost in a harmonious manner.
The Shortest Path problem refers to a problem of finding an optimal route in which the sum of weights of edges leads to the minimum value that con- nects the node u to node v in the network G where (n, v) ∈G. The edge weight is the value of the edge connecting the existing nodes and could be both positive to negative numerical values. This concept offers a numerical representation of resources and factors that evaluate the network (e.g., cost, distance, time, etc.), which can have positive or negative values. The shortest path problem in a weighted graph (i.e., edges denoted with weights) computes the shortest path that reaches the destination node v from the initial starting node u. Diverse research was conducted to effectively locate the shortest path concerning this problem. In this paper, we propose a novel degree graph CGn that presents a degree of three. We analyze the theoretical properties of this graph structure and the shortest path algorithm with respect to the parallel routing algorithmic perspective. Our n-dimensional CGn indicates the node address through n-bit binary, having a degree of three, 2n number of nodes, and 2n−2 diameter.
This paper is organized as follows. Section 2 explores the interconnection network and the types of constant-degree graphs. In section 3, we define the novel interconnection network CGn and analyze theoretical properties of the suggested graph and its degree, followed by presenting the routing algorithm. Finally, we conclude our works in section 4.
Related Works In a multiprocessor system, a multiprocessor interconnection network is defi- ned as the network connection to support communication between each existing processor that composes the target system. An interconnection netw- ork can be represented as an undirected graph, with each processor as a node and the communication channels between the processors as edges. If a chan- nel exists between two processors, an edge is placed between those entities. An edge is an undirected edge that can transmit data in both directions. The interconnection network of parallel computers is represented as G = (V, E) by an undirected graph G. V(G) is a set of nodes inside the graph G, that is, V (G) = {0, 1, 2, · · · , N −1}, and E(G) is a set of edges composing the G. The edge e(v, w) ∈E (G) is an arbitrary connection between the nodes v and w where (v, w) ∈V (G), and the necessary and sufficient condition for the existence of e(v, w) is a communication channel between the nodes v and w. A network with a relatively small diameter compared to the number of nodes have a short distance between nodes, but it becomes arduous to design the hard components as the number of nodes escalates.
Constant Degree Graph The interconnection networks can be classified into the following three types based on the number of nodes: mesh type with n(V(G)) = k×n, a hypercube
Three-Degree Graph and Design of an Optimal Routing Algorithm 223
Table 1. Constant degree graph’.
Table available in the original PDF paper.
Number of Nodes Degree Diameter Network Cost Interconnection Network Mesh k × n 4 2√n O(8√n) Honeycomb 6t2 3 1.63√n O(4.9√n) Torus k × n 4 √n O(4√n) SEPn n! 3 1 8(9n2 −22n + 24) O( 27
8 n2) NSEPn n! 4 2 3n2 −3 2n + 1 O( 8
3n2) CGn 2n 3 2n−2 O(3 × 2n−2 )
type with nV(G)) = 2n, and a star graph type with nV(G)) = n!. The mesh type is a well-known graph structure that has been widely utilized as a planar graph, which has been commercialized in various systems.
The m-dimensional mesh Mm(N) consists of nV(G)) = Nm and n (E (G)) = mNm −mNm−1. The address of each node is expressed with an m-dimensional vector, and when the addresses of any two nodes dif- fer by 1 in one dimension, there is an edge between them. The advantage of Low-dimensional meshes is that they are straightforward to design, it is considered a promising scheme that has been widely implemented to spe- cifically designs the network topology for parallel processing computers. Higher-dimensional meshes have smaller diameters and larger bipartite wid- ths. In addition, they tend to perform the parallel algorithms with rapid pace, but requires a high cost. Hexagonal Mesh, Toroidal Mesh, Diagonal Mesh, Honeycomb Mesh, and Torus are proposed as an alternative structure that shows to have improved general lattice-structured mesh diameter. Fur- thermore, the Shuffle-Exchange Permutation (SEP) was asserted based on permutation groups, which has the advantage of easy conductivity of graph- based simulation (e.g., Cayley graph). SEP enables to efficiently operate the algorithm with minimal transitions in given new graphs, also is a regular network with a degree of three. Moreover, an NSEP (New-SEP) with a degree of four with enhanced SEP diameter and network cost have been proposed.
CGn GRAPH DESIGN AND ANALYSIS The Graph is formulated based on the Vertex (Node) and Edge. Let node of graph CGn be S, where the node is expressed with binary n-bit, and the total number of node n S
∀i Si) = 2n. The address of the node S in the CGn graph is as follows.
S = (Sn Sn−1 Sn−2 ...Si...S3 S2 S1), 1 ≤i ≤n, i∈N Definition 1. The three edge types connecting to node S constituting the n- dimensional CGn graph are as follows.
1. Increasing Edge (Ef): Connect a node that is 1 bit higher from the address of the node S.
{(S + 1) + 2n } % 2n
2. Decreasing Edge (Eb): Connect a node that is 1 bit lesser from the address of the node S.
{(S −1) + 2n } % 2n
3. Complement Edge (Ec): Connect a node that is a complement node of the most significant bit Sn from the address of the node S.
(S + 2n−1) % 2n
Example 1. In the n-dimensional CGn graph, when n = 4, the connection relationship of nodes is as follows.
In G, n (V (G))= 24 with E (v∀i) = 3. If the node S is 1 (=0001(2)) where x(2) denotes the binary with x ∈{0, 1}, we substitute a decimal value accor- ding to the graph definition, which leads Ef to direct 2 (=0010(2)) and Eb to 0 (= 0000(2)). The final branch (Ec) points to 9 (=1001(2)) in which only the leftmost bit is complemented, and this operation is applied equally to all nodes, and the graph of 24 has the form as shown in Figure 1.
Definition 2. In CGn, a cycle of length 2n consisting only of increasing or decreasing edges is nominated as Hn cycle.
Example 2. When n = 3, the H3 cycle is a subgraph that has the length is 8 ([Fig. 2]).
A cycle that includes all vertices in the connected graph G is called a Hamil- tonian cycle. If the network has a Hamilton pass or a Hamilton cycle, a ring or a linear array can be easily implemented, thus it is used as a pipeline for parallel processing. Theorem 1 shows that the internal CGn network has a Hamiltonian cycle.
Theorem 1. CGn contains the Hamilton cycle.
Proof) Let S be an arbitrary node. By definition 2, there is always a cycle starting from S and returning to S by repeating increment or decrement operations. Therefore, CGn has a Hamiltonian cycle.
Theorem 2. CGn is a symmetric graph.
Proof) A symmetrical relationship proves a one-to-one relationship betw- een adjacent nodes of each existing node when mapping two arbitrary nodes. Let U be an arbitrary departure node and V be a destination node (0 ≤ U, V ≤2n, U̸ = V). By definition 2, arbitrary two nodes of CGn can be reached via increasing or decreasing edges. Therefore, U and V have the following relationship.
Equation reproduced from the original PDF.
The adjacent nodes of node U and V are {U + 1, U −1, (U + 2n) %2n}, {V + 1, V −1, (V + 2n) %2n} respectively. When mapping U to V, the nei- ghbor node is {(U + α) + 1, (U + α) −1, ((U + α) + 2n) %2n}, and for U + α = V, we conclude that {V + 1, V −1, (V + 2n) %2n}. Therefore CGn is a symmetric graph.
Three-Degree Graph and Design of an Optimal Routing Algorithm 225
Figure 1: CG4 Graph.Figure 2: H3 cycle.
Routing Algorithm Routing is the process of efficiently and quickly determining the route of two points among one or multiple networks. We can obtain an effective solution to Routing problems in diverse domains via network techniques. A path is a route from one node to another through the edge of the graph. A practi- cal routing algorithm should locate an optimal path, simultaneously simple. We introduce the routing algorithm and parallel path of the CGn. Moreover, we prove the shortest path through the routing algorithm and parallel path algorithm.
Definition 3. D’s location represents the set of destination nodes within the range when the starting node u is 0.
Our ultimate objective is to compute the optimal length, and the prelimi- nary step is to determine the range where the destination node is located. Our approach is to divide the graph into two sections, and in the correspon- ding section, we compute the optimal length. Let the initial starting node is u, and we subdivide the section range of destination node v into Section A and Section B. Note that this study only divides and analyzes the right side of the graph while the routing algorithm is being processed.
Section A: 0 < D
′s location < 2n−2 + 1 Section B: 2n−2 < D
′s location < 2n−1 + 1
Example 3. In a graph where n is 3, the nodes in parentheses (001, 111), (010, 110), (011, 101) have the identical number of edges used to arrive at
Table 2. Notation definition.
Table available in the original PDF paper.
Notation Definition S Starting node (Initial node) D Destination node Goal Destination node RN Current node FD, FD_s Verify whether functions move_f() and move_b() were previously applied D′ 2n −D (D > 2n−1) move_f(a) Apply edge Ef, Shift status by ((a + 1) + 2n) %2n
move_b(a) Apply edge Eb, Shift status by ((a −1) + 2n) %2n a + 2n−1 %2n move_c(a) Apply edge Ec, Shift status by
the optimal length from the start node to the destination node when the initial node is 0.
(001, 111): n (E (001, 111)) = 1, (010, 110): n (E (010, 110)) = 2, (011, 101): n (E (011, 101)) = 3 The main reason for this is that the graph is symmetric by definition. That is, when obtaining the optimal length with (010) as the target node, the length of the edges leading to (110) enables the successful path.
Theorem 3. Let D be an arbitrary destination node of CGn. The optimal length can be obtained through D′ that satisfies D + D′ = 2n.
Proof) Let D be an arbitrary destination node of CGn. With the formula: D′ = 2n −D, a node D′ is being used as the destination node. The range is divided into two, and the operation selected first differs depending on the section in Sections A and B. Suppose the node belonging to Section A is the destination node. In that case, the increment operation is optimal, and if the node belonging to Section B is the destination node, the decrement operation is preferred. We verify this assertion through the routing algorithm.
Example 4. When n = 4, Section A, B is defined as follows.
Section A: Since it is a set of nodes greater than 0 and less than 2n−2 + 1, it has a value of {1, 2, 3, 4} in decimal.
Section B: Since it is a set of vertices greater than 2n−2 and less than 2n−2 + 1, it has a value of {5, 6, 7, 8} in decimal.
Definition 4. The terms used in the routing algorithm are defined as follows.
Example 5. When n = 5, if the initial node is 0 and the destination node is 1, the path is as follows.
Equation reproduced from the original PDF.
Increment operation is conducted until it reaches the destination node since the destination node is an element of Section A.
0 →1
Three-Degree Graph and Design of an Optimal Routing Algorithm 227 Algorithm 1. Routing Algorithm g g g Input: Starting node S, Destination node D Output: int RN Node move_f(node RN)
Node move_f(node RN) return (𝑅𝑁+ 2ିଵ)%2 1 Initialize int RN ←S, int (FD, FD_s) ←0, int goal ←D 2 if (𝐷< 2ିଵ) then 3 FD ←1 4 else 5 FD_s ←1, 𝐷ᇱ←2−𝐷 6 𝐷←𝐷ᇱ
Example 6. When n = 5, if the initial node is 30 and the destination node is 15, the path is as follows.
Since destination node 30 is larger than 2n, it utilizes the value of D
′.
D
Equation reproduced from the original PDF.
Since D
′ is affiliated in Section A, it conducts decreasing operations until it reaches the destination node.
3 →2 →1 →0 →32 →31 →30
Example 7. When n = 5, if the initial node is 30 and the destination node is 15, the path is as follows.
Since destination node 15 is smaller than 2n and affiliated in Section B, it conducts the incremental operation after the complement operation.
30 →14 →15
Optimal Length In this section, we mathematically prove the formula that computes the Opti- mal Routing Path Length. In a graph with n bits, the optimal length from the single starting node S to the destination node D when the section is divided into two subparts according to the routing algorithm is as follows.
D or D Section A:
′
S − Section B: |C (S) −(D or D ′)|
In Fig. 1, we assume that the starting node S is 0 and the destination node D is 15. According to the formula D
Equation reproduced from the original PDF.
′ becomes 1, and it is affiliated in Section A. Therefore, substituting (0-1), the absolute value is 1, which leads to the optimal length is also 1.
Theorem 4. The diameter of CGn is 2n−2.
Proof) According to Theorem 4, the distance is equivalent when the initial node is 0, and the destination node is 2n. Note that the case of less than 2n was divided into Section A and Section B. Since there is an edge Ec connecting the 2n−1 nodes with the farthest distance on the cycle Hn, the node with the farthest distance from node 0 is 2n−2 and 2n−1 in Section B. According to the algorithm, the 2n−2 applies the edge Ef and 2n−1 implements the edge Eb, followed by utilizing Eb to reach the destination node. In this case, the distance to 2n−2 and 2n−1 is equivalent to 2n−2. Therefore, the diameter of CGn is 2n−2.
Example 8. When n = 5, let the initial node is 0, and the destination node is 7.
Since destination node 7 is associated with Section A, only increment operation is performed to reach the destination node.
0 →1 →2 →3 →4 →5 →6 →7 Therefore, the diameter of CG5 is 8.
CONCLUSION
In this paper, we proposed an interconnection network structure with a con- stant degree of three and analyzed its theoretical property. We defined the novel three-constant degree graph CGn , also proposed the shortest path rou- ting algorithm in propounded CGn . The n-dimensional CGn proposed in this paper represents a node address with n bits of a binary number, with a numerical degree of three, the 2n number of nodes, and a diameter of 2n−2. We show that the Hamilton cycle exists in internal CGn , also has a maxi- mum fault-tolerance. This novel graph topology and its property offer the viability of future implementation of a parallel processor system to enable high-performance computing operations, as well as providing insights and a reference to be applied in a real-world network system.
Three-Degree Graph and Design of an Optimal Routing Algorithm 229
ACKNOWLEDGMENT
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government (MSIT) (No. 2020R1A2C1012363).
REFERENCES
Adve. V. S, Vernon. M. K. Performance analysis of mesh interconnection networks with deterministic routing. IEEE Transactions on Parallel and Distributed Systems. 5(3). 225-246. 1994. Akers. S. B, Krishnamurthy. B. A group-theoretic model for symmetric interconne-
ction networks. IEEE transactions on Computers 38(4). 555–566. 1989. B. O. Seong, NSEP interconnection network improving the network cost of SEP, Korea, The graduate school sunchon national univ, (2021) Bokka. V. H, Gurla. S. Olariu and J. L. Schwing. Podality-based time-optimal com-
putations on enhanced meshes. IEEE Trans. Parallel and Distributed Systems. Vol 8. No. 10. 1019-1035. October 1997. Bondy. J. A., Murty. U. S. R. Graph Theory with applications, 5th Printing. American Elsevier Publishing Co., Inc. 1982. Chen. J. L, Shin. K. G. Addressing, routing, and broadcasting in hexagonal mesh
multiprocessors. IEEE trans. comput. 39(1). 10-18. Jan. 1990. D. Culler, J. Singh, A. Gupta, Parallel computer architecture-a hardware/software approach. 1999. Feng. T-Y. A survey of interconnection networks. IEEE computer. 12–27. 1981. G. Bell, Ultracomputers: A terafop before its time. Communications of the ACM.
27-47. 1992. Harary. F. Graph theory. Reading: Addison-Wesley. Massachusetts. 1969. J. H. Seo. Petersen-Torus interconnection network based on Petersen graph. Korea.
The graduate school sunchon national univ. 2008. Kwak, J. W. Ban, H. J. Jhon. C. S. Torus ring: improving performance of interconnection networks by modifying hierarchical ring. 32(5, 6). 196–208. 2005. Lakshmivarahan. S., J-S Jwo., Dhall. S. K. Symmetry in interconnection networks
based on cayley graphs of permutation groups: a survey. Parallel Computing. Vol. 19. 361–407. 1993. Leighton. F. T. Introduction to parallel algorithms and architectures: arrays, hypercubes. Morgan Kaufmann Publishers. 1992 Latifi, S., Srimani, P. K. A new fixed degree regular network for parallel processing.
IEEE Computer Society Press. 152–159. 1996. N-G. Kim. A study on the development of the composite measures of highperformance computer technology. Sungkyunkwan University. 2020. Parhami. B., Rakov. M. Perfect difference networks and related interconnection
structures for parallel and distributed systems. IEEE transactions on parallel and distributed systems. 16(8). 714–724. 2005. Robin, J. W., John, J. W. Graphs an ictroductory approach. Sons. USA. 1990 Sharma, P., Khurana, N. Study of optimal path finding techniques. International Journal of Advancements in Technology. 4(2). 2013. Tolkien, J. R., Medhi, D., Ramasamy, K. Networking and network routing: an
introduction. San Francisco: Elsevier. 2007.
LISTED IN THE AHFE DIGITAL BOOKSTORE CATALOGUE
Explore the complete digital volume
Artificial Intelligence and Social Computing
Read this individual research paper free through the original publisher, or explore the full digital proceedings book.
ISBN 978-1-958651-04-9
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