| In recent years, a large number of deadlock avoidance and recovery-based routing approaches have been proposed for regular and irregular interconnection networks. These approaches have been proposed without the benefit of fully understanding many factors regarding the likelihood and characteristics of actual deadlocks. The work presented in this thesis characterizes deadlocks and message blocking in a wide class of interconnection networks in order to provide information that can be useful towards making optimal trade-offs between routing restrictions, deadlock freedom, network resource utilization, and performance when building high-performance interconnection networks.; This work provides insight into the relationships between various network properties, deadlock, and other forms of correlated message blocking and, through empirical study, shows how various network parameters influence deadlock and message blocking frequency and characteristics for both regular and irregular interconnection networks. Techniques for reducing a network's susceptibility to deadlock are demonstrated and design guidelines for building networks which maximize routing flexibility and resource utilization are provided.; This work also presents a theoretical model of resource allocation and dependencies within wormhole and virtual cut-through interconnection networks which allows various types of message blocking to be described precisely, including deadlock. The model defines the necessary and sufficient conditions for the existence and resolution of deadlock, thus providing minimal criteria for deadlock detection and recovery for routing algorithms based on deadlock recovery. The model constitutes a framework for evaluating the correctness, accuracy, and efficiency of proposed deadlock detection and recovery routing schemes and provides insight useful towards developing improved deadlock detection and resolution schemes for deadlock recovery-based routing approaches. |
