Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering

Previous Articles     Next Articles

Adaptive Routing Algorithm Based on Congestion-aware in Network-on-Chip

SUN Li,TIAN Jinhua   

  1. (School of Information Engineering,Huanghuai University,Zhumadian 463000,China)
  • Received:2014-12-18 Online:2015-08-15 Published:2015-08-15

片上网络中基于拥塞感知的自适应路由算法

孙利,田进华   

  1. (黄淮学院信息工程学院,河南 驻马店 463000)
  • 作者简介:孙利(1972-),男,副教授、硕士,主研方向:片上网络,故障诊断;田进华,实验师、硕士。
  • 基金资助:
    河南省科技攻关计划基金资助项目(122102210510);河南省教育厅科学技术研究基金资助重点项目(14B520036)。

Abstract: Aiming at the disadvantages of existing XY routing algorithms have the higher delay in Network-on-Chip(NoC).In this paper,a new fault-tolerant and congestion-aware adaptive routing algorithm for NoC is proposed.A distributed approach is employed for partitioning of the regular NoC architecture into regions controlled by local monitoring units.Each local monitoring unit runs a shortest path computation procedure to identify the best routing path so that highly congested routers and faulty links are avoided while latency is improved.To dynamically react to continuously changing traffic conditions,a ball-and-string model based shortest path computation method is proposed,which is together with the decentralized region based routing approach,and leads to minimal hardware overhead.Experimental results based on an actual Verilog implementation demonstrate that the proposed adaptive routing algorithm improves significantly the network throughput compared with traditional XY routing and DyXY adaptive algorithms.

Key words: Network-on-Chip(NoC), adaptive routing, ball-string model, shortest path computation, throughput

摘要: 针对片上网络中现有XY路由算法延时较高的问题,提出一种新的容错和拥塞感知型自适应路由算法。采用分布式策略将常规的片上网络架构分为多个由本地监测单元控制的区域,每个本地监控单元利用最短路径计算方法检测出最优路径,以避免采用拥塞严重的路由器和故障链路,进而降低延时。为了对不断变化的网络状态做出响应,给出基于ball-string模型的最短路径计算方法,并结合基于分布式区域路由方法实现硬件开销最小化。基于真实Verilog部署的实验结果表明,与传统的XY路由算法和DyXY自适应路由算法相比,该算法能明显提升网络吞吐量。

关键词: 片上网络, 自适应路由, ball-string模型, 最短路径计算, 吞吐量

CLC Number: