Performance analysis of minimal adaptive wormhole routing with time-dependent deadlock recovery

Deadlock recovery as a viable alternative to deadlock avoidance has recently gained an increasing consideration in the scientific community. In this paper we present a simple and efficient minimal adaptive wormhole routing algorithm that recovers from potential deadlocks. Rather than using a static or dynamic channel dependency graph, we remove from the network those packets that have stalled for more than a given timeout in a router. The experimental results, conducted on a 256 nodes bi-dimensional tones show that it is possible to find a timeout which is optimal for several communication patterns. Our algorithm provides good network latency, stable throughput above saturation and compares well with a deterministic and a minimal adaptive algorithm based on Duato´s methodology with the same number of virtual channels