Reliability-Enabled Routing in Congestion-Aware Networks-on-Chip

Document Type : Original Article

Authors

Abstract

The efficiency of networks on chip (NoC) is affected by related routing algorithms. Network congestion has a negative impact on the performance of on-chip networks due to the increased packet latency. One of the key objectives design of NoC is reliability against failure. For a NoC to be robust, achieving better performance, and tolerating faults, two key functions need to be investigated: (a) the ability to avoid congested paths and balancing the traffic workloads, and (b) the ability to tolerate faults as well as proceeding to provide system functionality against physical impairment. For this purpose, a cost model for route selection with greater reliability and less congestion has been proposed. In this model, at first a congestion-aware routing algorithm is deployed based on the Q-learning approach to check congested areas in the network, then adjacent links are considered to deal with reliability. Finally, given the importance of the reliability, high weight is assigned to this parameter, and the path with the lowest cost is selected to forward packets. Simulation results show that the proposed approach outperforms state-of-the-art Bi-LCQ algorithm under two traffic patterns.

Keywords

Main Subjects

References

[1] R. Marculescu, U. Y. Ogras, L.-S. Peh, N. E. Jerger, and Y. Hoskote, "Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 3-21, 2009.
[2] W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Proceedings of the 38th Design Automation Conference (IEEE Cat. No.01CH37232), 2001, pp. 684-689.
[3] A. Jantsch and H. Tenhunen, Networks on chip. Springer, 2003.
[4] P. Gratz, B. Grot, and S. W. Keckler, "Regional congestion awareness for load balance in networks-on-chip," in High Performance Computer Architecture, 2008. HPCA 2008. IEEE 14th International Symposium on, 2008, pp. 203-214: IEEE.
[5] M. Li, Q.-A. Zeng, and W.-B. Jone, "DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip," in Proceedings of the 43rd annual Design Automation Conference, 2006, pp. 849-852: ACM.
[6] G. Ascia, V. Catania, M. Palesi, and D. Patti, "Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip," IEEE Transactions on Computers, vol. 57, no. 6, pp. 809-820, 2008.
[7] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, and H. Tenhunen, "Agent-based on-chip network using efficient selection method," in VLSI and System-on-Chip (VLSI-SoC), 2011 IEEE/IFIP 19th International Conference on, 2011, pp. 284-289: IEEE.
[8] S. Ma, N. Enright Jerger, and Z. Wang, "DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip," in ACM SIGARCH Computer Architecture News, 2011, vol. 39, no. 3, pp. 413-424: ACM.
[9] C. J. Watkins and P. Dayan, "Q-learning," Machine learning, vol. 8, no. 3-4, pp. 279-292, 1992.
[10] S. P. Choi and D.-Y. Yeung, "Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control," in Advances in Neural Information Processing Systems, 1996, pp. 945-951.
[11] S. Kumar and R. Miikkulainen, "Dual reinforcement Q-routing: An on-line adaptive routing algorithm," in Proceedings of the artificial neural networks in engineering Conference, 1997, pp. 231-238.
[12] S. Kumar and R. Miikkulainen, "Confidence based dual reinforcement q-routing: An adaptive online network routing algorithm," in IJCAI, 1999, vol. 99, pp. 758-763: Citeseer.
[13] M. K. Puthal, V. Singh, M. S. Gaur, and V. Laxmi, "C-Routing: An adaptive hierarchical NoC routing methodology," in VLSI and System-on-Chip (VLSI-SoC), 2011 IEEE/IFIP 19th International Conference on, 2011, pp. 392-397: IEEE.
[14] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, J. Plosila, and P. Liljeberg, "Optimized Q-learning model for distributing traffic in on-Chip Networks," in Networked Embedded Systems for Every Application (NESEA), 2012 IEEE 3rd International Conference on, 2012, pp. 1-8: IEEE.
[15] 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.
[16] آ. امیدوار. ک. محمدی, "الگوریتم مسیریابی با افزایش قابلیت اطمینان در شبکههای تحملپذیر تاخیر," فصلنامه صنایع الکترونیک , vol. 5, no. 1, 1393.
[17] J. Kim, D. Park, C. Nicopoulos, N. Vijaykrishnan, and C. R. Das, "Design and analysis of an NoC architecture from performance, reliability and energy perspective," in Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, 2005, pp. 173-182: ACM.
[18] M. Ebrahimi, M. Daneshtalab, J. Plosila, and F. Mehdipour, "MD: minimal path-based fault-tolerant routing in on-chip networks," in Design Automation Conference (ASP-DAC), 2013 18th Asia and South Pacific, 2013, pp. 35-40: IEEE.
[19] J.-x. Wang, F.-f. Fu, T.-S. Zhang, and Y.-P. Chen, "A small-granularity solution on fault-tolerant in 2D-mesh network-on-chip," in Solid-State and Integrated Circuit Technology (ICSICT), 2010 10th IEEE International Conference on, 2010, pp. 382-384: IEEE.
[20] Z. Zhang, A. Greiner, and S. Taktak, "A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip," in Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE, 2008, pp. 441-446: IEEE.
[21] D. Fick, A. DeOrio, G. Chen, V. Bertacco, D. Sylvester, and D. Blaauw, "A highly resilient routing algorithm for fault-tolerant NoCs," in Proceedings of the Conference on Design, Automation and Test in Europe, 2009, pp. 21-26: European Design and Automation Association.
[22] M. Valinataj, S. Mohammadi, J. Plosila, P. Liljeberg, and H. Tenhunen, "A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip," AEU-International Journal of Electronics and Communications, vol. 65, no. 7, pp. 630-640, 2011.
[23] R. J. Behrouz, M. Modarressi, and H. S. Azad, "A Reconfigurable Fault-Tolerant Routing Algorithm to Optimize the Network-on-Chip Performance and Latency in Presence of Intermittent and Permanent Faults," in 2011 IEEE 29th International Conference on Computer Design (ICCD), 2011, pp. 433-434: IEEE.
[24] J. Duato, S. Yalamanchili, and L. M. Ni, Interconnection networks: an engineering approach. Morgan Kaufmann, 2003.
[25] E. Wachter, V. Fochi, F. Barreto, A. Amory, and F. Moraes, "A Hierarchical and Distributed Fault Tolerant Proposal for NoC-based MPSoCs," IEEE Transactions on Emerging Topics in Computing, pp. 1-1, 2018.
[26] A. B. Gabis, P. Bomel, and M. Sevaux, "Application-aware Multi-Objective Routing based on Genetic Algorithm for 2D Network-on-Chip," Microprocessors and Microsystems, 2018.
[27] C. Wu et al., "An efficient application mapping approach for the co-optimization of reliability, energy, and performance in reconfigurable NoC architectures," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 8, pp. 1264-1277, 2015.
[28] Y. Ben-Itzhak, E. Zahavi, I. Cidon, and A. Kolodny, "HNOCS: modular open-source simulator for heterogeneous NoCs," in Embedded Computer Systems (SAMOS), 2012 International Conference on, 2012, pp. 51-57: IEEE.
[29] A. Varga, "Using the OMNeT++ discrete event simulation system in education," IEEE Transactions on Education, vol. 42, no. 4, p. 11 pp., 1999.

Files

History

  • Receive Date: 02 May 2017
  • Revise Date: 17 June 2019
  • Accept Date: 23 June 2019
  • First Publish Date: 23 June 2019

Share

How to cite

Statistics