In parallel computing, processors are connected into various interconnection networks. A number of network topologies have been suggested by several researchers.
Among these topologies, the hypercube network is one of the most popular topologies due to many of its attractive properties. However, the hypercube is not best possible for its resources. Variations of the hypercube network have been discovered which further improve some of its properties.
But due to a lack of the unified model, results on one network are hard to apply to other variants. We have chosen a class of hypercube variants, called the class of hypercube-like graphs. The class of hypercube-like graphs is proposed for the first time by Vaidya et al. The class retains many attractive properties of hypercube and contains most important hypercube variants.
In this thesis, we introduce the class of HL-graphs and present the graph-theoretic properties of the class.
We present two oblivious routing algorithms for the HL-graphs. The dimension reducing algorithm is a natural extension of the e-cube routing algorithm. The dimension detouring algorithm runs with look-ahead information. Both algorithms find a routing path at most n steps for an n-dimensional HL-graph. And we also present a deadlock-free wormhole routing algorithm for the HL-graphs. We introduce a new interconnection network topology, called a randomly twisted cube. We prove that the average distance of a randomly twisted cube is O(n/log n), which is asymptotically optimal. Our experiments show that the randomly twisted cube works well. We also show that the fault diameter of the HL-graph is at most n+[log(n-1)].
And we show that HL-graphs are hamiltonian. This result gives a positive answer to Vaidya's conjecture. All HL-graphs are hamiltonian-connected or hamiltonian-laceable. And we show that HL-graphs are bipancyclic. We also show that HL-graphs retain hamiltonian properties when some edges or vertices are faulty.
병렬 컴퓨터에서 프로세서들은 상호연결망을 통해 연결된다. 이를 위한 다앙한 연결망 구조가 여러 연구자들에 의해 제안되었다.
이런 연결망 중에 하이퍼큐브는 그 흥미로운 성질 때문에 가장 널리 사용되고 있다. 하지만 하이퍼큐브가 같은 자원을 쓰는 가장 효율적인 망 구조는 아니다. 몇몇 성질을 좀 더 개선한 하이퍼큐브 망의 다양한 변형들이 제시되었다.
하지만 이들의 공통된 모델이 없어, 한 망에 대한 결과가 다른 변형 망들로 쉽게 확장이 되지 않았다. 이에 우리는 유사 하이퍼큐브 그래프 부류(이하 HL-그래프)에 주목하여 살펴보았다. 이 부류는 Vaidya 등에 의해 처음 제안되었다. 이 부류는 하이퍼큐브의 좋은 성질을 유지하며, 여러 중요한 하이퍼큐브 변형들을 포함한다. 본 논문에서는 이 HL-그래프 부류를 소개하고, 그래프 이론적인 성질들을 살펴보았다.
그리고 HL-그래프에서 쓰이는 라우팅 알고리즘을 제안했다. Dimension reducing 알고리즘은 하이퍼큐브에서 쓰이는 e-cube 라우팅 알고리즘의 확장이다. 그리고 미리 앞을 내다본 정보를 이용하는 dimension detouring 알고리즘을 제안했다. 두 알고리즘은 모두 n차원 HL-그래프에서 최대 n단계 이내의 라우팅 경로를 찾아주는 걸 보장한다. 그리고 데드락이 없는 웜홀 라우팅 알고리즘도 제안했다.
그리고 "마구 꼬인 큐브(randomly twisted cubes)"라는 새로운 연결망 구조를 제안했다. 이 마구 꼬인 큐브의 노드간 평균 거리가 O(n/log n)이라는 것을 보였다. 이 결과는 점근적 최적이다. 또한 실험을 통해서 이를 검증하였다. 그리고 HL-그래프의 고장 지름이 n+[log(n-1)] 보다 작음을 보였다.
HL-그래프가 해밀톤 성질을 가짐을 보였다. 이 결과는 Vaidya의 추측에 대해 답이 된다. 더 나아가 HL-그래프가 hamiltonian-connected나 hamiltonian-laceable 성질을 가짐을 보였다. 그리고 HL-그래프가 다양한 크기의 사이클을 부그래프로 가짐을 보였다. 또한 일부 정점이나 에지에 고장이 있더라도 해밀톤 성질을 계속 만족함을 보였다.
