二维DMesh网络中基于转弯模型的无死锁路由算法研究

On a novel turn-model based deadlock-free routing algorithm for two-dimensional DMesh networks

路由算法对整个互连网络的性能有着至关重要的影响。二维DMesh网络有效地结合了Mesh网络以及高阶路由器的优势,降低了网络的拓扑直径和平均跳步数,为消息传输提供了更多的可选择路径。针对DMesh网络,设计了一种基于转弯模型的适应性无死锁路由算法,该算法为消息传输提供了更多的灵活性。当网络中负载率较高时,能够指导消息避开拥塞区域和热点路由器,降低等待时间,最终指导消息以更快的速度到达目的节点。对新提出的路由算法进行了路径多样性方面的分析,并对算法的无死锁性进行了严格的证明。仿真实验结果表明,与DMesh网络中传统的DXY路由算法相比,这种新的适应性路由算法有效地降低了平均延迟,增加了消息传输的灵活性,最终提高了整个网络的通信性能。

Routing algorithm plays an important role in performance of interconnection networks.The 2D DMesh network combines the advantages of both Mesh network and high-radix routers,which lowers down the diameter and average hops in the whole network,as well as providing many more optional paths for messages.In DMesh,this paper presents a novel adaptive deadlock-free routing algorithm based on turn model,which provides much more flexibility for message routing in the network.When the load rate is high,the proposed routing algorithm could efficiently guide messages to avoid the congested area and hotspot routers,which directly translates to lower waiting time,and ultimately cuts down the average latency of the whole network.This paper analyzes the routing diversity of the proposed algorithm,and gives also the formal proof for the aspect of deadlock freedom.Compared with the original DXY routing algorithm,the simulation results show that the proposed algorithm could perfectly cut down average latency,improve transmitting flexibility,and enhance the communicating performance of the whole network.