A Necessary and Sufficient Condition for Deadlock-Free Wormhole Routing
Abstract
An important open problem in wormhole routing has been to find a
necessary and sufficient condition for deadlock-free adaptive routing.
Recently, Duato has solved this problem for a restricted class of
adaptive routing algorithms. In this paper, a necessary and
sufficient condition is proposed that can be used for any adaptive or
nonadaptive routing algorithm for wormhole routing, as long as only
local information is required for routing. The underlying proof
technique introduces a new type of dependency graph, the channel
waiting graph, which omits most channel dependencies that cannot
be used to create a deadlock configuration. The necessary and
sufficient condition can be applied in a straightforward manner to
most routing algorithms. This is illustrated by proving deadlock
freedom for a partially adaptive nonminimal mesh routing algorithm
that does not require virtual channels and a fully adaptive minimal
hypercube routing algorithm with two virtual channels per physical
channel. Both routing algorithms are more adaptive than any
previously proposed routing algorithm with similar virtual channel
requirements.
Return to the Publication list.
Last updated by Loren Schwiebert Email: 
on Jun-06-2001