Journal Press India^®

Author Details ( * ) denotes Corresponding author

Deadlocks are an important issue in the design and analysis of communication networks. Wormhole switching is a popular switching technique in direct networks. It refers to a simple flow control system in computer network that is primarily based on fixed links. It also reduces the latency and storage requirements on each node. Deadlock analysis of routing function is a manual and complex task. In the absence of contention, latencies are proportional to the sum of the packet length and the distances to travel. We propose an algorithm to analyze the deadlock in communication networks. The deadlock-free routing algorithm is the first to automatically check a necessary and sufficient condition for deadlock-free routing. Our algorithm performs Effective analysis in this network.

Keywords

Deadlocks; Routing Algorithm; Communication Networks; Wormhole Switching

1. W. J. Dally, C. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Trans. Comput., 36(5), 1987, 547-553.


2. J. Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Trans. Parallel Distrib. Syst., 6(10), 1995, 1055-1067


3. J. Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Trans. Parallel Distrib. Syst., 4(12), 1993, 1320-1331.


4. C. Grecu, Rusu, A Flexible Network-on-Chip Simulator for Early Design Space Exploration, IEEE transactions on Microsystems and Nano Electronics Research Conference, 7(2), 2008


5. C. J. Glass, L. M. Ni, The Turn Model for Adaptive Routing, J. ACM, 41(5), 1994, 874-902


6. M. Kaufmann, P. Manolios, J. S. Moore, ACL2 Computer-Aided Reasoning: An Approach. Dordrecht, The Netherlands: Kluwer, 2011


7. W. Luo, D. Xiang, An Efficient Adaptive Deadlock-FreeRouting Algorithm for Torus Networks, IEEE Trans. Parallel Distrib. Syst., 23(5), 2012, 800-808


8. Sheng Ma, Natalie Enright Jerger, Whole Packet Forwarding: Efficient Design of Fully Adaptive Routing Algorithms for Networks-on-Chip, IEEE International Symposium on High Performance Computer Architecture, 2012


9. F. Verbeek, J. Schmaltz, A Comment on ‘A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Trans. Parallel Distrib. Syst., 22(10), 2011, 1775-1776


10. F. Verbeek, J. Schmaltz, On Necessary and Sufficient Conditions for Deadlock-Free Routing in Wormhole Networks, IEEE Trans. Parallel Distrib. Syst., 22(12), 2011, 2022-2032


11. F. Verbeek, J. Schmaltz, Automatic Verification for Deadlock in Networks-on-Chips with Adaptive Routing and Wormhole Switching, IEEE NOCS, 2011, 25-32


12. F. Verbeek, J. Schmaltz, Formal Verification of a Deadlock Detection Algorithm, 10th Int. Workshop ACL2 Theorem Prover Appl., 2011, 103-112


13. Zaheer Ahmed, A Fault Adaptive Routing, J. ACM, 41(5), 2009, 874-902.


14. Zhonghai Lu, Layered switching for networks on chip, IEEE Trans. Parallel Distrib. Syst., 22(10), 2011, 1775-1776