하이퍼-스타 연결망의 위상적 성질과 방송 알고리즘 = Topological Properties and Broadcasting Algorithm of Hyper-Star Interconnection Network

다국어 초록 (Multilingual Abstract)

Recently A Hyper-Star Graph HS(m,k) has been introduced as a new interconnection network of new topology for parallel processing. Hyper-Star Graph has properties of hypercube and star graph, further improve the network cost of a hypercube with the same number of nodes. In this paper, we show that Hyper-Star Graph HS(m,k) is subgraph of hypercube. And we also show that regular graph, Hyper-Star Graph HS(2n,n) is node-symmetric by introduced mapping algorithm. In addition, we introduce an efficient one-to-all broadcasting scheme - takes 2n-1 times-in Hyper-Star Graph HS(2n,n) based on a spanning tree with minimum height.

국문 초록 (Abstract)

최근에 병렬처리를 위한 새로운 위상으로 하이퍼-스타 그래프 HS(m,k)가 제안되었다. 하이퍼-스타 그래프는 하이퍼큐브와 스타 그래프의 성질을 가지고 있으면서, 같은 노드수를 갖는 하이퍼큐브보다 망비용이 우수한 그래프이다. 본 논문에서는 하이퍼-스타 그래프 HS(m,k)가 하이퍼큐브의 서브그래프임을 증명한다. 그리고 정규형 그래프인 하이퍼-스타 HS(2n,n)가 제안된 매핑 기법에 의해 노드 대칭임을 보이며, 최소 높이를 갖는 스패닝 트리를 이용한 일-대-다 방송 기법을 제안하고, 방송 수행 시간이 2n-1임을 보인다.

참고문헌 (Reference)

1 S. B. Akers,D. Harel, "The star graph：An attractive alternative to the n-cube" 216-223, 1986.

2 A. H. Esfahanian, "The Twisted N-Cube with Application to Multiprocessing" 40 (40): 88-93, 1991.

3 V. E. Mendia nad D. Sarkar, "Optimal Broadcasting on the Star Graph" 3 (3): 389 -396, 1992

4 J. Kim, "Operationally Enhanced Folded Hypercubes" 5 (5): 1310 -1316, 1994

5 F. T. Leighton, "Introduction to Parallel Algorithms and Architectures：Arrays" Morgan Kaufmann Publishers 1992.

6 H.-O. Lee, "Hyper-Star Graph：A New Interconnection Network Improving the Network Cost of the Hypercube" 858-865, 2002

7 S. L. Johnsson, "Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures" 4 : 133-172, 1987.

8 S.-K. Yun, "Comments on Hierarchical Cubic Networks" 9 (9): 410-414, 1998

9 D-R. Duh, "Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules" 6 (6): 714-723, July1995.

10 A. S. Vaidya,P. S. N. Rao, "A Class of Hypercube_like Networks" 800-803, 1993.