하이퍼큐브와 매트릭스 하이퍼큐브 사이의 임베딩 알고리즘
Embedding Algorithms between Hypercube and Matrix Hypercube
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
하이퍼큐브는 효율적이고 대표적인 상호연결망 중 하나로 지금까지 수많은 연구를 통해 다양한 좋은 성질들을 갖고 있다는 것이 알려져 있다. 특히 링, 트리, 메쉬 등과 같은 다른 연결망 구조들이 효율적으로 임베딩 될 수 있다. 매트릭스 하이퍼큐브는 하이퍼큐브와 동일한 노드 개수를 가지면서 하이퍼큐브보다 망비용이 개선된 연결망이다. 알고리즘의 설계에 있어서 주어진 연결망을 다른 연결망으로 임베딩하는 것은 알고리즘을 활용하는 중요한 방법 중의 하나이다. 임베딩을 분석하는 척도로는 연장율, 밀집율, 확장율이 있다. 본 연구에서는 하이퍼큐브와 매트릭스 하이퍼큐브 사이의 임베딩 알고리즘을 제안한다. 하이퍼큐브가 매트릭스 하이퍼큐브에 연장율 3, 확장율 1에 임베딩 가능함을 보이고, 평균 연장율이 2 이하임을 보인다. 또한 매트릭스 하이퍼큐브가 하이퍼큐브에 임베딩하는 비용이 O(n)임을 보인다. 이러한 결과는 이미 개발된 하이퍼큐브의 알고리즘을 매트릭스 하이퍼큐브에서 효율적으로 활용할 수 있다는 것을 의미한다.
Abstract
One of the most popular and efficient interconnection networks is hypercube. Through the various studies, we can know that it has a lot of good properties. Especially, lots of interconnection networks can be embedded into hypercube efficiently. Matrix Hypercube is that an interconnection network has improved network cost than that of hypercube with the same number of nodes. It is one of the important measures in the area of algorithm design that any interconnection network should be embedded into another interconnection network for the practical use of algorithm. The measures of the embedding are dilation, congestion and expansion. In this paper, we propose embedding algorithms between hypercube and matrix hypercube. We show that hypercube can be mapped into matrix hypercube with dilation 3 and expansion 1, and the average dilation is less than 2. Also, matrix hypercube can be embedded into hypercube with dilation O(n). These results mean that we can use designed algorithms of hypercube in matrix hypercube efficiently.
참고문헌 (13)
- Y. Saad, "Topological properties of hypercubes", IEEE Transactions on Computers, 37(7), pp.867~872 (1988)
- S. L. Bezrukov, "Embedding complete trees into the hypercube", Discrete Applied Mathematics, 110(2-3), pp.101~119 (2001)
- J.-S. Fu, "Fault-tolerant cycle embedding in the hypercube", Parallel Computing, 29(6), pp.821~832 (2003)
- P. T. Gaughan, "Adaptive routing protocols for hypercube interconnection networks", Computer, 26(5), pp.12~23 (1993)
- S.-Y. Hsieh, "Fault-tolerant embedding of pairwise independent hamiltonian paths on a faulty hypercube with edge faults", Theory of Computing Systems, 45(2), pp.407~425 (2009)
- J. Liang, "The t", s-diagnosability of hypercube networks under the PMC and comparison models, 2017, pp.5, 2169~3536
- A. Y. Wu, "Embedding of tree networks into hypercubes", Journal of Parallel and Distributed Computing, 2(3), pp.238~249 (1985)
- H.-C. Keh, "On fault-tolerant embedding of hamiltonian cycles, linear arrays and rings in a flexible hypercube", Parallel Computing, 26(6), pp.769~781 (2000)
- 서정현, "하이퍼큐브의 망비용을 개선한 매트릭스 하이퍼큐브 설계 및 분석", 예술인문사회 융합 멀티미디어 논문지, 8(7), pp.769~777 (2018), 사단법인 인문사회과학기술융합학회[DOI]
- J.-S. Kim, "A note on embeddings among folded hypercubes, even graphs and odd graphs", International Journal of Computer Mathematics, 8(5), pp.882~891 (2011)
- J.-S. Kim, "Embedding Hypercubes, Rings and Odd graphs into Hyper-stars", International Journal of Computer Mathematics, 86(5), pp.771~778 (2009)
- D. I. Moldovan, "Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays", IEEE Transactions on Computers, C-35(1), pp.1~12 (1986)
- M.-C. Yang, "Fault-tolerant cycle-embedding of crossed cubes", Information Processing Letters, 88(4), pp.149~154 (2003)