片上网络路由优化算法分析

胡 明，季双双

(芜湖职业技术学院 网络工程学院，安徽 芜湖 241003)

随着半导体技术的进步，片上系统(SoC)技术被广泛地应用到各种领域。片上系统包含的一系列核心工作都需要靠一定的拓扑结构和互联方式实现。在规模较小的系统中，往往采用总线互联的方式，但连接结点增加时容易产生对总线的争夺，每次只能进行两个结点之间的通信，导致系统通信的带宽太小。交叉开关矩阵也是一种常用的互联机制，其实现了片上网络每两个结点的直接互联，实现了低延时和高吞吐率，但是容易产生通信通道的浪费[1]。

片上网络系统(下文简称NoC)平衡了通信延时和通信成本的关系，它将片上系统的结点以网络的形式连接，在大规模结点的片上系统中得到广泛运用。目前，应用最广泛的片上网络系统的拓扑结构是网格结构，它将每个核心结点通过网格的结构连接起来，既具有较低的成本，又可以达到较低的通信延时。网格结构也易于半导体工艺的实现，可以对其中任意两个核心结点提供多条通信路径，具有较高的容错能力。

1 路由算法分类

NoC路由算法根据路径决策来分可分为无关路由、自适应路由及部分自适应路由。无关路由是指对于指定的发送结点和目标结点，在不同的时间下都采用相同的路由策略而不考虑当前网络的状态。而自适应路由针对的是指定的发送结点和目标结点，每次的路由决策会根据网络故障、拥塞及硬件温度等情况发生变化，实现整体的最优决策。部分自适应路由则综合了无关路由和自适应路由，针对不同的情况采取不同的路由方式[2]。

1.1 NoC无关路由算法

NoC无关路由所做的决策与片上网络的拥塞程度、故障结点无关，它可以按固定方法发送数据包，也可以沿随机路径发送数据包。虽然无关路由算法简单，但是一般按照固定策略发送数据包的路由策略没有容错能力，在片上结点出现故障时将失效。NoC无关路由算法包括：维序路由算法、禁止转向算法及泛洪算法[3]。

1.2 NoC自适应路由算法

自适应路由主要是指对网络中拥塞的自适应。当网络中的某些结点负载过重时，自适应路由算法可以自动检测并绕过这些结点，选择另一条空闲的路径。

自适应路由的策略一般是建立在对拥塞考察的基础上，按其对拥塞的感知程度可分为本地拥塞感知和区域拥塞感知。本地拥塞感知往往考察本路由单元的相邻路由单元的拥塞情况，其实现较为简单，仅需在路由单元加入拥塞决策函数即可实现拥塞的自适应。区域拥塞感知需综合考察全局结点的状态，其路由策略往往优于仅考察邻居结点的路由策略，但其硬件和算法实现较复杂。

自适应路由根据适应程度分为完全自适应路由和部分自适应路由。完全自适应路由在综合考虑各方向的拥塞程度的基础上，选择最优的方向发送数据包；而部分自适应路由在路由策略上有所限制，在综合考虑拥塞程度和路由方向限制的因素后选择路由策略。

1.3 NoC容错路由算法

容错路由算法是在存在故障的片上网络实现正常通信的路由算法。对于可能出现故障的片上网络，可以通过沿不同路径重复发送相同的数据包来解决，也可以在故障结点处通过绕路发送数据包来解决[4]。对于发送单一数据包的路由，又可以跟据对待故障的粒度分成故障块路由、单故障路由及细粒度故障路由[5]。

1.4 源路由算法

源路由算法是指路由决策全部完成于发送数据包的源结点。源结点将路由路径加入数据包的头部，网络结点根据头部的路由信息对数据包进行转发，不再参与路由决策。源路由算法中应用较多的是NoC-LS(LinkState，链路状态)算法。该算法也被应用于宏观计算机网络的路由算法中。其思想是每个片上网络的结点都存储一份整个网络上的状态信息(链路延时、故障等)[6]。当网络发生变化时，每个片上网络结点都向邻居结点发送TEST数据包，当邻居结点接收到TEST数据包后，将回复ECHO数据包。结点根据是否收到回复的ECHO数据包判断链路是否出现了故障。当某条链路出现故障时，该结点将故障链路的位置作为数据包广播给片上网络的所有的结点，结点收到故障信息后更新当前的片上网络信息表。当需要进行路由决策时，在源结点处根据存储的整个网络结点的延时和故障信息使用路由算法找出最佳路径。

2 源路由算法分析

源路由算法的优点是在寻找路由决策的时候具有全局的链路信息，因此路由策略可以综合各种信息找出最佳路径。但该算法的实现和网络信息的存储较复杂，不适用于结点结构简单的片上网络中。

2.1 迷宫BFS寻路算法

图1 BFS 寻路算法示意图

BFS算法通过两个线性表实现，open表用来存放源结点，从open表中取出结点向4个方向扩展结点；close表用来存放已扩展结点。过程是从open表中取出所有结点，如果close表中无扩展结点，就放入open表尾，直至结束。

为了最后得出路由的策略，每个片上网络的结点需实时监测其相邻结点的故障情况，当邻居结点出现故障时，需要广播故障信息给片上网络的所有结点。片上网络每个结点需存储并更新片上网络结点的状态，记录故障结点的位置。

