Full Binary Tree-Based Fixed Degree Graph Design and Parallel Algorithm - Bo Ok Seong; Jin-Hyeok Jang; Hyeong Ok Lee (IEEE Access, 2023)
Interconnection network is a network that connects processors and is an important factor in determining the performance of a parallel processing system. One measure of interconnection network evaluation is network cost, defined as degree $* $ diameter. The interconnection networks proposed so far can be classified into mesh, hypercube, and star graph types based on the number of nodes. The interconnection network $Tree-baseGraph(TG_{n})$ proposed in this study is a graph based on a full binary tree with a fixed degree of three, and the node address is expressed using n binary numbers. In this study, routing algorithms, Hamiltonian cycle, node disjoint parallel path, etc. are analyzed for $Tree-baseGraph(TG_{n})$ . ${TG}_{n}$ graph has network cost $O(6n)$ with a fixed degree of three and diameter $2n-2$ . From the network cost viewpoint, ${TG}_{n}$ has around 50% improvement results compared to existing fixed degree graphs such as mesh, torus, honeycomb mesh and shuffle-exchange permutation.