새로운 상호연결망 하프 버블정렬 그래프 설계 및 성질 분석 = Design and feature analysis of a new interconnection network : Half Bubblesort Graph

다국어 초록 (Multilingual Abstract)

The Bubble sort graph is node symmetric, and can be used in the data sorting algorithm. In this research we propose and analyze that Half Bubble sort graph that improved the network cost of Bubble sort graph. The Half Bubble sort graph's number of node is n!, and its degree is ${\lfloor}n/2{\rfloor}+1$. The Half Bubble sort graph's degree is $${\sim_=}0.5$$ times of the Bubble sort, and diameter is $${\sim_=}0.9$$ times of the Bubble sort. The network cost of the Bubble sort graph is $${\sim_=}0.5n^3$$, and the network cost of the half Bubble sort graph is $${\sim_=}0.2n^3$$. We have proved that half bubble sort graph is a sub graph of the bubble sort graph. In addition, we proposed a routing algorithm and analyzed the diameter. Finally, network cost is compared with the bubble sort graph.

참고문헌 (Reference)

1 N. Y. Phing, "Topology Design of Extended Torus and Ring for Low Latency Network-on-Chip Architecture" 15 (15): 869-876, 2017

2 J. H. Seo, "Three-dimensional Petersen-torus network : a fixed-degree network for massively parallel computers" 64 (64): 987-1007, 2013

3 P. Matthew, "There and Back Again : Optimizing the Interconnect in Networks of Memory Cubes" 678-690, 2017

4 S. Klaus, "The fourth industrial revolution" Penguin UK 2017

5 M. Heydari, "On sorting by prefix reversals and the diameter of pancake networks" 218-227, 1993

6 C. H. Yeh, "Macro-Star Networks : Efficient Low-Degree Alternatives to Star Graphs" 9 (9): 987-1003, 1998

7 H. Hossein, "Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks" 1-20, 2017

8 Q. Dong, "Embedding a mesh of trees in the crossed cube" 112 (112): 599-603, 2012

9 Z. T. Chou, "Bubblesort star graphs : a new interconnection network" 41-48, 1996

10 S. B. Akers, "A group-theoretic model for symmetric interconnection networks" 38 (38): 555-566, 1989