A PROBE-BASED DEADLOCK DETECTION MECHANISM IN WORMHOLE NETWORKS

摘要

Deadlock recovery-based routing algorithms in wormhole networks have gained attraction due to low hardware complexity and high routing adaptability. They detect deadlock mainly by using time-out mechanism and recover from deadlock by utilizing resources prepared for recovery. However, their primary function of deadlock detection accompanies several disadvantages: Firstly, it is hard to determine the time-out value for best performance under various traffic patterns or packet length; Secondly, many false deadlocks may be detected especially in a heavy-loaded network or with long message size; Thirdly, when a deadlock occurs, more than one message may be detected as deadlocked, which saturate the resources allocated for recovery. This paper proposes a more accurate deadlock detection scheme which overcomes previous disadvantages. The proposed scheme reduces the probability of detecting false deadlocks considerably. Furthermore, a single message is selected as deadlocked for each cycle of blocked messages, thereby eliminating recovery overheads.