Deadlock recovery-based router architectures for high performance networks

Multiprocessor systems have been developed to efficiently solve complex and large scientific problems. Generally, these systems have a critical component, i.e., interconnection network, which significantly affects system performance by determining the communication capability of multiprocessor systems. In recent years, with the emergence of bandwidth-hungry applications and multi-GHz processors, the demand on high performance interconnection networks has been increased to meet rapidly growing communication needs of multiprocessor systems.; To satisfy this demand, routing algorithms must fully utilize network resources while efficiently handling message deadlock which leads to the halting of an entire system. There are largely two classes of routing algorithms according to the way deadlocks can be dealt: deadlock avoidance-based and deadlock recovery-based routing algorithms. Deadlock avoidance-based networks prevent deadlocks by enforcing routing restrictions, which hampers routing adaptivity and, therefore, limits network performance. To overcome this problem, recently a number of deadlock recovery-based networks have been proposed, which maximize routing adaptivity and, thus, significantly increase network performance. But, the increased routing adaptivity could lead to slower and more complicated router architectures, degrading overall network performance.; In order to minimize the architecture complexity of deadlock recovery-based routers and to maximize network performance, this dissertation optimizes deadlock recovery-based router architectures by proposing two router component design solutions, i.e., partitioned crossbar designs and enhanced dynamically allocated multi-queue designs. These solutions significantly reduce the architecture complexity of deadlock recovery-based routers while fully benefiting from their capability, leading to optimal deadlock recovery-based router architectures.; Through extensive evaluations of various router architectures, this dissertation verifies that the true fully adaptive routing capability of deadlock recovery schemes can be efficiently implemented in routers and, hence, their superior network performance can be realized. Finally, this work demonstrates the feasibility of some of the proposed router architectures by implementing the WARRP router.