基于维序路由算法的自适应算法

谈俊燕 华迪

（1.常州市工学院电气信息工程学院 江苏省常州市 213032 2.常州市信息技术学院电子工程学院 江苏省常州市 213000）

科技的发展使得单个芯片能够集成更多的IP 核，但是IP 核数量的逐渐增加使得片上系统（System On Chip, SoC）难以满足设计需求。而片上网络（Network On Chip, NoC）能使系统更好地适应复杂多核SoC 设计中使用的全局异步局部同步的时钟机制，优化网络的性能。因此NoC 凭借其可升级性和易扩展性，逐渐成为了一种热门的新兴通讯结构。

维序算法是一种经典的3D 片上网络的确定性路由算法，它的路由路径仅由源节点和目的节点的地址决定，该算法根据偏移量来决定在哪个维度上进行数据传送，当数据包在一个维度内传送完成后不会再次在该维度内传送，因此维序路由可以有效的防止死锁的产生。但是由于其算法的路由路径是固定的，不能根据路径中各节点情况进行路径调整和自适应，容易产生节点阻塞而降低效率。因此本研究提出了一种改进的自适应算法，当数据在传送过程中遇到阻塞时，算法会判断当前情况，并且改变数据的传送路径，从而避开阻塞的数据传送通道，而在其他空闲通道完成数据传送，由此显著降低等待通信通道恢复通畅状态所额外增加的延迟和时间，极大地提高运行的效率。

1 数据传输状态对比

数据的传输通道可分为阻塞状态和正常状态。为了得到两种状态下数据传输通道的特点，可将分别处于阻塞状态和正常状态的数据传输通道节点100 和节点000 的SwitchContorl 模块中的所有变量进行仿真对比，得到图1 所示的仿真波形图。可以看出当数据传输通道正常时，节点100 的SwitchContorl 模块中auxfree 变量的0端口在数据传送时变为低电平，而在27 个时钟周期后又恢复到高电平；当数据传送通道阻塞时，节点 100 的 SwitchContorl 模块中auxfree 变量的 0 端口在数据传送时变为低电平，之后始终保持该状态不变。

分析数据传输过程中通道节点的活动后可以发现，在数据传送时，节点100 由于阻塞而无法接收到来自节点 200 的发送请求信号的应答信号，因此其一直处于请求状态，即auxfree 的0 端口长期处于低电平状态而无法恢复。

2 自适应算法原理

由数据传输通道阻塞时的特点可得知，阻塞节点SwitchContorl模块中的auxfree 变量的0 端口低电平持续脉冲数大于27 个周期。因此本算法通过统计当前节点SwitchContorl 模块中auxfree 变量的0 端口低电平持续的脉冲数以判定该节点是否出现阻塞情况。

2.1 算法步骤

算法的流程如图2 所示，具体分为以下四个步骤：

（1）设定阈值为 30 个时钟周期脉冲，以此作为目标节点auxfree 变量0 端口低电平脉冲数的比较标准值。

图1：两种节点SwitchContorl 模块中auxfree 变量的0 端口信号量仿真波形图

图2：算法工作流程图

图3：维序路由算法的路由路径

图4：自适应算法的路由路径

（2）统计数据传送时auxfree 变量0 端口低电平持续的脉冲数。

（3）当0 端口低电平持续时钟周期脉冲数小于阈值时，继续该数据传输x 方向的维序路由算法；当脉冲数达到设定阈值时，即当前x 方向中存在阻塞，算法就将数据传送方向转换为 y 方向并且继续对auxfree 变量进行判断。

图5：总延迟曲线

图6：总时间曲线

（4）若y 方向的0 端口低电平持续时间小于设定的阈值，则将数据转发到 y 方向的节点并继续维序路由算法，若低电平持续时间达到 30 个时钟周期，则继续将数据传送方向转换为z 方向。

2.2 自适应算法与维序路由算法路由路径的比较

实验将数据从源节点000 传送到节点222，并且把节点100 与节点200 之间的数据传输通道手动阻塞，对维序路由算法和基于维序路由的自适应算法进行路由路径的比较，如图3 和图4 所示。

3 实验结果分析

在实验测试中选择节点 222 为源节点，节点 001 和000 分别为目的节点，并且阻塞了节点022 和112。要传输的数据包采取单一注入速率的方式，且每次进行测试时使用不同种的注入速率。为了与维序路由算法对比，实验增加了一组维序路由算法的测试作为对照，选择节点 000 为源节点，节点 221 和222 分别为目的节点，并且将节点 000 和节点 100 之间的数据传送通道阻塞 450 个时钟周期。最后将测试结果制成折线图，分析自适应算法的性能，如图5、图6 所示。

对图5 总延迟曲线进行分析，发现注入速率小于40%时，维序路由算法在阻塞状态下的总延迟明显大于本设计实现的自适应路由算法；而注入速率超过 40%后自适应路由算法图线消失，表示数据传送错误，经分析后发现是由于自适应算法在数据传输时需要对传输通道状态进行一次或者两次算法判断，此时数据应处于等待状态。随着传送速度的不断加快但是判断速度始终不变，当注入速率超过某一速度时就导致了数据的错误传送，因此本设计中所实现的自适应算法仅适用于注入速率不高于 40%的情况。

对图6 总时间曲线进行分析，发现注入速率小于40%时，数据传送完成所需时间随注入速率的增大而减少，当注入速率为 30%时，数据传输所需总时间趋近于饱和。当注入速率为小于10%时，自适应算法完成一次数据传送所需时间大于维序路由算法中存在阻塞时完成一次数据传送所需时间。因此，本设计中所实现的自适应算法在注入速率高于10%时才能具有优于维序算法的性能。

4 总结

综合上面的测试结果和分析，可以看出本设计所提出并实现的基于维序路由算法的自适应算法在数据包注入速率不小于10%且不大于40%的情况下，能够解决维序路由算法在片上数据传输通道阻塞的问题，证明了本设计路由算法的优越性和有效性。