Real-time flow control policies in wormhole-routed interconnect networks

Abstract

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 fr...