하이퍼큐브와 매트릭스 하이퍼큐브 사이의 임베딩 알고리즘

• 영문명: Embedding Algorithms between Hypercube and Matrix Hypercube
• 발행기관: 인문사회과학기술융합학회
• 저자명: 김종석(Jongseok Kim) 이형옥(Heongok Lee)
• 간행물 정보: 『예술인문사회융합멀티미디어논문지』8권 9호, 201~210쪽, 전체 10쪽
• 주제분류: 사회과학 > 사회과학일반
• 파일형태: PDF
• 발행일자: 2018.09.30

국문 초록

하이퍼큐브는 효율적이고 대표적인 상호연결망 중 하나로 지금까지 수많은 연구를 통해 다양한 좋은 성질들을 갖고 있다는 것이 알려져 있다. 특히 하이퍼큐브 구조는 기존의 다양한 연결망(메쉬 토러스, 스타 등)에 임베딩 되어 알고리즘의 활용성을 높일 수 있는 장점이 있다. 매트릭스 하이퍼큐브는 노드를 행렬 형태로 표현하여 분지수에 비해 많은 노드 수를 갖게 되어 망비용이 개선된 네트워크이다. 알고리즘의 설계에 있어서 주어진 연결망을 다른 연결망으로 임베딩하는 것은 알고리즘을 활용하는 중요한 방법 중의 하나이다. 임베딩을 분석하는 척도로는 연장율, 밀집율, 확장율이 있다. 본 연구에서는 하이퍼큐브와 매트릭스 하이퍼큐브 사이의 임베딩 알고리즘을 제안한다. 하이퍼큐브가 매트릭스 하이퍼큐브에 연장율 3, 확장율 1에 임베딩 가능함을 보이고, 평균 연장율이 2 이하임을 보인다. 또한 매트릭스 하이퍼큐브의 노드와 에지를 하이퍼큐브에 일-대-일로 사상하는 비용이 O(n)보다 크지 않음을 보인다. 이러한 결과는 이미 개발된 하이퍼큐브의 알고리즘을 매트릭스 하이퍼큐브에서 효율적으로 활용할 수 있다는 것을 의미한다.

영문 초록

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. Hypercube structure has an advantage that it can enhance usage of the algorithm by embedding various of other networks(Mesh, Torus, Star etc). Matrix Hypercube is a network which has an improved network cost by having more nodes, express by matrix structure. 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, we can see that the cost isn’t bigger than O(n), which is an one to one mapping cost of Matrix Hypercube’s nodes and edge, to Hypercube. These results mean that we can use designed algorithms of hypercube in matrix hypercube efficiently.

목차

1. 서론

2. 관련연구

3. 임베딩 알고리즘

4. 결론

키워드

상호연결망 알고리즘 하이퍼큐브 매트릭스 하이퍼큐브 임베딩 Interconnection Network Algorithm Hypercube Matrix hypercube Embedding