迷宫BFS寻路算法优、缺点明显，源结点和目标结点之间必有一条最短路径，但需要扩展更多的结点路径，效率比较低。

图1是迷宫BFS寻路算法示意图。黑色的结点是出现故障或通信出现拥塞的结点，也可以是在电路交换中被独占通信的结点；浅灰色结点是在算法过程中扩展出的结点；深灰色结点是最终找出的路由路径。从扩展的结点可以看到，迷宫BFS寻路算法具有一定的盲目性，即使目的结点在源结点的西北方，原结点仍然会忽视目的结点的方向而向周围4个方向都扩展结点，这样做虽然总能找到最短路径，但其效率低下。

2.2 迷宫 A*寻路算法

图2 A*寻路算法示意图

为了解决BFS寻路算法的盲目性，往往会在搜索过程中加入启发式函数加快寻路速度。对目前所有的启发式寻路算法来说，使用最多的是A*寻路算法，它是目前在游戏领域中应用最广泛的寻路算法。其主要优点是通过启发式函数来预测当前结点到目标结点的距离，选择性的扩展与目标结点距离较近的结点，从而加速找到通向目的结点的路径。可以证明当当前结点到目的结点的估计距离不大于当前结点到目的结点的实际距离时，A*算法总能找到最短路径。

A*算法最重要的内容就是启发式函数。令f(x)=g(x)+h(x)，x表示某一结点，g(x)表示已知源结点到x结点实际路由距离，h(x)表示x结点到目标结点的预测距离，f(x)则表示整个预测距离。A*算法同样设置两个线性表(open 表和 close 表)，其中open 表用来维护待扩展的结点，close 表放置扩展结束的结点。当h(x)=0 时，A*算法就是 BFS 算法。A*寻路算法示意图如图2所示。

3 路由算法测试分析

采用黑盒测试法，分别对BFS寻路算法和A*算法进行测试。测试数据为随机数据，测试模拟在真实的片上网络上，所有的IP核处于对等的位置，源发送结点与接收目的结点随机生成，故障结点率分为0/10%/30%3档，随机生成5000组数据，在扩展出合法路径的测试数据中取扩展结点和路径长度的平均值。测试结果见表1-表6。

表1 故障结点率0扩展结点数测试

表2 故障结点率 10%扩展结点数测试

表3 故障结点率 30%扩展结点数测试

从表1-表3可以看出，采用 A*算法寻路与 BFS 算法相比，由于加入了启发式函数，其扩展的结点数大大减少，降低了路由算法的时间复杂度和空间复杂度，即使是A*算法增加了open 表的维护，在网络规模增大时，其效率提升仍明显。

表4 故障结点率0 时间空间占用测试

表5 故障结点率10% 时间空间占用测试

表6 故障结点率30% 时间空间占用测试

从表4-表6可以看出，A*算法对于大规模片上网络来说优势明显，当网络规模增大，A*算法不会盲目扩展目标结点。而对于小规模片上网络，BFS算法和A*算法效率差不多，甚至BFS算法更优于A*算法。

4 迷宫寻路算法的扩展

迷宫A*路由算法加入结点拥塞权值，实现拥塞自适应路由。此外，可通过提高容错粒度，提高A*算法效率。

4.1 拥塞自适应路由

将网络中的每个结点附上相应的权值作为通过该结点的代价，即可将 A*算法用于实现拥塞自适应的路由，具体方法如下：

每个片上网络结点检测其自身结点的拥塞情况，例如数据包进入该结点到离开该结点的等待时间，将该时间以正相关的方式映射为 1～N的某一整数值。1 表示结点最为空闲，N 表示结点最为繁忙。此时每隔一段固定时间将该整数值及对应结点的编号广播给片上网络的所有结点。这样每个结点都能获得整个网络结点的拥塞情况。

此时代价函数g(x)修改为从源结点到当前结点 x 已经走过的权值和，启发式函数为当前结点x到目的结点预测的权值和，可以根据网络拥塞情况计算如下：h(x)=k*(|xx—xt| + |yx—yt|), 1kN。其中k根据拥塞程度确定，当片上网络整体拥塞程度较高时，需提高k的值，反之降低k的值。

4.2 提高容错粒度

粒度是指在路由策略中，对待路由单元的故障的宏观程度。之前提出的迷宫A*寻路算法，是把出现故障的路由结点都视为不可用结点，该方法的粒度较大，浪费路由资源较多。

对于仅考虑链路故障的容错策略，需设置数组存储每个结点4个方向链路的有效情况：link_enable[x][y][dir]表示坐标为(x,y)的结点其dir方向的链路是否正常。在进行结点扩展时，需要考虑扩展方向的其链路是否正常，若正常则扩展该相邻结点，否则不扩展。

5 结语

片上网络核心的性能随着半导体行业的发展而逐渐提升，在高级的片上网络上，每一个核心都被视作一个基本的 CPU 单元，使得源路由算法参考计算机领域的路由算法成为可能。本文介绍了各类型NoC 路由算法，给出了迷宫BFS算法和迷宫A*算法分析，根据实验结果给出了扩展措施。