INTRODUCING A NEW ROUTING ALGORITHM FOR WIRELESS NETWORKS ON CHIP USING REINFORCEMENT LEARNING


(Received: 16-Apr.-2021, Revised: 13-Jun.-2021 , Accepted: 3-Jul.-2021)
Wireless network on chip (WNoC) can be used as an alternative to bus technology in high-core chips in which the multi-hop paths between far apart cores are replaced with a wireless single-hop link. The main reason for using wireless communication is to reduce latency as well as power consumption. According to the limitation of resources, the performance of the WNoC is sensitive to the routing algorithm. While an appropriate routing algorithm reduces latency, it should avoid deadlock. In this paper, we propose a novel routing algorithm using Q- learning, which is one of the reinforcement learning methods for balancing wireless network traffic on the chip. Using such an algorithm, the nodes can make decisions based on congestion conditions in the network when transferring flits from the source node to the destination one. The simulation results show that using the proposed reinforcement learning for routing the packets considerably improves the performance of the network; more precisely, the system performance is improved by 8% compared with the previous related works.

[1] S. Kundu and S. Chattopadhyay, Network-on-Chip: The Next Generation of System-on-Chip Integration, Taylor & Francis, 2014.

[2] R. Venugopalan, S. Kumar Goel and Y.-H. Lee, "Network-on-Chip System and a Method of Generating the Same," U.S. Patent Application 16/879,567, Filed September 3, 2020.

[3] A. Ganguly, K. Chang, S. Deb, P. Pratim Pande, B. Belzer and C. Teuscher, "Scalable Hybrid Wireless Network-on-Chip Architectures for Multicore Systems," IEEE Transactions on Computers, vol. 60, no. 10, pp. 1485-1502, 2010.

[4] J. Flich, S. Rodrigo and J. Duato, "An Efficient Implementation of Distributed Routing Algorithms for NoCs," Proc. of the 2nd ACM/IEEE Int. Symposium on Networks-on-Chip (NOCs 2008), pp. 87-96, 2008.

[5] Z. Mogharrabi-Rad and E. Yaghoubi, "ADFT: An Adaptive, Distributed, Fault-tolerant Routing Algorithm for 3D Mesh-based Networks-on-Chip," International Journal of Internet Technology and Secured Transactions, vol. 10, no. 4, pp. 481-490, 2020.

[6] R. Bishnoi, "Hybrid Fault Tolerant Routing Algorithm in NoC," Perspectives in Science, vol. 8, pp. 586-588, 2016.

[7] S. Mubeen and S. Kumar, "Designing Efficient Source Routing for Mesh Topology Network on Chip Platforms," Proc. of the 13th IEEE Euromicro Conference on Digital System Design: Architectures, Methods and Tools, pp. 181-188, 2010.

[8] Z.-S. Chen, Y. Zhang, Z. Peng and J.-H. Jiang, "A Deterministic-path Routing Algorithm for Tolerating Many Faults on Wafer-level NoC," In IEEE Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 1337-1342, Florence, Italy, 2019.

[9] T. A. Eltaras, W. Fornaciari and D. Zoni. "Partial Packet Forwarding to Improve Performance in Fully Adaptive Routing for Cache-coherent NoCs," Proc. of the 27th IEEE Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), pp. 33-40, Pavia, Italy, 2019.

[10] M. M. Rahaman, P. Ghosal and T. Subhra Das, "Latency, Throughput and Power Aware Adaptive NoC Routing on Orthogonal Convex Faulty Region," Journal of Circuits, Systems and Computers, vol. 28, no. 04, DOI: 10.1142/S0218126619500555, 2019.

[11] M. Sun, Q. Liu, B. Yan and X. Wang, "Minimally Buffered Router and Deflection Routing Algorithm for 3D Mesh NoC," Proc. of Recent Developments in Intell. Computing, Communication and Devices, Part of the Advances in Intelligent Systems and Computing Book Series, vol. 752, pp. 515-522, 2019.

[12] M. Schoeberl, L. Pezzarossa and J. Sparsø, "A Minimal Network Interface for a Simple Network-on-Chip," Proc. of the International Conference on Architecture of Computing Systems (ARCS 2019), Part of the Lecture Notes in Computer Science Book Series, vol. 11479, pp. 295-307, 2019.

[13] Song, Yang and Bill Lin. "Uniform Minimal First: Latency Reduction in Throughput-optimal Oblivious Routing for Mesh-based Networks-on-Chip." IEEE Embedded Systems Letters, vol. 11, no. 3, pp. 81-84, 2019.

