Graph embedding is one of the key conceptual tools for implementing parallel algorithms or simulating interconnection networks on a parallel computer. In this thesis, we study on embeddings of graphs into a hypercube, recursive circulant, and hypermesh.
First, we propose a many-to-one embedding strategy of a tree-related graph into a recursively-structured graph. Here, the tree related graph is a complete binary tree, mesh of trees or pyramid. The strategy evenly distributes the same level nodes of a tree-related graph to the nodes of the recursively-structured graph. From this strategy, we design embedding methods of a tree-related graph into a hypercube or recursive circulant. The methods are optimal or nearly optimal in terms of the general embedding measures such as dilation, congestion, and load.
Second, we present one-to-one embedding methods of graphs into a hypermesh. All these embeddings are optimal in terms of alignment cost. The alignment cost is one of the important embedding measures for hypermesh. We show how to embed a butterfly using the concept of quotient group. We also show how to embed multiple copies of a graph using a labeling scheme. This embedding of multiple copies is optimal in all respects of congestion, expansion, and alignment cost.
Our new or improved embedding results shows that the recursive circulant and hypermesh as well as the hypercube are versatile interconnection networks.
그래프 임베딩은 병렬 컴퓨터에 다양한 구조의 병렬 알고리즘을 구현하거나 상호 연결망을 시뮬레이션하기 위한 핵심적인 개념이다. 본 논문에서는 하이퍼큐브, 재귀원형군, 하이퍼메쉬에 그래프들을 임베딩하는 연구를 수행한다.
먼저, 재귀적 구조를 가지는 그래프에 트리-관련 그래프를 다-대-일 임베딩하는 전략을 제시한다. 여기서 트리-관련 그래프란 완전이진트리나 메쉬오브트리나 피라미드를 말한다. 이 전략은 트리-관련 그래프에서 같은 레벨에 있는 노드들을 재귀적 구조를 가지는 그래프에서 골고루 분산되도록 한다. 이 전략으로부터, 트리-관련 그래프를 하이퍼큐브나 재귀원형군에 임베딩하는 방법들을 고안한다. 이 방법들은 연장율, 밀집률, 부하율 같은 일반적 임베딩 척도들면에서 최적이거나 최적에 가깝다.
다음으로는, 그래프들을 하이퍼메쉬에 일-대-일 임베딩하는 방법들을 제시한다. 이 임베딩 방법들은 정렬비용면에서 최적인데, 정렬비용은 하이퍼메쉬에 대한 임베딩에서 주요한 비용 척도중 하나이다. 몫 그룹 (quotient group) 개념을 이용하여 버터플라이를 임베딩하고, 레이블링 전략을 이용하여 한 그래프의 여러 복사본을 임베딩한다. 이 여러 복사본의 임베딩은 밀집률, 팽창율, 정렬비용측면에서 모두 최적이다.
이러한 임베딩들은 새롭거나, 기존의 연구들을 개선한 것으로서, 하이퍼큐브뿐아니라 재귀원형군과 하이퍼메쉬도 범용의 상호 연결망임을 보여준다.
