International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Blog/Latest News Contact Us
10th percentile
Powered by  Scopus
Scopus coverage:
Nov 2018 to May 2020


IJSTR >> Volume 8 - Issue 11, November 2019 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

An Efficient Directional Routing Algorithm For Network On Chip

[Full Text]



Venkateswara Rao Musala, Venkata Rama Krishna Tottempudi



Avg. Latency, Directional Routing Algorithm (DRA), Network-on-Chip (NoC), Resistance and Capacitance (RC), System on chip (SoC), Throughput .



Bus structures are commonly used in System on Chip (SoC) which needs a lot of wiring that causes an increase in Resistance and Capacitance (RC) of the framework in SoC. To avoid this an interconnection network called Network on Chip (NoC) is introduced for better communication in terms of latency and throughput among the processing cores in the vicinity of the selected network. It plays a major role to dress the issues in SoC. An on-chip routing resource is used to send the data packet based on routing decisions done in the router, which improves performance of interconnection fabric in terms of latency and throughput over resolute wiring and buses. Present routing algorithms in NoC experience a problem of channel load imbalance, which causes congestion in the routed path and effects the latency and throughput of the routed packet. This work proposes an adaptive routing resource fabric (Directional Routing Algorithm (DRA)) to avoid the congestive paths by identifying the unloaded path with the help of timeout piggybacking and load shedding, the DRA bypasses the congested path on the channel, based on direction specific traffic patterns. The proposed algorithm does better than Normal XY routing by 18% and 31% in terms of Avg.latency and throughput



