Major topics of this thesis are concentrated on two issues: (1) Optimal routing algorithms of the hierarchical cubic network (HCN) and a hierarchical hypercube network (HHN) based on the extension of HCN and (2) Fault-tolerant routing algorithm and distributed fault-free subcube identification algorithms in a faulty hypercube.
The hypercube topology has many advantages. However, it is not suitable for very large-scale parallel computers due to rapid increase of links. So, we need interconnection networks which have the smaller node degree and hold many advantages of the hypercube. The HCN proposed by Ghose and Desai is a network with these desirable properties. The HCN has the smaller diameter regardless of the smaller node degree. The performance of parallel algorithms with regular pattern of communications is identical to their performance on a hypercube. We propose the optimal routing algorithm in the HCN and show that the diameter of HCN(n, n) which consists of $2^{2n}$ nodes is $n+\lceil(n+1)/3\rceil$+1 while its node degree is only n+1. Incomplete HCN's are also discussed.
We also propose the hierarchical hypercube network (HHN), which is a multiple level extension of the HCN, and deal with the routing algorithm, broadcasting algorithm, and some properties. The HHN has a smaller number of links than the comparable hypercube. In particular, the HHN network with $2^K$ nodes can be constructed with the node degree about $2\sqrt{K}$ while the node degree of the comparable hypercube is K . Due its smaller node degree, the HHN is an interconnection network suitable for constructing large scale parallel computers. Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in hypercube and a hypercube can emulate the comparable hypercube in O(1) time. Thus, HHN is a good alternative to the popular hypercube network for large scale parallel systems.
As the second topic, fault-tolerant methods for a faulty hypercube are dealt with. With the increase in the number of processors, the likehood of failure of various nodes or links increase. Therefore, fault-tolerant processing in large scale systems is very important. We propose the fault-tolerant shortest path routing algorithm and the distributed identification algorithm of all fault-free subcubes in a hypercube with faulty components. The fault-tolerant shortest path routing algorithm can be used in a hypercube with any number of faulty components and provides the shortest path using the guide information obtained by trial-and-error during the first routing between two nodes. The guide information consists of the output dimension and the number of detours for each destination. The size of the guide information at each node is not large in comparison with the number of faulty links.
The identification of fault-free subcubes in a faulty hypercube is important in the processor allocation. Identified fault-free subcubes can be used as the initial state in processor allocation. In identifying fault-free subcubes, each node need not know explicitly the location of faulty components and identify all the fault-free subcubes by exchanging the information of free-cubes with its neighbors. The proposed distributed algorithm can identify fault-free subcubes regardless of node failure or link failure while most of other algorithms assume only the node failure. This algorithm is more efficient than Latifi's algorithm.
본 논문에서는 다음과 같은 두 가지 주제에 대해서 다룬다. 첫째, 다중컴퓨터 형태의 병렬컴퓨터를 위한 계층적 하이퍼큐브 네트웍에 대해서 다루고, 둘째, 고장이 잇는 하이퍼큐브 컴퓨터에서의 고장허용 라우팅 알고리즘과 고장없는 서브큐브 찾는 알고리즘을 제시한다.
하이퍼큐브 구조는 이 구조가 지닌 여러 장점들로 인해서 많은 관심을 받아왔고 KAICUBE-860등의 하이퍼큐브 구조를 갖는 연구용/상업용 병렬컴퓨터들이 발표 되었다. 하이퍼큐브가 비교적 적은 노드 차원을 갖고 있음에도 불구하고 대규모의 시스템을 구현하려고 할 때에 링크의 개수가 구현하기 어려울 정도로 커지게 된다. 따라서 하이퍼큐브의 많은 장점을 유지하면서 하이퍼큐브보다 더 적은 노드 차원을 갖는 연결 네트웍을 사용하는 것이 바람직하다. Ghose와 Desai가 제안한 HCN(Hierarchical Cubic Network)은 이러한 조건을 비교적 잘 만족시키는 네트웍이다. HCN은 하이퍼큐브보다 작은 노드차수로 구성되고 더 작은 지름을 갖는다. 그리고 하이퍼큐브에 적합한 많은 병렬 프로그램을 같은 시간 복잡도로 HCN에서 수행 시킬 수 있다. 본 논문에서는 HCN에서의 최단거리 라우팅 방법을 제시하고 이를 바탕으로하여HCN(n,n)의 지름을 유도한다. HCN(n,n)은 노드 차원이 같은 크기의 하이퍼큐브이 거의 반 정도인 n+1임에도 불구하고 그 지름이 $n+\lceil(n+1)/3\rceil$+1에 불과하다. 불완전HCN인 HCN(m,n) (m≤n)에 대해서HCN(n,n)의 여러 결과를 확장시켜 적용하였다.
그 다음에 HCN의 확장된 형태의 계층적 하이퍼큐브 네트웍인 HHN (Hierarchical Hypercube Network)을 제안한다. HHN은 여러 단계의 확장이 가능하고 HCN은 1단계의 HHN이다. $2^k$개의 노드로 구성되는 HHN 네트웍을 만들 수 있는 최소 노드차수는 $2\sqrt{K}$ 보다 작다. 이에 비해서 하이퍼큐브는 K의 노드 차수가 필요하다. HHN은 이러한 적은 노드 차원에도 불구하고 하이퍼큐브를 최대 3단계에 emulation 을 할 수 있고 하이퍼큐브에 적합한 병렬 프로그램은 하이퍼큐브와 같은 시간 복잡도로 수행될 수 있다. 이러한 적은 노드 차수로 큰 크기의 네트웍을 구성 할 수 있고 병렬 프로그램은 커다란 성능 저하 없이 수행할 수 있기 때문에 커다란 병렬 컴퓨터를 구성할 때에 하이프큐브 구조의 대안으로 적합하다.
병렬 컴퓨터를 구성하는 프로세서 개수의 증가에 따라서 노드와 이들을 연결하는 링크의 고장 가능성은 증가한다. 대규모 병렬 컴퓨터는 많은 비용이 들어가기 때문에 이러한 고장에도 불구하고 병렬컴퓨터를 사용할 수 있어야 한다. 본 논문에서는 고장이 있는 하이퍼큐브 구조의 병렬컴퓨터에서 메시지가 최단거리를 목적지까지 전달되도록 하는 고장허용 최단거리 라우팅 알고리즘과 고장이 없는 서브큐브를 분산방식으로 찾는 알고리즘을 제시한다.
임의의 개수의 고장이 있는 하이퍼큐브에서 최단거리 라우팅 알고리즘은 두 노드사이의 첫 번째 라우팅동안에 최단거리 경로를 찾고 최단 경로에 대한 정보를 각 노드에 저장한다. 첫 번째 라우팅에서 처음에는 우회 없이 라우팅을 시도하고 경로를 찾을 수 없을 때에는 허용우회횟수를 증가시켜가면서 라우팅을 시도한다. 라우팅 동안 backtracking 메시지를 받은 노드는 다른 경로를 선택하고 새로운 경로에 대한 정보를 guide information으로서 저장한다. 이렇게 얻어진 guide information 을 사용하면 같은 목적지에 대해서는 항상 최단거리 경로로 메시지를 전달할수 있다. 각 노드가 보관해야할 guide information의 크기는 고장난 전체 링크 수에 비해서 상당히 작다.
고장있는 하이퍼큐브에서 고장없는 서브큐브를 찾는 분산 알고리즘에서는 초기에 각 노드는 인접 노드와의 연결상태에 대한 정보만 갖는다. 인접노드와 서로 현재까지 찾는 서브큐브 정보를 교환하여 새로운 고장없는 서브큐브를 찾는다. n큐브에서 n번의 정보교환이 필요하다. 고장난 링크가 있을 때에는 앞서 찾은 서브큐브가 틀릴 수가 있다. 따라서 이를 바로잡는 과정이 필요하다. 다시 n-1번의 이웃노드와의 정보교환을 통해서 각 노드는 잘못된 결과를 바로잡는다. 이전에 제시되었던 알고리즘들이 링크의 고장은 고려하지 않고 있는 데 비해서 본 논문에서 제시되는 알고리즘은 링크의 고장을 다룰 수 있다. Latifi의 분산알고리즘과 비교하면 통신횟수나 비교횟수면에서 본 알고리즘이 더 효율적이다.