基于动态调整的弹性片上网络路由算法  

Resilient on-chip network routing algorithm based on dynamic tuning

作　　者：李悦瑶 胡海洋 王奇 安鑫[1,2] 李建华[1,2] LI Yueyao;HU Haiyang;WANG Qi;AN Xin;LI Jianhua(School of Computer Science and Information Engineering,Hefei University of Technology,Hefei 230601,China;Anhui Province Key Laboratory of Affective Computing and Advanced Intelligent Machine,Hefei University of Technology,Hefei 230601,China)

机构地区：[1]合肥工业大学计算机与信息学院,合肥230601 [2]合肥工业大学情感计算与先进智能机器安徽省重点实验室,合肥230601

出　　处：《智能计算机与应用》2022年第10期1-8,14,共9页Intelligent Computer and Applications

基　　金：安徽省重点研究与开发计划(202004d07020004);安徽省自然科学基金项目(2108085MF203)。

摘　　要：片上网络具有良好的可拓展性和并行性,能够应对多核处理器的各种通信需求。路由算法对片上网络的性能和效率有较大的影响。网络流量不均衡可导致拥塞和热点,严重影响整个网络的性能。当前学界已提出了本地感知、区域感知和全局感知的自适应路由算法来缓解拥塞问题。然而,这些算法依然存在一些问题,如近视、非全局最优、开销高。本文提出了基于强化学习中sarsa奖惩机制思想的路由算法,简称TCRA。TCRA针对Mesh网络中无死锁的路由限制来确定每一跳的可选输出端口,并基于sarsa模型进行非最短路由的策略选择和拥塞值更新。此外,TCRA中还引入了基于延迟的阈值更新机制,通过增加一些阈值的限制来动态调整拥塞值,从而平衡网络中的流量分布。实验结果表明,与传统的区域感知路由算法相比,TCRA能够将网络延迟平均减少30%,并降低13%的功耗。与传统的基于强化学习的路由算法相比,TCRA也能够平均降低20%的延迟,并具有较低的路由器面积开销。The on-chip network has good scalability and parallelism,which can cope with the various communication needs of multi-core processors.Routing algorithms have a significant impact on the performance and efficiency of the on-chip network.Unbalanced network traffic can lead to congestion and hotspots,and seriously affect the performance of the entire network.Locally-aware,area-aware and globally-aware adaptive routing algorithms have been proposed to alleviate congestion problems.However,these algorithms still suffer from some problems such as myopia,non-global optimality and high overhead.In this paper,a routing algorithm is proposed based on the idea of sarsa reward and punishment mechanism in reinforcement learning,referred to as TCRA.The optional output port of each hop is determined by TCRA for deadlock-free routing constraints in Mesh networks,and policy selection and congestion value update are performed for non-minimal routing based on the sarsa model.In addition,a delay-based threshold update mechanism is introduced in TCRA to dynamically adjust the congestion value to balance the traffic distribution in the network by adding some threshold limits.Experimental results show that TCRA is able to reduce network latency by an average of 30%and power consumption by 13%compared to traditional area-aware routing algorithms.TCRA is also able to reduce latency by an average of 20%and has a lower router area overhead than traditional reinforcement learning based routing algorithms.

关 键 词：片上网络 无拥塞路由 自适应路由算法 强化学习 sarsa模型 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]