片上网络路由算法的研究 (1).pdfVIP

信息科技探索

片上网络路由算法的研究

胡明，张俊

摘要路由算法的作用是在片上网络中结点间相互通信时选择一条最优的通信路径。文章针对片上网络的传输规律

与特性，归类各类型的片上网络路由算法。

关键词片上网络；路由算法；通信

G2A1674-6708（2019）230-0118-02

中图分类号文献标识码文章编号

DOI:10.16607/j.cnki.1674-6708.2019.05.057

1无关路由算法最终使得至少有一份数据包发送至目的结点。该算

无关路由不考虑自适应性、容错性等，直接发法由于发送数据包的路径有多条，当片上网络的结

送数据包，包括维序路由算法、维序路由算法、泛点出现故障时，具有较强的容错能力。但由于同时

洪算法。发送多份数据包，将对网络的通信资源造成浪费，

1）维序路由算法。对一个多维网格来说，维易引起信道的拥塞。另外为了避免数据包在片上网

序路由是指在路由路径选择的过程中按照维度的顺络内无限制游走，需要给每个数据包设置生存阈值

序路由且维度顺序不能交叉。以2DMesh为例，维时间，若数据包的生存时间超过该时间将自动销毁。

序路由要求数据必须先沿X轴方向传输，再沿Y方

向传输。该路由算法实现简单，且避免死锁，但导2自适应路由算法

致了大量的数据传输包含重复路径，浪费了大量的自适应路由考虑网络拥塞程度，选择空闲路径

传输资源。欧阳一鸣等提出了XY-YX算法，当目的到达目的结点。自适应路由按其对拥塞的感知程度

结点Y方向的值小于当前结点Y方向的值时，选择分可分为本地拥塞感知和区域拥塞感知，按适应程

先Y方向后X方向传输；当目的结点Y方向的值大度分为完全自适应路由和部分自适应路由。

于当前结点对应的值时，选择X方向后Y方向传输，1）Odd-Even算法。禁止转向中的三种算法都

从而减轻XY路由算法在X方向产生的阻塞。该算限制了一定的路由选择，易引起数据包在某些方向

法也是免死锁的。2）禁止转向算法。禁止转向算的阻塞。另外平均一半的数据包的传输只有一种最

法是对维序路由算法的一种改进。根据GlassCJ，短的路由策略（例如West-First算法中目的结点

NiLM.提出的转向模型，在不使用虚通道的情况在发送结点西边的情形）。而Odd-Even算法不完全

下，为了使路由算法免死锁需要破坏逆时针和顺时限制任何一种转向，将数据包发生拥塞的可能性降

针的环行传输依赖。而维序路由算法即是破坏了顺到最低，另外每一个发送-目的结点对几乎都有多

时针和逆时针各两种转向方式。但其限制的转向个种路由策略，实现了高适应性。其基本规则是在偶

数并不是最少的，禁止转向算法在正反方向仅各禁数列禁止由东向南和由东向北的转向；在奇数列

止一种转向来达到免死锁的目的。并不是限制任意禁止由南向西和由北向西的转向。Odd-Even算法

顺时针和逆时针各一种转向就能避免死锁，例如限相对于禁止转向算法有更多的路由策略可供选择，

制西北和北西转向仍然会存在环形依赖导致死锁。