Message-passing multicomputers have been expected as the most promising way to construct massively parallel computers. The overall performance of these machines critically depends on the performance of the communication network to achieve the expected speedup and scalability. The communication networks of recently developed multicomputers have employed the oblivious wormhole routing strategy in which the cut-through switching technique makes the message latency insensitive to the distance traveled by a message, and the blocking flow control avoids using storage bandwidth in intermediate nodes where messages are routed. The combination of cut-through switching technique and the blocking flow control is called wormhole routing, and the network that adopts the wormhole routing technique is called wormhole-routed network. An important drawback of oblivious wormhole routing strategy is that the performance is seriously degraded due to the message contention that is caused by the deterministic routing algorithm when message injection rate is high and the traffic pattern is realistically non-uniform. And it is fault-intolerant to the node and channel failures. The adaptive routing has been expected as one of the best approaches to improve the network performance overcoming the message contention problem by utilizing available network bandwidth. In adaptive routing, multiple paths are provided for the messages and the selections are adaptively determined by local message congestion. Many adaptive routing strategies for wormholerouted networks have been developed. These strategies can be characterized by the number of additional virtual channels required to prevent deadlock, the degree of adaptiveness provided. All of the previous adaptive routing approaches restrict the adaptiveness to prevent the communication deadlock, and only a part of the shortest paths are permissible for the messages. This results in low utilization of the channels, hence low performance. In this thesis, two classes of adaptive routing strategies are developed for the wormhole-routed networks. One is restrictive routing and the other is restriction-free one. In the restrictive routing, the deadlock is prevented by routing restriction. We propose partially adaptive and fully adaptive routing algorithms for two-dimensional meshes. The proposed algorithms maximize the degree of adaptiveness by minimizing the routing restriction, and minimize the additional virtual channels required to prevent deadlock. In order to pursuit the restriction-free routing in wormhole-routed networks, a deadlock prevention scheme different from the routing restriction is needed. A flow control policy, called message cutting is developed for deadlock prevention, and deadlock-free adaptive routing strategies, called leader-following routing are proposed. Additive virtual channels can be used for performance enhancement. The performance of proposed adaptive routing strategies is evaluated by simulation. The simulation results show that increasing the adaptiveness contributes to the high performance of the routing strategy and nonminimal routing is useful for nonuniform traffic patterns.
컴퓨터 제조 기술의 눈부신 발전과 보다 높은 성능을 요구하는 응용 분야의 폭발적인 증대로 인하여 대규모 병렬 처리의 필요성이 대두되면서 병렬 컴퓨터 구조에 대한 많은 연구가 있 었다. 메시지 전송 방식의 다중컴퓨터는 확장성이 뛰어나 대규모 병렬 시스템을 구축하기가 용이한 구조로서 많은 연구가 활발히 진행되어 왔으며 산업용 및 연구용의 여러 시스템들이 구현된 바 있다. 메시지 전송 다중 컴퓨터는 각 노드 컴퓨터들이 통신망을 통하여 연결된 형태로서 통신망의 성능이 시스템의 전체 성능에 큰 영향을 미치며 통신망의 성능은 라우팅 전략에 따라 크게 좌우된다. 최근에 개발된 다중컴퓨터의 통신망은 훰홀 스위칭 기법을 채택함으로써 메시지 지연시간과 메시지 버퍼의 용량면에서 큰 개선을 가져왔으나 맹목적인 라우팅 알고리즘을 사용함으로써 잦은 메시지 충돌로 인하여 성능을 충분히 발휘하지 못하고 있으며 교착상태 방지를 위해 메시지 경로 선택을 제한함으로써 통신망이 제공하는 대역폭을 충분히 활용하지 못하고 있다. 적응 라우팅은 통신망의 성능을 개선하기 위한 대안으로 연구되는 라우팅 전략으로서, 맹목 라우팅 알고리즘이 출발지 목적지 사이에 단 하나의 경로만을 제공하는데 비해 적응 라우팅 알고리즘은 다수의 경로를 허용하고 목적지로 향하는 각 메시지들에게 중간노드의 국부적인 메시지 혼잡을 피하여 동적으로 메시지 경로를 배정함으로써 메시지간의 충돌을 줄이고 통신망이 제공하는 대역폭을 최대로 활용하고자 하는 방안이다. 웜홀 방식의 통신망을 위한 적응 라우팅 전략은 교착상태 방지에 드는 비용을 최소화하고 높은 성능을 위하여 다수의 메시지 경로를 제공하여야 하며 여러 통신망 연결구조에 적용 가능하여야 한다. 본 논문에서는 교착상태 방지를 위하여 최소한의 가상채널만을 사용하고, 메시지의 전달거리가 지연시간에 미치는 영향이 적은 웜홀 스위칭의 특성을 이용하여 비최단 경로도 허용 하면서 메시지 경로 제한을 최소화하는 세 가지 적응라우팅 전략을 제안하였다. 첫째는 2차원 메쉬를 위한 일부 적웅 라우팅 알고리즘으로써 추가적인 가상채널을 필요로 하지 않으며 출발지-목적지 간의 모든 최단거리 경로 중 일부만을 허용하는 라우팅 알고리즘이다. 둘째는 2차원 메쉬를 위한 완전 적응 라우팅 알고리즘으로써 한 차원의 양방향 및 음방향의 채널에 각각 하나의 가상채널만을 추가하고 출발지-목적지 간의 모든 최단거리 경로를 허용하는 라우팅 알고리즘이다. 세째는 임의의 통신망 연결구조에 적용 가능한 무제한 적응 라우팅 알고리즘으로써 본 논문에서 제안한 메시지 업합이라는 새로운 교착상태 방지 기법을 통하여 교착상태를 방지하고 추가되는 가상채널은 아무런 제한 없이 사용될 수 있는 라우팅 알고리즘이다. 제안한 적응라우팅 알고리즘들의 성능을 평가하기 위하여 시뮬레이션을 통하여 통신망의 크기, 가상채널의 수, 메시지의 길이, 메시지 주입율, 트래픽 패턴 등의 변화에 따른 성능 평가 실험을 하였으며 실험 결과 본 논문에서 제안한 적응라우팅 알고리즘들은 맹목 라우팅 알고리즘에 비해 비균등 트래픽 패턴에서 괄목할 만한 성능개선을 보였으며 집중 트래픽의 경우 비최단 라우팅이 최단 라우팅에 비해 성능 개선 효과가 있음을 입증하였다.
