The performance of a multicomputer system is largely affected by the performance of the communication network. Nodes of a multicomputer system communicate each other by sending and receiving messages through the communication network. The performance of the communication network is determined by several factors such as topology, switching technique, flow control policy, and routing algorithm adopted in the system. It is necessary to develop an efficient routing algorithm for constructing high performance communication network. Recently, the number of nodes that compose a multicomputer system tends to increase. In a large scale multicomputer system that has thousands of nodes, the possibility of component failure is rather high. Therefore, the communication network is desirable to have ability to communicate messages despite of faulty components as well as to maintain high performance. A fault tolerant routing algorithm is mandatory to provide fault tolerant communication in multicomputer systems. A good fault tolerant routing algorithm should guarantee the correct delivery of messages under various faulty situations and exhibit high performance under both faulty and normal situation. Moreover, these goals should be achieved with moderate hardware requirement.
We propose a fault tolerant routing scheme based on the solid fault model. The proposed fault tolerant routing algorithm can be applied multicomputer system constructed with mesh topology and employing the wormhole switching technique. With the solid fault model, we can cover all convex fault regions and a large portion of concave fault regions. The proposed fault tolerant routing scheme can tolerate any number of node and channel faults if the fault regions are solid fault regions. Furthermore, the fault regions are allowed to be overlapped each other and to be fault chains. To resolve non-solid concave fault regions, we also propose a fault region conversion algorithm. The fault region conversion algorithm transforms non-solid fault regions into solid ones by deactivating some functional nodes. We prove that the proposed fault tolerant routing algorithm is deadlock and livelock free with four virtual channels. We extend the proposed fault tolerant routing algorithm to be adaptive and to general higher dimensional meshes. The extended routing algorithm also uses only four virtual channels. We evaluate the performance of the proposed fault tolerant routing algorithm by extensive simulations under various fault conditions. We show that the proposed fault tolerant routing algorithm maintains high performance under normal situation and exhibits a gradually degraded performance behavior under faulty situations. We also show that the non-solid fault regions are converted to solid ones by deactivating a small number of functional nodes. We expect that the proposed fault tolerant routing algorithm can be easily implemented with hardware since it requires a small number of virtual channels and has a simple routing decision logic.
다중컴퓨터(Multicomputer)시스템은 각각이 하나의 독립적인 컴퓨터라고 볼수 있는 노드들이 상호 연결망에 의해 연결되어 있는 병렬처리 시스템이다. 다중컴퓨터 시스템에 포함된 노드들은 상호 연결망을 통해 서로간의 동기화 정보 및 데이타를 메시지 형태로 전송 및 수신함으로써 주어진 일을 수행해 나간다. 따라서 다중컴퓨터 시스템의 성능은 노드간의 상호 연결망의 성능에 크게 영향을 받는다. 노드간 상호 연결망의 성능을 결정하는 요소로는 노드간 연결망의 형태 및 연결망을 구성하기 위해 채택된 스위칭 기법, 흐름 제어 정책, 메시지 전송 알고리즘 등을 들 수 있다. 고성능의 상호 연결망을 구성하기 위해서는 다른 요소들과 더불어 효율적인 전송 알고리즘의 개발이 필수적이다.
최근들어 고도의 처리능력을 요하는 응용 분야의 수요를 만족시키기 위해 많은 수의 노드를 포함하는 대규모 다중컴퓨터 시스템이 확산되는 추세에 있다. 하나의 다중컴퓨터 시스템에 포함되는 노드의 수가 증가함에 따라 그중 일부 노드 혹은 노드들을 연결하는 통신 채널이 고장을 일으킬 확률 또한 비례적으로 증가하게 된다. 이를 해결하기 위해 멀티 컴퓨터 시스템이 고장 허용성을 갖도록 하기 위한 다양한 방향의 연구가 진행되고 있으며 다중컴퓨터 시스템의 노드간 상호 연결망을 구성함에 있어서도 이러한 요구가 부각되고 있다. 노드간 상호 연결망이 고장허용성을 갖기 위해서는 메시지 전송 알고리즘이 고장 허용성을 갖도록 하는 것이 필수적이다. 메시지 전송 알고리즘이 고장 허용성을 갖는다는 것은 다중컴퓨터 시스템에 포함된 몇 개의 노드 혹은 채널들이 고장을 일으킨 상황에서도 정상적으로 작동되는 노드들 사이의 올바른 메시지 전송을 보장할 수 있어야 한다는 의미이다. 바람직한 고장 허용 메시지 전송 알고리즘은 다양한 고장 상황하에서 메시지의 올바른 전송을 보장해야 하며 고장 발생시와 정상의 상황 모두에서 높은 성능을 유지해야 한다. 또한 메시지 전송 알고리즘을 하드웨어로 구현 할 경우를 고려하면, 이러한 요구조건들을 만족시키기 위해 필요한 하드웨어의 양이 너무 과도하지 않아야 한다.
본 논문에서는 솔리드 고장 모델을 기반으로 하여 고장 허용성을 갖는 메시지 전송 알고리즘을 제안한다. 본 논문에서 제안된 메시지 전송 알고리즘은 메쉬형태를 가지며 웜홀(wormhole) 스위칭 기법을 채택한 상호 연결망에서 사용될 수 있다. 솔리드 고장 모델은 모든 경우의 볼록한 (convex)형태의 고장 영역과 오목한(concave)형태의 고장 영역중 많은 경우를 처리할 수 있다. 본 논문에서 제안된 고장 허용 전송 알고리즘은 고장 영역이 솔리드(solid)한 경우 고장이 발생한 노드 혹은 채널의 갯수와 무관하게 올바른 메시지 전송을 보장한다. 또한 고장영역들이 서로 겹쳐있는 경우나 고장 영역이 전송망의 가장자리의 노드를 포함하는 경우도 허용된다. 본 논문에서는 또한 오목한 형태의 고장 영역중 솔리드하지 않은 고장 영역이 발생한 경우를 해결하기 위해, 몇 개의 정상 노드를 불활성화(deactivate)함으로써 솔리드하지 않은 고장 영역을 솔리드한 고장 영역으로 변환하는 고장 영역 변환 알고리즘을 제안한다. 본 논문에서는 제안된 고장 허용 전송 알고리즘이 네 개의 가상 채널을 사용함으로써 전송되는 메시지가 교착상태 (deadlock) 및 영구 진행상태 (livelock)에 빠지지 않음을 증명하였다. 또한 제안된 전송 알고리즘을 현재의 상호 연결망의 상태에 따라 서로 다른 경로를 이용할 수 있는 적응성 (adaptivity)을 갖도록 확장하였으며 3차원 이상의 고차원 메쉬 연결망에도 적용할 수 있음을 보였다. 이러한 확장된 알고리즘들도 역시 네 개의 가상 채널만을 사용한다. 본 논문에서는 제안된 전송 알고리즘의 성능을 평가하기 위해 다양한 고장 상황하에서의 모의 실험을 수행하였다. 모의 실험을 통해 제안된 고장 허용 전송 알고리즘이 정상적인 상황에서 높은 성능을 가질 뿐만 아니라 고장 발생시 점진적인 성능 저하를 나타냄을 보였다. 또한 적은 갯수의 정상 노드를 불활성화 시킴으로써 솔리드하지 않은 고장 영역을 솔리드한 고장영역으로 변환할 수 있음을 보였다. 본 논문에서 제안된 고장 허용 전송 알고리즘은 적은 수의 가상 채널을 필요로 하며 비교적 간단한 전송 경로 결정 과정을 가지므로 쉽게 하드웨어 라우터로 구현되어 실제의 다중컴퓨터 시스템에 채택될 수 있을 것으로 기대된다.
