A Polynomial Algorithm to Prove Deadlock-Freeness of Wormhole Networks

Deadlocks are an important issue in wormhole networks and a lot of works have been done on deadlock avoidance. Sufficient and necessary deadlock-freeness conditions have been proposed and used to build deadlock-free wormhole networks. But none of these works provide an efficient way to verify if a given network is deadlock-free. The present article proposes a new sufficient and necessary condition associated with a polynomial algorithm to check if a given network is deadlock-free. This new algorithm identifies escape paths from channels that are involved in circular dependencies. Identifying escape paths can be easily done by studying strongly connected components of the dependency graph instead of studying individually each cycle. The proposed algorithm has been implemented in a tool for automatic detection of deadlocks in wormhole networks (ODI). ODI has been used to establish the deadlock-freeness of complex realistic networks and networks with defective routers.