하이퍼-스타 연결망의 위상적 성질과 방송 알고리즘
Topological Properties and Broadcasting Algorithm of Hyper-Star Interconnection Network
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
최근에 병렬처리를 위한 새로운 위상으로 하이퍼-스타 그래프 HS(m,k)가 제안되었다. 하이퍼-스타 그래프는 하이퍼큐브와 스타 그래프의 성질을 가지고 있으면서, 같은 노드수를 갖는 하이퍼큐브보다 망비용이 우수한 그래프이다. 본 논문에서는 하이퍼-스타 그래프 HS(m,k)가 하이퍼큐브의 서브그래프임을 증명한다. 그리고 정규형 그래프인 하이퍼-스타 HS(2n,n)가 제안된 매핑 기법에 의해 노드 대칭임을 보이며, 최소 높이를 갖는 스패닝 트리를 이용한 일-대-다 방송 기법을 제안하고, 방송 수행 시간이 2n-1임을 보인다.
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.
참고문헌 (10)
- S. B. Akers,D. Harel, "The star graph：An attractive alternative to the n-cube", pp.216~223 (1986)
- D-R. Duh, "Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules", 6(7), pp.714~723
- A. H. Esfahanian, "The Twisted N-Cube with Application to Multiprocessing", 40(1), pp.88~93 (1991)
- S. L. Johnsson, "Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures", 4, pp.133~172 (1987)
- J. Kim, "Operationally Enhanced Folded Hypercubes", 5(12), pp.1310~1316 (1994)
- H.-O. Lee, "Hyper-Star Graph：A New Interconnection Network Improving the Network Cost of the Hypercube", pp.858~865 (2002)
- F. T. Leighton, "Introduction to Parallel Algorithms and Architectures：Arrays" (1992), Morgan Kaufmann Publishers
- V. E. Mendia nad D. Sarkar, "Optimal Broadcasting on the Star Graph", 3(4), pp.389~396 (1992)
- A. S. Vaidya,P. S. N. Rao, "A Class of Hypercube_like Networks", pp.800~803 (1993)
- S.-K. Yun, "Comments on Hierarchical Cubic Networks", 9(4), pp.410~414 (1998)