Deadlock prevention by turn prohibition in interconnection networks
Authors:
- 1 May 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
In this paper we consider the problem of constructing minimal cycle-breaking sets of turns for graphs that model communication networks, as a method to prevent deadlocks in the networks. We present a new cycle-breaking algorithm called simple cycle-breaking or SCB algorithm that is considerably simpler than earlier algorithms. The SCB algorithm guarantees that the fraction of prohibited turns does not exceed 1/3. Experimental simulation results for the SCB algorithm are shown.Keywords
This publication has 9 references indexed in Scilit:
- A New Algorithm for Finding Minimal Cycle-Breaking Sets of Turns in a GraphJournal of Graph Algorithms and Applications, 2006
- Application of network calculus to general topologies using turn-prohibitionIEEE/ACM Transactions on Networking, 2003
- Tree-based multicasting in wormhole-routed irregular topologies2002
- A general theory for deadlock avoidance in wormhole-routed networksIEEE Transactions on Parallel and Distributed Systems, 1998
- Resource deadlocks and performance of wormhole multicast routing algorithmsIEEE Transactions on Parallel and Distributed Systems, 1998
- The turn model for adaptive routingJournal of the ACM, 1994
- A survey of wormhole routing techniques in direct networksComputer, 1993
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987