| 标题 | 片上网络路由算法的研究 |
| 范文 | 胡明 张俊 摘 要 路由算法的作用是在片上网络中结点间相互通信时选择一条最优的通信路径。文章针对片上网络的传输规律与特性，归类各类型的片上网络路由算法。 关键词 片上网络；路由算法；通信 中图分类号 G2 文献标识码 A 文章編号 1674-6708（2019）230-0118-02 1 无关路由算法 无关路由不考虑自适应性、容错性等，直接发送数据包，包括维序路由算法、维序路由算法、泛洪算法。 1）维序路由算法。对一个多维网格来说，维序路由是指在路由路径选择的过程中按照维度的顺序路由且维度顺序不能交叉。以2D Mesh为例，维序路由要求数据必须先沿X轴方向传输，再沿Y方向传输。该路由算法实现简单，且避免死锁，但导致了大量的数据传输包含重复路径，浪费了大量的传输资源。欧阳一鸣等提出了XY-YX算法，当目的结点Y方向的值小于当前结点Y方向的值时，选择先Y方向后X方向传输；当目的结点Y方向的值大于当前结点对应的值时，选择X方向后Y方向传输，从而减轻XY路由算法在X方向产生的阻塞。该算法也是免死锁的。2）禁止转向算法。禁止转向算法是对维序路由算法的一种改进。根据Glass CJ，Ni LM.提出的转向模型，在不使用虚通道的情况下，为了使路由算法免死锁需要破坏逆时针和顺时针的环行传输依赖。而维序路由算法即是破坏了顺时针和逆时针各两种转向方式。但其限制的转向个数并不是最少的，禁止转向算法在正反方向仅各禁止一种转向来达到免死锁的目的。并不是限制任意顺时针和逆时针各一种转向就能避免死锁，例如限制西北和北西转向仍然会存在环形依赖导致死锁。在所有禁止两种转向的方法中，只有4种方法可以保证死锁，考虑对称性有West-First（WF），NorthLast（NL）及Negative-First（NF）三种算法。禁止转向的三种算法在某些情况下的路由路径不是唯一的，因此其在选择路径中可以通过一定的选择策略加入选择函数来防止拥塞。3）泛洪算法。泛洪算法将数据包沿不同的方向发送相同的数据包多份，最终使得至少有一份数据包发送至目的结点。该算法由于发送数据包的路径有多条，当片上网络的结点出现故障时，具有较强的容错能力。但由于同时发送多份数据包，将对网络的通信资源造成浪费，易引起信道的拥塞。另外为了避免数据包在片上网络内无限制游走，需要给每个数据包设置生存阈值时间，若数据包的生存时间超过该时间将自动销毁。 2 自适应路由算法 自适应路由考虑网络拥塞程度，选择空闲路径到达目的结点。自适应路由按其对拥塞的感知程度分可分为本地拥塞感知和区域拥塞感知，按适应程度分为完全自适应路由和部分自适应路由。 1）Odd-Even算法。禁止转向中的三种算法都限制了一定的路由选择，易引起数据包在某些方向的阻塞。另外平均一半的数据包的传输只有一种最短的路由策略（例如West-First算法中目的结点在发送结点西边的情形）。而Odd-Even算法不完全限制任何一种转向，将数据包发生拥塞的可能性降到最低，另外每一个发送-目的结点对几乎都有多种路由策略，实现了高适应性。其基本规则是在偶数列禁止由东向南和由东向北的转向；在奇数列禁止由南向西和由北向西的转向。Odd-Even算法相对于禁止转向算法有更多的路由策略可供选择，PoonaBahrebar，DirkStrooband将其运用到NoC上的多播路由，实现了路由策略适应性的最大化。 2）double-x算法。维序、禁止转向、Odd-Even等算法均通过限制一部分的路由策略实现了路由的免死锁，而在某些无法限制路由策略的情况下，此时设置虚通道是另一种免死锁的方式。Double-x算法是指在x方向的通道设置两条虚拟通道x0及x1，而在y方向的通道不设置虚拟通道，将整个网络分成上升子网和下降子网。上升子网包含x0和y+（y轴正向传输通道），下降子网包含x1和y-（y轴负向传输通道）。当目的结点在发送结点的上方时，使用上升子网路由；当目的结点在发送结点的下方时，使用下降子网路由。因此任意数据包的传输过程将只使用其中的一个子网，因而消除了环形依赖。 3）mad-y算法。double-x算法在上升子网和下降子网各只能有两个方向的转弯。例如当数据包使用y+通道时，只能在下一步使用x0通道。可能仍会导致数据包占用虚通道资源的不平衡。mad-y算法仍然在一个维度使用两条虚通道，但其通过限制最少的转向策略达到免死锁的目的，又可以根据虚通道的拥塞情况发送数据包使资源的使用较为平衡。对于double-x算法，我们可以相应扩展出mad-x算法：在double-x的规则上允许y-→x0方向和y+→x1方向的转弯。此时由于在同一子网中仍不能形成环形依赖，因而是免死锁的。此时算法具有更大的自适应度。例如当数据包将从y+转到x方向时，可以根据拥塞情况选择x0和x1之间的任意一个虚通道。而mad-y是mad-x算法在维度上交换的对称算法。 4）NoP算法。LOCAL算法是一种仅考察当前结点相邻结点的拥塞情况的算法，在可行的发送策略中选择最为空闲的结点发送数据包。其实现较简单，但路由策略缺少全局性。NoP（Neighbors-on-Path）算法是LOCAL的一种改进，其进一步考虑邻居结点的相邻结点的拥塞情况来达到避免拥塞的目的。该算法考虑的范围比LOCAL算法要大，其考察半径扩大了一倍，但未能从本质上克服局部拥塞感知的缺点，缺乏全局性。 5）RCA算法。RCA（RegionCongestionAwareness）算法是一类算法的统称：包括RCA-1D，RCA-Fanin，RCA-Quadrant等算法，都是考虑一定区域内结点的拥塞情况而做出路由决策，通过独立的逻辑单元收集片上网络其他结点的拥塞信息。RCA-1D算法考虑当前结点4个方向沿直线的所有结点的拥塞信息。RCA-Fanin算法用最简单的数字逻辑按不同权重考虑整个网络所有结点的拥塞情况，但其考虑的结点有冗余。RCA-Quadrant将整个网络按象限划分为独立的单元来考虑片上网络所有结点的拥塞情况，避免了冗余拥塞信息，但硬件实现较RCA-Fanin复杂。 6）DBAR算法。NoP算法和RCA算法在考虑结点拥塞情况时都与目的结点无关，因此会将许多无用的阻塞信息考虑其中。马胜提出的DBAR（Destination-BasedAdaptiveRouting）算法在每個结点接收并存储所有的与其同行及同列结点的拥塞信息。当数据包进行路由决策时，仅考虑位于目的结点与当前结点之间的结点的拥塞信息，从而选择最优的路由路径。 3 容错路由算法 容错路由算法是在存在故障的片上网络实现正常通信的路由算法。对于可能出现故障的片上网络，可以通过沿不同路径重复发送相同的数据包来解决，也可以在故障结点处通过绕路发送数据包来解决。对于发送单一数据包的路由，又可以跟据对待故障的粒度分成不同的路由种类：故障块路由。将集中的故障结点和周围结点一起看作整个故障块，数据包在传送过程中沿着故障块周围绕行。单故障路由。将故障结点视作单个的结点看待，不考虑故障结点相连的情况。在维序路由算法的基础上，遇到单个故障结点时采用在其自然轮廓上绕路的方式，为了使路由免死锁，需修改部分绕路方式。粒度故障路由。其将片上网络故障分为结点故障和链路故障等多种情况，因而对于路由算法的实现更加复杂，但可以减少片上网络资源的浪费。 4 源路由算法 源路由算法主要是用于宏观网络中，通过网络中结点存储网络的状态信息，包括拥塞情况、故障情况等。当网络出现问题，结点向相邻结点发送数据包，相邻结点收到数据包后回传一个链路数据包，来判断网络是否出现故障。如网络出现故障，则广播给片上网络中所有结点该数据包，并更新整个网络信息表。如需路由决策，则根据源节点存储的结点信息（故障信息、延时、拥塞等）找出到目的结点间最优路径。源路由算法是路由决策全部完成于发送数据包的源结点。源结点将路由路径加入数据包的头部，网络结点根据头部的路由信息对数据包进行转发，不再参与路由决策。源路由算法的优点是其在寻找路由决策的时候具有全局的链路信息，因此路由策略可以综合各种信息找出最佳路径。但其由于算法的实现和网络信息的存储较复杂，不适用于结点结构简单的片上网络中。 5 结论 本文在研究片上系统网络路由算法的发展现状，对目前各类型应用于片上网络的路由算法做一个归纳和综述。目前的片上网络系统进行核间通信都需要通过路由算法实现一条可行的路径，由于目前片上网络核心数不断增加，优化路由策略是提高片上网络速度的重要途径。后面将研究对源路由算法进行研究，来提高网络效率。 参考文献 [1]来耀，荆明娥.基于A*算法优化的片上网络源路由算法[J].复旦学报（自然科学版），2018，57（5）：605-610. [2]欧阳一鸣，董少周，梁华国.基于 2DMesh的NoC路由算法设计与仿真[J].计算机工程，2009（22）：227-229，235. [3]马胜.Cache一致性片上网络路由算法和流控机制优化关键技术研究[D].长沙：国防科学技术大学，2012. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。