Level Based Routing Using Dynamic Programming for 2D Mesh

Punhani, Akash; Kumar, Pardeep; Nitin, Nitin

doi:10.1515/cait-2017-0017

Abstract

The performance of the interconnection network doesn’t only depend on the topology, but it also depends on the Routing algorithm used. The simplest Routing algorithm for the mesh topology in networks on chip is the XY Routing algorithm. The level based Routing algorithm has been proved to be more efficient than the XY Routing algorithm. In this paper, level based Routing algorithm using the dynamic programming has been proposed. The proposed Routing algorithm proves to be more efficient in the terms of the computation. The proposed Routing algorithm has achieved up to two times bigger speed.

References

1. Dally, W. J., B. Towels. Principle and Practices of Interconnection Networks. Elsevier, 2004.
Search in Google Scholar Back to article
2. Duato, J., S. Yalamanchili, L. Ni. Interconnection Networks. Elsevier, 2003.
Search in Google Scholar Back to article
3. Palesi, M., M. Daneshtalab. Routing Algorithms in Networks-on-Chip. Berlin, Springer, 2014.10.1007/978-1-4614-8274-1
Search in Google Scholar Back to article
4. Bhardwaj, V. P., R. V. Nitin. On the Minimization of Crosstalk Conflicts in a Destination Based Modified Omega Network. – Journal of Information Processing Systems, Vol. 9, 2013, No 3, pp. 301-314.10.3745/JIPS.2013.9.2.301
Search in Google Scholar Back to article
5. Nitin, R. V., U. Srivastava. On a Deadlock and Performance Analysis of ALBR and DAR Algorithm on X-Torus Topology by Optimal Utilization of Cross Links and Minimal Lookups. – Journal of Supercomputing, Vol. 59, 2010, No 3, pp. 1252-1288.10.1007/s11227-010-0524-x
Search in Google Scholar Back to article
6. Nitin, R. V., D. S. Chauhan. Stochastic Communication for Application Specific Networks-on-Chip. – Journal of Supercomputing, Vol. 59, 2010, No 2, pp. 779-810.10.1007/s11227-010-0472-5
Search in Google Scholar Back to article
7. Nitin, R. V., S. Garhwal, N. Srivastava. Designing a Fault-Tolerant Fully-Chained Combining Switches Multi-Stage Interconnection Network with Disjoint Paths. – Journal of Supercomputing, Vol. 55, 2009, No 3, pp. 400-431.10.1007/s11227-009-0336-z
Search in Google Scholar Back to article
8. Yu-Hang, L., Z. Ming Fa, W. Jue, Li-Min Xiao, G. Tao. X-Torus: An Extended Torus Topology for On-Chip Massive Data Communication. – In: Proc. of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW’12), 2012, pp. 2061-2068.
Search in Google Scholar Back to article
9. Hu, W. H., S. E. Lee, N. Bagherzadeh, Z. Xiao-Jing, H. Wei-Wu, M. Ke, Z. Long-Bing. X-Mesh: A Mesh-Like Topology for Network on Chip. – Network. Chip Architecture, 2008, p. 14.
Search in Google Scholar Back to article
10. Wang, Y., H. Du, X. Shen. Topological Properties and Routing Algorithm for Semi-Diagonal Torus Networks. – J. China Univ. Posts Telecommunication, Vol. 18, 2011, No 5, pp. 64-70.10.1016/S1005-8885(10)60105-7
Search in Google Scholar Back to article
11. Arora, L. K., Rajkumar. C2-Mesh. – In: Proc. of 3rd IEEE International Advance Computing Conference (IACC’13), 2013, pp. 282-286.
Search in Google Scholar Back to article
12. Yadav, S., C. R. Krishna. CC-Torus: A New Torus Topology for Interconnection Networks. – In: Proc. of International Conference on Advanced Computational Technologies & Creative Media (ICACTCM’14), 2014, pp. 14-15.
Search in Google Scholar Back to article
13. Manish, Bhardwaj. C2-Torus New Interconnection Network Topology Based on 2D Torus, American. – Journal of Network Communication, Vol. 4, 2015, No 3, pp. 1-4.10.11648/j.ajnc.s.2015040301.11
Search in Google Scholar Back to article
14. Punhani, C. A., R. V. Nitin, P. Kumar. A Modified Diagonal Mesh Interconnection Network. – In: Annual IEEE India Conference (INDICON’14), 2014, pp. 1-6.10.1109/INDICON.2014.7030606
Search in Google Scholar Back to article
15. Punhani, C. A., P. Kumar, R. V. Nitin. Diagonal Connected T-Mesh. – Indian Journal of Science and Technology, Vol. 9, 2016, No 32.10.17485/ijst/2016/v9i32/100219
Search in Google Scholar Back to article
16. Punhani, C. A., R. V. Nitin. EMC2-Mesh. – In: Annual IEEE Conference (INDICON’15), India, 2015, pp. 1-5.
Search in Google Scholar Back to article
17. Nitin, R. V., D. S. Chauhan. Comparative Analysis of Traffic Patterns on k-Ary n-Tree Using Adaptive Algorithms Based on Burton Normal Form. – Journal of Supercomputing, Vol. 59, 2010, No 2, pp. 569-588.10.1007/s11227-010-0454-7
Search in Google Scholar Back to article
18. Mejia, M. Palesi, J. Flich, S. Kumar, P. Lopez, R. Holsmark, J. Duato. Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs. – IEEE Trans. Very Large Scale Integration of Systems, Vol. 17, 2009, No 3, pp. 356-369.10.1109/TVLSI.2008.2012010
Search in Google Scholar Back to article
19. Chiu, G. M. The Odd-Even Turn Model for Adaptive Routing. – IEEE Trans. Parallel Distributed Systems, Vol. 11, 2000, No 7, pp. 729-738.10.1109/71.877831
Search in Google Scholar Back to article
20. Glass, J., L. M. Ni. The Turn Model for Adaptive Routing. – In: Proc of 19th Annual International Symposium on Computer Architecture, 1992, pp. 278-287.10.1145/146628.140384
Search in Google Scholar Back to article
21. Arora, L. K., R. Kumar. Alternatives of XY-Routing for Mesh. – In: Special Issue of International Journal of Computer Application ICNICT, 2012, pp. 6-8.
Search in Google Scholar Back to article

Level Based Routing Using Dynamic Programming for 2D Mesh

Abstract

Paradigm

My account