[14] L. Wang, X. Wang, H.-F. Leung and T. Mak, "A Non-minimal Routing Algorithm for Aging Mitigation in 2D-mesh NoCs," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 38, no. 7, pp. 1373-1377, 2018.

[15] K.-C. Chen, "Game-based Thermal Delay-aware Adaptive Routing (GTDAR) for Temperature-aware 3D Network-on-Chip Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 9, pp. 2018-2032, 2018.

[16] W. Zhang and Y. Ye, "A Table-free Approximate Q-learning Based Thermal-aware Adaptive Routing for Optical NoCs," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 40, no. 1, pp. 199-203, 2020.

[17] Y. Ye, W. Zhang and W. Liu, "Thermal-aware Design and Simulation Approach for Optical NoCs," IEEE Trans. on Computer-aided Design of Integrated Circuits and Sys., vol. 39, no. 10, pp. 2384 – 2395, 2019.

[18] N. Shahabinejad and H. Beitollahi, "Q-thermal: A Q-learning Based Thermal-aware Routing Algorithm for 3D Network On-Chips," IEEE Transactions on Components, Packaging and Manufacturing Technology, vol. 10, no. 9, pp. 1482 – 1490, 2020.

[19] T. H. Vu, O. M. Ikechukwu and A. Ben Abdallah, "Fault-tolerant Spike Routing Algorithm and Architecture for Three Dimensional NoC-based Neuromorphic Systems," IEEE Access, vol. 7, pp. 90436-90452, DOI: 10.1109/ACCESS.2019.2925085, 2019.

[20] Y.-Y. Chen, E.-J. Chang, H.-K. Hsin, K.-C. Chen and A.-Y. Wu, "Path Diversity-aware Fault-tolerant Routing Algorithm for Network-on-Chip Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 3, pp. 838-849, 2016.

[21] J. Zhou, H. Li, T. Wang and X. Li, "LOFT: A Low-overhead Fault-tolerant Routing Scheme for 3D NoCs," Integration, vol. 52, pp. 41-50, 2016.

[22] Y. Kurokaw and M. Fukushi, "Passage of Faulty Nodes: A Novel Approach for Fault-tolerant Routing on NoCs," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 102, no. 12, pp. 1702-1710, 2019.

[23] R. S. Sutton, "Introduction: The Challenge of Reinforcement Learning," Proc. of Reinforcement Learning, Part of the Springer International Series in Engineering and Computer Science Book Series, vol. 173, pp. 1-3, Springer, Boston, MA, USA, 1992.

[24] S. Mahadevan, "Average Reward Reinforcement Learning: Foundations, Algorithms and Empirical Results," Machine Learning, vol. 22, no. 1-3, pp. 159-195, 1996.

[25] C. J. Watkins and P. Dayan, "Q-learning," Machine learning, vol. 8, no. 3-4, pp. 279– 292, 1992.

[26] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, P. Liljeberg and J. Plosila, "Q-learning Based Congestion-aware Routing Algorithm for on-chip Network," Proc. of the 2nd IEEE International Conference on Networked Embedded Systems for Enterprise Applications, pp. 1-7, Perth, WA, Australia, 2011.

[27] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, J. Plosila and P. Liljeberg, "Adaptive Reinforcement Learning Method for Networks-on-Chip," Proc. of the IEEE International Conference on Embedded Computer Systems (SAMOS), pp. 236-243, Samos, Greece, 2012.

[28] S.-C. Kao, C.-H. Huck Yang, P.-Y. Chen, X. Ma and T. Krishna, "Reinforcement Learning Based Interconnection Routing for Adaptive Traffic Optimization," Proceedings of the 13th IEEE/ACM International Symposium on Networks-on-Chip, pp. 1-2, DOI: 10.1145/3313231.3352369, 2019.

[29] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, J. Plosila and P. Liljeberg, "Optimized Q-learning Model for Distributing Traffic in on-chip Networks," Proc. of the 3rd IEEE International Conference on Networked Embedded Systems for Every Application (NESEA), pp. 1-8, Liverpool, UK, 2012.

[30] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, P. Liljeberg and J. Plosila, "Bi-LCQ: A Low-weight Clustering-based Q-learning Approach for NoCs," Microprocessors and Microsystems, vol. 38, no. 1, pp. 64-75, 2014.

