一种新的片上网络拥塞感知容错路由算法

提出一个有效的路由通道选择机制,实现了基于片上网络(networks on chips,NoC)的拥塞感知的自适应容错路由算法(congestion-aware adaptive fault-tolerant routing algorithm,CAFR).该算法基于Up*/Down*路由算法得出源节点到目的节点每条路径的转向概率,再根据每条链路的两端路由器剩余内存时隙得出一个加权链路,最后由每条路径权重值和其路径的转向概率计算出源地址到目的地址各条路径的总权重值.实验结果表明,在无故障条件下,该算法的平均延迟和平均吞吐率都能维持较好水平.在故障条件下,该算法相对其他算法在吞吐量衰减方面有很大改善,尤其在故障率达到20%时,该算法吞吐量只有44.32%的衰减,而其他有容错性能的算法衰减达到48%~70%.

A new congestion-aware fault-tolerant routing algorithm for networks-on-chips

We put forward an effective routing channel selection mechanism to realize the adaptive fault-tolerant routing algorithm with ability of congestion aware on NoC, called CAFR(congestion-aware adaptive fault-tolerant routing algorithm). CAFR algorithm gets the turning probability of each path from the source node to the destination node based on the Up*/Down* routing algorithm; secondly, it gets a weighted link according to the remaining memory time-slot of the endpoint router in each link; finally, the total weight value in each path from the source node to the destination node is calculated according to the weight value of each path and its path turning probability. Experimental results show that the algorithm can maintain a good level on the performance of average latency and average saturation throughput under the condition of trouble-free. Under fault conditions, the algorithm has greatly improved the attenuation of the throughput compared with other algorithms. Especially When the failure rate reach 20%, the algorithm only get 44.32% decay on the throughput, and other fault tolerant algorithms get 48%~70% decay.