Multicomputers and scalable clusters of low-end PCs/workstations have been expected as the most promising vehicle for high-performance computing. Whereas high-performance power in the past was dedicated for large-scale computation intensive applications, recent high-performance computing from multicomputers and scalable clusters has been exploited for a broad range of new service such as multimedia processing, data mining, and industrial process control. Unlike traditional supercomputing applications which desire a better system performance in an average sense, the new service requires another performance criteria in terms of quality of service(QoS). With QoS being a different definition for each application, we in this thesis focus on timing correctness which requires logically correct results to be generated within a specified deadline for real-time application with delay sensitive traffic such as multimedia service, automated manufacturing, and industrial process control. Since the overall performance of multicomputers and scalable clusters critically depends on the performance of their interconnect networks, efforts are made in this thesis to make their interconnect networks to satisfy the new criteria.
Most of recent interconnect networks have employed a wormhole routing technique, since it makes the message latency insensitive to the distance travelled by a message and it can be implemented by a small, high-speed router with a current VLSI technology. Wormhole-routed networks can be characterized by its blocking flow control in which a packet to fail to acquire a desired channel is just stopped in place. Assuming a priority-driven paradigm where a different level of delay requirement of a real-time message is represented into an appropriate priority, the blocking flow control may directly lead to a priority inversion problem in the sense that high priority packets are blocked by low priority packets for unlimited time. The priority inversion causes the frequent deadline missing even at a low network load and system unpredictable.
In this thesis, applying a technique of preemption to wormhole routing instead of blocking, we propose two preemptive flow controls, simple preemptive flow control and throttle and preempt flow control, which make a high priority packet preempt network resources from a low priority packet. Especially, the throttle and preempt flow control prohibits low priority packets from using input buffers beyond their allowed limit, hence, high priority packets can be guaranteed to immediately preempt desired resources without priority inversion. The performance of proposed flow controls are evaluated by simulations. The simulation results show that the conventional blocking flow control does not satisfy the timing property of real-time applications. Also, it is observed that the proposed flow controls offer low deadline miss ratios compared to existing real-time flow control under various conditions where the real-time traffic coexists with the best-effort traffic.
병렬컴퓨터와 저가의 PC군으로 구성된 클러스터 시스템은 고성능 컴퓨터를 구성하는 가장 유망한 방법 중의 하나로 여겨지고 있다. 과거의 고성능 컴퓨터들이 방대한 계산을 요구하는 공학응용프로그램을 위해서 주로 사용된 데 반해서, 현재의 고성능 컴퓨터는 멀티미디어 서비스, 산업 공정 제어, 데이타 베이스 처리등의 광범위한 응용분야에 사용되고 있다. 따라서, 과거의 고성능 컴퓨터들이 평균적인 의미의 성능으로 평가된 것과는 달리, 현대의 고성능 컴퓨터들은 각 응용프로그램이 요구하는 서비스의 질을 얼마나 만족시켜 줄 수 있느냐로 평가되어야 한다. 서비스의 질이란 응용프로그램에 따라 달리 정의될 수 있으나, 본 논문에서는 멀티미디어 서비스 등의 제한시간을 갖는 실시간 응용프로그램이 급증하고 있는 사실을 고려하여, 시간 만족도(timing correctness)라는 서비스의 질에 촛점을 맞추었다. 또한, 고성능 컴퓨터의 성능은 그 상호연결망의 성능에 의해서 크게 좌우되므로, 본 논문에서는 실시간 메세지에 대해서 시간 만족도를 제공하기 위한 상호연결망을 설계하였다.
현재의 고성능 컴퓨터의 상호연결망은 대부분 웜홀 라우팅 기법을 채택하고 있다. 이는 웜홀 라우팅 기법이 메세지의 전달 지연 시간을 감소시켜 줄 수 있으며 웜홀 네트워크를 구성하는 각 라우터가 현재의 VLSI 기술을 고려할 때 손쉽게 구현될 수 있기 때문이다. 웜홀 라우팅의 가장 큰 특징은 봉쇄 흐름제어 정책을 쓴다는데 있다. 봉쇄 흐름제어 정책이란, 하나의 메시지가 원하는 채널을 획득하지 못하는 경우에 네트워크에서 봉쇄된 채로 원하는 채널이 사용가능해질때까지 기다리는 것을 말한다. 서로 다른 제한시간을 갖는 실시간 메세지들은 긴급성에 따라서 서로 다른 우선순위를 갖게 되는데, 봉쇄 흐름제어 정책에 의해서 높은 우선순위의 메세지가 낮은 우선순위의 메세지에 의해서 무제한 시간동안 봉쇄되는 경우가 발생할 수 있다. 이러한 우선 순위 전도현상은 시스템을 예측 불가능하게 만들기 때문에, 네트워크의 부하가 낮을 때도 메세지들이 제한시간을 지키지 못하는 경우가 빈번하게 발생한다.
본 논문에서는 봉쇄흐름제어 정책 대신에, 실시간 메세지들을 위해 선점 흐름제어 정책을 제안하였다. 제안한 기본선점 흐름제어 정책(Simple Preemptive Flow Control)과 통제 및 선점 흐름 제어 정책(Throttle and Preempt Flow Control)에 의해서, 높은 우선 순위의 메세지들은 낮은 우선순위의 메세지들이 차지한 채널을 선점하여 계속 전진하게 된다. 특히, 통제 및 선점 흐름 제어 정책은 낮은 우선순위의 메세지들이 각 중간 라우터의 버퍼를 사용하는데 제한을 두어서, 높은 우선순위의 메세지가 채널을 선점하려고 할 때 버퍼의 남아있는 공간을 활용하여 언제라도 선점할 수 있도록 하였다. 따라서, 통제 및 선점 흐름 제어 정책에서 우선순위전도 현상은 발생하지 않게 된다. 제안한 두개의 선점흐름제어 정책들의 성능은 모의실험에 의해서 평가되었는데, 두 개의 선점흐름제어 정책들은 봉쇄 흐름제어 정책이나 기존 실시간 메세지들을 위한 흐름제어 정책에 비해서, 시간 만족도면에서 괄목할 만한 성능개선 효과가 있음이 입증되었다.
