A <i>Q</i>-Learning-Based Fault-Tolerant and Congestion-Aware Adaptive Routing Algorithm for Networks-on-Chip
Yi Liu, Rujia Guo, Changqing Xu, Xiaodong Weng, Yintang Yang
Abstract
Link failure and network congestion have a serious impact on the performance degradation of network on chip (NoC). Adaptive routing algorithms, which have the capability of fault tolerance and congestion awareness, can make NoCs adapt to complex and changeable applications. The proposed algorithm in this letter is an adaptive routing algorithm based on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Q$ </tex-math></inline-formula> -learning. By introducing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$H - Q$ </tex-math></inline-formula> table to learn the congestion and fault information of the paths between the source node and the destination node, it can avoid the unnecessary detour of data in the fault area and select the path with less congestion. Aiming at the problem caused by the untimely updating of some values in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Q$ </tex-math></inline-formula> -learning, the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Q$ </tex-math></inline-formula> -value decay and dynamic learning rate mechanism are proposed. Experimental results demonstrate that the proposed routing algorithms still can obtain a good performance under a high failure rate (Fault rate >25%) with modest extra hardware overhead.