Full Binary Tree-Based Fixed Degree Graph Design and Parallel Algorithm

Abstract

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 $\ast $ 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.

Keywords

• Fixed degree
• full binary tree
• interconnection network
• network cost
• parallel paths