Next: Breaking Cycles Up: Routing Algorithms Previous: Dimension Order Routing

Determining Deadlock Freedom

Basic technique is to draw channel dependence graph and demonstrate that there are no cycles.

To derive channel dependence graph:

Dimension order routing for 4 node ring is deadlock free.

True for all k-ary n-cubes if k<5 (all hypercubes).

True for all meshes.



Paul H J Kelly Fri Apr 24 19:49:58 BST 1998