하이퍼큐브의 망비용을 개선한 매트릭스 하이퍼큐브 설계 및 분석
Design and analysis of matrix hypercube with improved network cost of hypercube
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
상호연결망은 병렬 컴퓨터의 프로세서 연결 구조를 제공한다. 대표적인 상호연결망으로 토러스, 하이퍼큐브, 스타그래프가 있다. 하이퍼큐브는 재귀적 구조, 노드 대칭성, 간단한 라우팅 알고리즘 등 다양한 장점을 갖는 상호 연결망으로 가장 많이 상용화되고 있다. 본 논문에서는 하이퍼큐브의 망 비용을 개선하기 위해 분할정복 기법을 적용할 때 고려할 내용을 분석한다. 또한 연구 결과를 기반으로 분할정복 기법을 적용한 새로운 매트릭스 하이퍼큐브를 제안한다. 제안된 매트릭스 하이퍼큐브의 클러스터 성질을 분석하였다. 추가하여 라우팅 알고리즘을 제안하고, 라우팅에 따른 지름을 도출하여 다른 연결망들과 망 비용을 비교 분석하였다. 매트릭스 하이퍼큐브는 동일한 노드 개수를 갖는 하이퍼큐브와 비교했을 때 분지수가 3/4 개선되었다. 망 비용 관점에서는 하이퍼큐브가 이고, 매트릭스 하이퍼큐브는 을 갖는다. 따라서 본 연구에서 제안한 매트릭스 하이퍼큐브가 하이퍼큐브보다 개선된 결과를 갖는다.
Abstract
The interconnection network provides a processor connection structure for parallel computers. Typical interconnections include torus, hypercube, and star graph. Hypercube is the most widely used interconnection network with various advantages such as recursive structure, node symmetry, and simple routing algorithm. In this paper, we analyze what to consider when applying the devide-and-conquer method to improve the network cost of the hypercube. We also propose a new matrix hypercube based on the results of the study. The cluster properties of the proposed matrix hypercube are analyzed. In addition, we propose a routing algorithm, derive the diameter according to the routing, and compare the network cost with other networks. Matrix hypercube improved by 3/4 compared to hypercube with the same number of nodes. In terms of network cost, hypercube is, and matrix hypercube has. Therefore, the proposed matrix hypercube has better results than hypercube.
참고문헌 (10)
- Jung-hyun Seo, "Link-Disjoint Broadcasting Algorithm in Wormhole-Routed 3D Petersen-Torus Networks", International Journal of Distributed Sensor Networks, 9(12), pp.1~7 (2013)
- González-Durruthy, M, "Carbon Nanotubes’ Effect on Mitochondrial Oxygen Flux Dynamics:Polarography Experimental Study and Machine Learning Models using Star Graph Trace Invariants of Raman Spectra", Nanomaterials, 7(11), pp.386~ (2017)
- Tanaka, Yuuki, "On the Stack Number and the Queue Number of the Bubble-Sort Graph, IEICE Transactions on Fundamentals of Electronics", Communications and Computer Sciences, 99(6), pp.1012~1018 (2016)
- Konstantinova, Elena, "Independent even cycles in the Pancake graph and greedy Prefix-reversal Gray codes", Graphs and Combinatorics, 32(5), pp.1965~1978 (2016)
- 서정현, "새로운 상호연결망 하프 버블정렬 그래프 설계 및 성질 분석", 한국정보통신학회논문지, 21(7), pp.1327~1334 (2017), 한국정보통신학회[DOI]
- Saikia, Dilip K., "Embedding torus on the star graph", IEEE Transactions on Parallel and Distributed Systems, 9(7), pp.650~663 (1998)
- Bettayeb, Saïd, "Embedding star networks into hypercubes", IEEE Transactions on Computers, 45(2), pp.186~194 (1996)
- J.-H. Park, "Circulant Graphs and their Applications to Communication Networks", Ph. D, Dept. Computer Science, pp.1992
- K. Efe, "A Variation on the Hypercube with Lower Diameter", IEEE Trans. comput, 40(11), pp.1312~1316 (1991)
- J.-S. Kim, "A Design of Interconnection Network Based on Matrix Operation", Ph. D, Dept. Computer Science, pp.2001