A deadlock detection mechanism for true fully adaptive routing in regular wormhole networks

Different from traditional deadlock avoidance schemes, deadlock detection and recovery-based routing algorithms in wormhole networks have gained attention due to low hardware complexity and high routing adaptability. By its nature, current deadlock detection techniques based on time-out accompany unignorable number of false deadlock detections especially in a heavily loaded network or with long packet size and may mark more than one packet in a deadlock as deadlocked. This would saturate the resources allocated for recovery, making deadlock recovery schemes less viable. This paper proposes a simple but more accurate deadlock detection scheme which is less dependent on the time-out value. The proposed scheme uses a control packet to find a potential cyclic dependency between packets and presumes a deadlock only upon finding such dependency. The suggested scheme considerably reduces the probability of false deadlock detections over previous schemes, thus enabling more efficient deadlock recovery and higher network throughput. Simulation results are provided to demonstrate the efficiency of the proposed scheme.