[1] V. Rantala, T. Lehtonen, and J. Plosila, Network on chip routing algorithms: Citeseer, 2006.
[2] U. Y. Ogras, P. Bogdan, and R. Marculescu, "An analytical approach for network-on-chip performance analysis," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, pp. 2001-2013, 2010.
[3] E.-J. Chang, H.-K. Hsin, S.-Y. Lin, and A.-Y. Wu, "Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems," IEEE Transactions on computer-aided design of Integrated circuits and systems, vol. 33, pp. 113-126, 2013.
[4] S. Foroutan, Y. Thonnart, and F. Petrot, "An iterative computational technique for performance evaluation of networks-on-chip," IEEE Transactions on Computers, vol. 62, pp. 1641-1655, 2012.
[5] K. Yu-Hsin, T. Po-An, H. Hao-Ping, C. En-Jui, H. Hsien-Kai, and W. An-Yeu, "Path-Diversity-Aware Adaptive Routing in Network-on-Chip Systems," pp. 175-182, 2012.
[6] G.-M. Chiu, "The odd-even turn model for adaptive routing," IEEE Transactions on parallel and distributed systems, vol. 11, pp. 729-738, 2000.
[7] W. J. Dally and H. Aoki, "Deadlock-free adaptive routing in multicomputer networks using virtual channels," IEEE transactions on Parallel and Distributed Systems, vol. 4, pp. 466-475, 1993.
[8] P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh, "Performance evaluation and design trade-offs for network-on-chip interconnect architectures," IEEE transactions on Computers, vol. 54, pp. 1025-1040, 2005.
[9] K.-C. Chen, S.-Y. Lin, H.-S. Hung, and A.-Y. A. Wu, "Topology-aware adaptive routing for nonstationary irregular mesh in throttled 3D NoC systems," IEEE transactions on parallel and distributed systems, vol. 24, pp. 2109-2120, 2012.
[10] A. Singh, W. J. Dally, A. K. Gupta, and B. Towles, "GOAL: a load-balanced adaptive routing algorithm for torus networks," in Computer Architecture, 2003. Proceedings. 30th Annual International Symposium on, 2003, pp. 194-205.
[11] L. Schwiebert and R. Bell, "Performance Tuning of Adaptive Wormhole Routing through Selection Function Choice," Journal of Parallel and Distributed Computing, vol. 62, pp. 1121-1141, 2002.
[12] P.-T. Huang and W. Hwang, "An adaptive congestion-aware routing algorithm for mesh network-on-chip platform," in 2009 IEEE International SOC Conference (SOCC), 2009, pp. 375-378.
[13] E. Nilsson, M. Millberg, J. Oberg, and A. Jantsch, "Load distribution with the proximity congestion awareness in a network on chip," in 2003 Design, Automation and Test in Europe Conference and Exhibition, 2003, pp. 1126-1127.
[14] R. Oommen and J. Jose, "Congestion management in adaptive NoC routers using cost-effective selection strategies."
[15] J. Hu and R. Marculescu, "DyAD: smart routing for networks-on-chip," in Proceedings of the 41st annual Design Automation Conference, 2004, pp. 260-263.
[16] P. Gratz, B. Grot, and S. W. Keckler, "Regional congestion awareness for load balance in networks-on-chip," in 2008 IEEE 14th International Symposium on High Performance Computer Architecture, 2008, pp. 203-214.
[17] C. Wang, W.-H. Hu, and N. Bagherzadeh, "Congestion-aware Network-on-Chip router architecture," in 2010 15th CSI International Symposium on Computer Architecture and Digital Systems, 2010, pp. 137-144.
[18] J. Kim, D. Park, T. Theocharides, N. Vijaykrishnan, and C. R. Das, "A low latency router supporting adaptivity for on-chip interconnects," in Proceedings. 42nd Design Automation Conference, 2005., 2005, pp. 559-564.
[19] N. Aswathy, R. R. Raj, A. Das, J. Jose, and V. Josna, "Adaptive Packet Throttling Technique for Congestion Management in Mesh NoCs," in International Symposium on VLSI Design and Test, 2017, pp. 337-344.
[20] A. Singh, W. J. Dally, A. K. Gupta, and B. Towles, "GOAL: a load-balanced adaptive routing algorithm for torus networks," in 30th Annual International Symposium on Computer Architecture, 2003. Proceedings., 2003, pp. 194-205.
[21] F. Jafari, Z. Lu, A. Jantsch, and M. H. Yaghmaee, "Buffer optimization in network-on-chip through flow regulation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, pp. 1973-1986, 2010.
[22] N. Rohbani, Z. Shirmohammadi, M. Zare, and S.-G. Miremadi, "LAXY: A location-based aging-resilient Xy-Yx routing algorithm for network on chip," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 36, pp. 1725-1738, 2017.
[23] A. E. Kiasari, Z. Lu, and A. Jantsch, "An analytical latency model for networks-on-chip," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, pp. 113-123, 2012.
[24] R. S. Ramanujam and B. Lin, "Destination-based adaptive routing on 2D mesh networks," in Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2010, p. 19.
[25] L. Benini and G. De Micheli, "Networks on chip: A new paradigm for systems on chip design," in Proceedings 2002 Design, Automation and Test in Europe Conference and Exhibition, 2002, pp. 418-419.
[26] S. D. Chawade, M. A. Gaikwad, and R. M. Patrikar, "Review of XY routing algorithm for network-on-chip architecture," International Journal of Computer Applications, vol. 43, pp. 975-8887, 2012.
[27] P. Parandkar, J. Dalal, and S. Katival, "Performance Comparison of XY, OE and DY Ad Routing Algorithm by Load Variation Analysis of 2-Dimensional Mesh Topology Based Network-on-Chip," BIJIT Journal, vol. 4, pp. 391-396, 2012.
[28] A. Vitkovskiy, V. Soteriou, and C. Nicopoulos, "A highly robust distributed fault-tolerant routing algorithm for nocs with localized rerouting," in Proceedings of the 2012 Interconnection Network Architecture: On-Chip, Multi-Chip Workshop, 2012, pp. 29-32.
[29] V. Catania, A. Mineo, S. Monteleone, M. Palesi, and D. Patti, "Cycle-Accurate Network on Chip Simulation with Noxim," ACM Transactions on Modeling and Computer Simulation, vol. 27, pp. 1-25, 2016.