A multicomputer system consists of a large number of cooperating computer nodes interconnected in a fixed topology, interconnection network, to increase the computation speed by employing parallelism. The interconnection network should provide adequate performance to avoid becoming a bottleneck of the overall performance. In addition, it should be fault-tolerant since the probability that some nodes in the system will fail increases proportionally to the size of the network.
In this thesis, a family of symmetric graphs, called multistage DeBruijn graph, is proposed by generalizing the DeBruijn graph to be used as the interconnection topologies of multicomputer systems. Due to the symmetry, the performance of an interconnection network can be increased by minimizing the congestion problem since the load for message communication will be distributed uniformly through all the nodes and communication links. Moreover, the cost to develop a system can be reduced due to the symmetry since identical hardwares and softwares can be used for each node.
It is shown that the proposed graph is a good candidate for symmetric and fault-tolerant interconnection networks by the characteritics of the graph such as the small diameter, vertex-symmetry, edge-symmetry, existence of Hamilton cycles, large fault-tolerance, and existence of wide and short containers. With regard to performance considerations, the proposed graph is superior to other known symmetric graphs such as the hypercube and the star graph by the fact that the proposed graph contains remarkably larger number of nodes than the others for given degree and diameter. With regard to fault-tolerance considerations, the proposed graph is superior to other known fault-tolerant graphs such as the star graph and the flip-tree by the fact that it has asymptotically best known fault-diameter and container-diameter which are important measures of fault-tolerance and performance degradation due to faults. Finally, simple and efficient algorithms for message routing and broadcasting are given.
병렬 처리 방식을 도입하여 계산 속도를 높이는 한 방법으로서 하나의 다중 컴퓨터 시스템은 많은 수의 상호 협력하는 컴퓨터 노드들로 구성된다. 컴퓨터 노드들은 일정한 연결망으로 상호 연결되며 메시지를 주고 받으므로써 상호 통신이 가능하게 된다. 따라서 연결망은 상호 메시지 교환에 필요한 성능을 제공해야하며, 노드 수가 늘어남에 따라 몇몇 노드들에 고장이 발생할 확률도 비례해서 증가하므로 충분한 고장 허용성을 가져야 한다.
본 논문에서는 그래프들의 곱을 이용하여 DeBruijn 그래프를 일반화함으로써 연결망 구조로서 적합한 대칭성 그래프를 제안하고 성능 면에서나 고장 허용성 면에서 기존의 연결망 구조들보다 우수함을 보여 주었다. 연결망 구조가 대칭성을 가짐으로써 메시지 교환에 필요한 부하가 노드들과 통신선들에 균일하게 분배되고 따라서 병목현상이 없어지고 전체 성능이 향상될 수 있다. 또한 각 노드를 위해 동일한 하드웨어와 소프트웨어를 사용할 수 있으므로 시스템의 개발 비용을 줄일 수 있다.
주어진 노드 갯수와 노드당 통신선 갯수에 대해 연결망의 성능을 나타내는 척도로서 주로 직경이 사용되는데, 본 논문에서 제안된 그래프는 기존의 대칭성 그래프인 하이퍼큐브 (Hypercube)나 성형 그래프 (Star Graph)보다 직경이 작고 따라서 성능면에서 우수하다. 또한, 고장 허용성과 고장 발생시 성능 저하 정도를 나타내는 척도인 고장 직경 (Fault-Diameter)과 컨태이너 직경 (Container-Diameter)면에서도 제안된 그래프는 기존의 그래프들 중에서 가장 우수함을 보여 주었다. 덧붙여서, 메시지의 경로 선택과 브로드캐스팅을 위한 간단하고 효율적인 알고리즘을 제시하였다.
