A Probe-based Deadlock Detection Mechanism in Wormhole Networks

S. Lee (Korea)


Wormhole Switching, Deadlock Detection, Deadlock Re covery, Adaptive Routing, Multiprocessors, Communica tion Networks


Deadlock recovery-based routing algorithms in wormhole networks have gained attraction due to low hardware com plexity and high routing adaptability. They detect dead lock mainly by using time-out mechanism and recover from deadlock by utilizing resources prepared for recov ery. However, their primary function of deadlock detection accompanies several disadvantages: Firstly, it is hard to de termine the time-out value for best performance under var ious 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 dead lock occurs, more than one message may be detected as deadlocked, which saturate the resources allocated for re covery. This paper proposes a more accurate deadlock de tection scheme which overcomes previous disadvantages. The proposed scheme reduces the probability of detecting false deadlocks considerably. Furthermore, a single mes sage is selected as deadlocked for each cycle of blocked messages, thereby eliminating recovery overheads.

Important Links:

Go Back