[31] S. Sakamoto, R. Obukata, T. Oda, L. Barolli, M. Ikeda and A. Barolli, "Performance Analysis of Two Wireless Mesh Network Architectures by WMN-SA and WMN-TS Simulation Systems," Journal of High Speed Networks, vol. 23, no. 4, pp. 311-322, 2017.

[32] R. Mohammadi and H. Boroumand Noghabi, "SAT: Simulated Annealing and Tabu Search Based Routing Algorithm for Wireless Sensor Networks," International Journal of Computer Networks and Communications Security, vol. 4, no. 10, Paper ID: 286, 2016.

[33] A. Norollah, D. Derafshi, H. Beitollahi and A. Patooghy, "PAT-Noxim: A Precise Power & Thermal Cycle-accurate NoC Simulator," Proc. of the 31st IEEE International System-on-Chip Conference (SOCC), pp. 163-168, Arlington, VA, USA, 2018.

[34] V. A. M. Catania, S. Monteleone, M. Palesi and D. Patti, "Noxim: An Open, Extensible and Cycle-accurate Network on Chip Simulator," Proc. of the 26th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), pp. 162-163, Toronto, Canada, 2015.

[35] S. Khan, S. Anjum, U. Ali Gulzari and F. Sill Torres, "Comparative Analysis of Network-on-Chip Simulation Tools," IET Computers & Digital Techniques, vol. 12, no. 1, pp. 30-38, 2017.

[36] I. L. P. Pires, M. A. Z. Alves and L. C. P. Albini, "Trace-driven and Processing Time Extensions for Noxim Simulator," Design Automation for Embedded Systems, vol. 23, no. 1-2, pp. 41-55, 2019.

[37] M.-H. Tang and L. I. N. Jing, "A Quantitative Study on NoC Traffic Scenarios," DEStech Transactions on Computer Science and Engineering, DOI: 10.12783/dtcse/iece2018/26648, 2018.

[38] S. Jog, Z. Liu, A. Franques, V. Fernando, H. Hassanieh, S. Abadal and J. Torrellas, "Millimeter Wave Wireless Network on Chip Using Deep Reinforcement Learning," ACM Conf. on Special Interest Group on Data Communication (SIGCOMM'20 posters/demos), p. 1-3, DOI 10.1145/3405837.3411396, 2020.

[39] Z. Li and Y. Li, "Use Deep Reinforcement Learning for NoC Design," [Online], Available: https://aml-2020.aminer.cn/proposal/ZhiyaoLi_YiweiLi.pdf, 2020.

[40] T.-R. Lin, D. Penney, M. Pedram and L. Chen, "A Deep Reinforcement Learning Framework for Architectural Exploration: A Routerless NoC Case Study," Proc. of the IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 99-110, San Diego, CA, USA, 2020.

[41] S. Deb and H. Kumar Mondal, "Wireless Network-on-Chip: A New ERA in Multi-core Chip Design," Proc. of the 25th IEEE Int. Symposium on Rapid System Prototyping, pp. 59-64, New Delhi, India, 2014.

[42] A. Ganguly, K. Chang, S. Deb, P. P. Pande, B. Belzer and C. Teuscher, "Scalable Hybrid Wireless Network-on-Chip Architectures for Multicore Systems," IEEE Transactions on Computers, vol. 60, no. 10, pp. 1485–1502, 2010.

[43] E. Tahanian, M. Rezvani and M. Fateh, "A Novel Wireless Network-on-Chip Architecture for Multicore Systems," Proc. of the 26th IEEE International Computer Conference, Computer Society of Iran (CSICC), pp. 1-8, Tehran, Iran, 2021.

[44] C. JCH Watkins and P. Dayan, "Q-learning," Machine Learning, vol. 8, no. 3-4, pp. 279-292, 1992.

[45] Md S. Shamim, N. Mansoor, R. Singh Narde, V. Kothandapani, A. Ganguly and J. Venkataraman, "A Wireless Interconnection Framework for Seamless Inter and Intra-chip Communication in Multichip Systems," IEEE Transactions on Computers, vol. 66, no. 3, pp. 389-402, 2016.

[46] K. Gola and B. Gupta "An Energy-efficient Quality of Service (QoS) Parameter-based Void Avoidance Routing Technique for Underwater Sensor Networks," Jordanian Journal of Computers and Information Technology (JJCIT), vol. 5, no. 3, pp 244-261, December 2019.