An important feature of an interconnection network is its ability to efficiently simulate algorithms proposed for other architectures. Such a simulation problem can be formulated as graph embedding. A good embedding is said to exist when adjacent vertices in the guest graph are mapped to reasonably close vertices in the host graph and when a path between adjacent vertices in the guest graph is chosen in a way that the congestion of the corresponding path in the host graph is moderately small. Therefore, the fitness of embedding can be measured by dilation and congestion.
In this thesis, we embed grids into recursive circulant. Recursive circulant R(N, d) is a circulant graph with N vertices and jumps of power of d. We propose an embedding scheme named iterative 2-edge labeling which can embed 88.6% of grids into their optimal recursive circulant with dilation 1 and congestion 1. This algorithm also can be applied for embedding cylinder and torus into recursive circulant.
본 논문에서는 병렬처리 분야에서 가장 널리 쓰이는 연결망 구조의 하나인 격자구조를 재귀원형군에 임베딩하는 문제를 다룬다. 병렬처리를 위한 프로세서들은 트리나 격자와 같이 다양한 구조로 연결되며, 각 연결망 구조에 따라서 서로 다른 다양한 병렬처리 알고리즘이 제안되고 있다. 주어진 연결망 구조에서의 효율적인 병렬처리 알고리즘을 제안하기 위한 방법의 한 가지는, 이미 알려진 좀 더 단순한 연결망 구조에서의 효율성이 검증된 알고리즘을 주어진 연결망에 적용하는 것이다. 이와 같이 하나의 연결망 구조에 대한 알고리즘을 다른 연결망 구조를 위해 사용하기 위해서는, 각 연결망 구조를 분석하여 그 대응관계를 찾을 필요가 있다. 이러한 대응관계를 찾는 문제를 네트워크 임베딩이라고 한다.
이와 같은 문제를 해결하기 위하여, 재귀원형군의 특성을 관찰하고 그 관찰 결과를 이용하여 연속 라벨링이라는 기법을 제안하였다. 이 방법으로 우리는 몇몇 특별한 크기의 격자 구조가 2-edge labeling을 갖음을 알게 되었다. 이와 함께 격자구조의 특성인 확대 축소가 간단한 점을 이용하여 격자구조를 재귀원형군에 임베딩할 수 있는 알고리즘을 제안하였다. 이 알고리즘을 이용하면, 모든 격자구조의 88.6%에 대해 항상 그 최적의 재귀원형군으로 dilation 1과 congestion 1으로 임베딩이 가능함을 보였다. 또한, 임베딩에 소요되는 시간복잡도는 N × M 격자구조에 대해 최적인 O(NM)이 소요되며, 단 하나의 노드에 대해 그에 대응하는 재귀원형군의 노드를 O(1)에 찾을 수 있다. 이 기법과 그래프 곱을 이용함으로서 격자구조와 유사하나 좀 더 복잡한 구조인 실린더와 토러스를 재귀원형군에 임베딩하는 알고리즘을 제안하였다.
이 알고리즘의 특징은격자구조와 달리 확대 축소가 구조에 영향을 끼치기 때문에 선대칭의 라벨링을 통하여 확대 축소가 가능하게 한 것이다. 이 알고리즘은 44.3%의 실린더와 22.2%를 각각의 최적 재귀원형군으로 dilation 1, congestion 1에 임베딩할 수 있으며, 88.6%의 실린더와 토러스를 dilation 2, congestion 1에 임베딩할 수 있다. 이 알고리즘의 시간 복잡도 역시 최적이다.
