The hypercube is one of the most versatile and efficient topologies yet discovered for parallel computation. It is well suited for the parallel execution of various algorithms for many application areas because of its regularity and their relatively small number of interprocessor connections. Recently, the mesh that is a rectangular grid-type array, and torus have been drawing a considerable attention as topologies for multiprocessor interconnection networks due to its simple, regular, and scalable architecture.
As the number of nodes in a multicomputers increases, the probability that some node fails also increases. To increase the reliability of the multicomputers, efficient fault-tolerant schemes in multicomputers are necessary.
There is an increasing interest in the problem of embedding graphs in faulty hypercubes. The embedding graphs such as rings[1, 2, 3, 5, 6], meshes[8], trees and so on, in faulty hypercubes, have been investigated by many researchers. Of these research results, we are particularly interested in the embedding of rings in faulty hypercubes. Many ring embedding algorithms for faulty hypercubes have been developed[1, 2, 3, 4, 5, 6].
Fault-tolerance in tori and meshes has been studied by several researchers, and several interesting techniques have been proposed, including fault-tolerant routing schemes[37, 38]. Ma et al. [32, 33] studied the problem of embedding d-dimensional meshes or tori in c-dimensional meshes or tori. Several topics related to the embedding in a faulty mesh have been studied previously including embedding linear arrays[34, 35], Hamiltonian cycles[31], and binary trees in a mesh with faulty nodes. Furthermore, it has been proved that embedding a Hamiltonian cycle in a mesh with arbitrary faulty nodes is NP-complete[30], and hence no efficient algorithm exists unless P=NP. Hedetniemi et al.[31] propose a ring embedding method in a mesh with a single faulty node.
In this thesis, we consider tasks that require a ring structure, which are mainly used in parallel and pipeline computations. We propose an ring embedding algorithm which improves over existing algorithms in the size of ring for hypercube multicomputers. Our algorithm can tolerate up to $\theta(2^{n/2})$ faults, and guarantee that given any f＜$(n-2k)2^k$ faulty nodes, it can find a ring of size at least $2^n-2f$ for $k=0$, $2^n-2f-2$ for $k=1$, and $2^n-2^{k-1}f-5\cdot2^{2k-3}$ for k≥2 in an n-dimensional hypercube.
We propose algorithms of embedding a ring in a partially faulty torus. We prove that, given any f≤4 faulty nodes, our algorithm always finds an optimal ring, i.e., one of the largest rings, in a $2m_1\times2m_2$ torus. And then, a Hamiltonian cycle can be found \it if and only if the number of faulty nodes which have even parity is equal to the number of faulty nodes which have odd parity, i.e., if and only if there are either 2 or 4 faulty nodes half of which are even and odd, respectively.
하이퍼큐브, 메쉬, 토러스는 여러 가지 효율적인 특성을 가지고 있기 때문에 많은 병렬 컴퓨터에서 상호연결망의 구조로 채택하였다. 즉 하이퍼큐브, 메쉬, 토러스는 구조가 규칙적이고 노드간을 연결하는 연결선의 수가 비교적 적기 때문에 여러 가지 응용분야의 알고리즘들을 병렬화시키기에 적합하다.
상호연결망(interconnection network)에서 가장 중요한 특징중의 하나가 이식성(portability)이다. 이식성이란 병렬 알고리즘에서 발생하는 통신 패턴을 효율적으로 시뮬레이션할 수 있는 능력을 말한다. 다중컴퓨터의 이식성을 높이기 위한 한 방법으로서 다중컴퓨터의 구조에 통신 패턴을 효율적으로 임베딩(embedding)하려는 연구가 많이 수행되었다.
다중컴퓨터의 노드의 수가 증가함에 따라 몇개의 노드에 결함이 발생할 확률이 점점 높아지고 있다. 따라서 다중컴퓨터의 신뢰성(reliability)을 높이기 위해서는 다중컴퓨터에서 사용할 수 있는 효율적인 결함허용(fault-tolerant)기법이 필요하다. 이러한 이유때문에 결함이 있는 다중컴퓨터 구조에 그래프를 임베딩하려는 연구가 많이 수행되었다. 즉 결함노드를 가진 다중컴퓨터에 링, 메쉬, 트리 등의 그래프를 임베딩하는 연구가 많이 수행되어 왔다.
본 논문에서는 결함노드를 가진 하이퍼큐브에 링을 임베딩하는 문제를 다룬다. 링 구조는 병렬 계산이나 파이프라인 방식의 계산에 많이 사용되는 구조이다. 따라서 결함노드를 가진 다중컴퓨터에 링 구조를 효율적으로 임베딩할 수 있으면 다중컴퓨터의 이식성과 신뢰성을 높일 수 있다.
본 논문에서 결함노드를 가진 하이퍼큐브 다중컴퓨터에 링을 임베딩하는 알고리즘을 제안하였다. 이 알고리즘은 기존의 알고리즘에 비해 더 큰 크기의 링을 임베딩할 수 있다. 즉 본 논문에서 제안한 링 임베딩 알고리즘은 $\theta(2^{n/2})$개의 결함노드를 허용할 수 있다. 즉 n-차원 하이퍼큐브에 $f<(n-2k)2^k$개의 결함노드가 발생했을 때 k=0인 경우는 $2^n-2f$개, k=1인 경우는 $2^n-2f-2$개, k≥2인 경우는 $2^n-2^{k-1}f-5\cdot2^{2k-3}$개 이상 크기의 링을 임베딩할 수 있다.
본 논문에서는 결함노드를 가진 토러스 다중컴퓨터에서 링을 임베딩하는 알고리즘을 제안하였다. 본 논문에서는 제안된 알고리즘이 $2m_1\times2m_2$ 토러스에서 f≤4일 때 토러스에 해밀토니안 사이클(Hamiltonian cycle)이 존재할 필요충분조건이 짝수 패리티(even parity)의 결함노드의 갯수와 홀수 패리티(odd parity)의 결함노드의 갯수가 같다는 것임을 증명하였다.
