片上网络高效自适应路由算法研究

摘要

随着集成电路(Integrated Circuit,IC)工艺节点的进步，在片上系统(System-on-chip,SoC)上可集成的IP(Intellectual Property)核数越来越多，实现的功能也越来越复杂。SoC设计方法学通常采用总线式结构设计，目前在系统设计中总线面临的有限地址空间和较大的延迟问题已成为设计的瓶颈。片上网络(Network-on-chip,NoC)技术借鉴了分布式计算机网络通信的特点，它具有的并行通信能力和网络可扩展性可以有效地解决复杂SoC的通信瓶颈问题，已成为具有广阔前景的片上互连解决方案。 在片上网络设计中，路由算法对网络的延迟、吞吐率和硬件开销等性能有重要的影响，因此，高效路由算法的研究十分重要。路由算法中确定性路由算法的路径唯一、实现简单，但不能根据网络状态选择路径，仅适用于低注入率；而其中的自适应路由算法可以根据网络的状态动态选择轻负载路径，适用于高注入率。 本论文系统地分析了片上网络设计的关键技术，对自适应路由算法展开了深入的研究，提出了一些设计思路，主要的研究内容和研究成果如下： （1）对已存在的XY、XY-YX、CXY和OE(Odd Even)路由算法进行了详细的分析和实现，通过流程框图、伪代码和转弯模型(Turn Model)分析了每种路由算法的设计思想和优缺点，然后通过对比分析找出了已有路由算法可以进一步改进的创新点，即将传统的OE路由算法改进为真正的具有自适应性的OE路由算法。 （2）针对传统OE路由算法不能动态选择路由路径的问题，提出了一种公平仲裁路由(Fair Arbiter Routing,FAR)，该算法采用了兼顾优先级和公平性的可变优先级(Alterable Priority,AP)仲裁方案在路由节点上实现了输出多路径的动态随机选择，缓解了拥塞，提高了网络性能。公平的FAR路由算法分别在OE模型和XY模型上实现，Noxim仿真平台的仿真和在SMIC0.13μmCMOS工艺下的验证结果表明，公平仲裁FAR路由算法以较低的硬件开销增加有效地改善了路由的网络性能。 （3）针对轻负载路径的选取问题，提出了一种本地自适应公平仲裁路由(Local Adaptive Fair Arbiter Routing,LAFAR)，该算法采用拥塞感知的方式获取相邻路由器的拥塞信息，通过比较相应路由端口的拥塞值大小选择低拥塞值的路径，有效地避开了拥塞区域，改善了网络性能；若拥塞值相同，则该路由算法退化为FAR路由算法，通过AP公平仲裁随机选择路由路径。LAFAR路由算法分别在OE模型和XY模型上实现，Noxim仿真平台的仿真和在SMIC0.13μmCMOS工艺下的验证结果表明，低拥塞LAFAR自适应路由算法具有良好的路由网络性能和较低的额外硬件开销增加。

目录

第一个书签之前