片上网络自适应路由选择策略
来源:用户上传
作者: 冯漪平
摘要：本文研究了现有自适应路由算法选择策略，提出一种适合于片上网络自适应路由算法选择策略的设计方法――动态的、非探测式的路由选择，并设计了SDNS(Simple Dynamic Non-Credit Path Selection)和DOFS(Data Packet Output Information Feedback Selection)两种动态非探测式自适应路由选择策略，实现了相应的片上网络自适应路由算法。
关键词：片上；自适应；路由选择
中图分类号：TP39 文献标识码：A 文章编号：1003-2851（2011）09-0-02
片上网络设计采用虫蚀寻径的数据交换方式时，网络状态探测包准确性降低，探测式路由的性能下降，同时需要片上网络宝贵的硬件资源和能耗。对于非探测式路由选择策略，在得到路由可选输出通道集合后，SDNS采用轮询的方式为数据包分配输出端口；DOFS将本地节点之前发送数据包对各端口的请求/成功比率作为判断端口拥塞程度的指标和为数据包分配输出端口的依据。实验结果表明，动态的、非探测式的路由选择策略提高了自适应路由算法的传输效率，由于避免使用网络状态探测包，减少了缓存面积开销和额外能耗，是一种适合于片上网络自适应路由算法的选择策略设计方法。
路由选择策略作为自适应路由算法中的重要组成部分，对于充分利用网络通道资源，保证自适应路由算法的自适应性，减少网络传输延迟，提高网络传输效率起到了很重要的作用。是自适应路由算法的本质要求。
在多处理机系统中，为了提高路由性能，除了随机选择方式外，提出了三种不同的路由选择策略：最大灵活性选择、最小拥塞选择、直线选择。片上网络系统沿用了这些方法。直线选择在最靠近当前维的方向上选择通道，将数据包尽量按照维序寻径的方式路由。最小拥塞选择方法为平衡各个相邻可选方向通道使用率，选择相邻节点通道或者缓存使用最少的方向为数据发送方向。在二维网格的片上网络结构上提出了拥塞觉醒（Contention-Aware）的路由选择策略。每个节点上的路由选择决策都是基于相邻节点拥塞的信息――“压力值”（Stress Value），“压力值”通过专用的信号线传送到每一个相邻的节点。提出在片上网络中建立基于蚁群算法的通信模型，设计探测包收发控制模块，发送专用探测包收集网络状态信息并更新路由表。自适应路由选择拥塞较小方向作为发送方向来减少网络中热点（Hot Spot）的形成。提出片上网络邻居节点拥塞发现选择策略（Neighbors-on-Path Congestion-Aware Selection）。NoP策略在进行路由选择时，假设下一跳各可选相邻节点向当前数据包的目的节点发送数据包，NoP策略将沿某一条从相邻节点到目的节点的路径上所有缓存占用的数量相加，最后选择缓存占用最少的方向作为数据包发送的方向。
由于片上网络的硬件条件限制，片上网络设计的各方面，包括拓扑结构、IP核之间的交换方式、路由算法等，和多处理器系统都存在差异。片上网络的路由算法需要与片上网络中特殊的拓扑结构、交换方式相适应，才能够在有效地利用有限的资源条件下，保证良好的数据传输能力。
在传统网络中，广泛采用专门探测包收集网络负载信息的方法，它提高了自适应路由算法的性能。但是由于适用于片上网络的虫孔交换方式可能会使数据包跨越多个节点，这种方法应用在片上网络中时，会降低探测包所收集网络负载信息的有效性，不能获得其在传统网络中相当的性能。在片上网络探测包工作所产生的开销不能忽视，它需要设计的专门硬件模块，产生额外的功耗，这些限制是片上网络设计中区别于传统网络设计非常重要的方面。与传统的相邻节点最小拥塞选择策略不同，NoP策略和基于蚁群方式的策略是基于全局网络负载信息自适应路由选择策略，实现基于全局网络负载信息的自适应路由选择策略需要产生NoC设计更多的开销。基于蚁群算法建模的选择策略中，每个节点在一定的时钟间隔向网络中所有节点广播探测包，并且需要建立与数据包传输并行的探测包控制模块和路由表，其路由表随着网络规模的增大而不断增大；NoP选择策略在路由决策时需要迭代计算某一条路径上所有可能路由节点的缓存占用数量，当数据包离目的节点距离较远时，会产生较大的时间开销。此外，由于基于全局网络负载信息的自适应路由选择策略实现过程复杂，决策过程中网络状态的变化可能会降低所收集网络负载信息的有效性。
片上网络路由算法选择策略设计的困难之处在于，如何在非常有限的硬件条件下，减小或者避免额外的硬件和能耗开销，同时又能充分利用可用网络资源，提高数据传输的效率。本文研究片上网络在互连传输中各方面的特点，抽象出片上网络路由选择策略中对开销和性能影响很大的两个属性，提出一种适合于片上网络应用的自适应路由选择策略设计方法。
一、探测式路由选择与非探测式路由选择
探测式路由选择策略在传统路由中有着广泛的应用，它通过专用的探测包收集局部或者全局的网络状态信息，作为路由选择的依据。探测式路由选择策略需要一组专门的硬件来完成探测包生成、发送、回收以及处理的过程。在传统网络设计中，硬件以及能耗限制较小，探测式路由选择测策略产生的额外开销是值得的。由于对面积需求小，和其他交换方式相比，虫蚀寻径是适合于片上网络要求的数据交换方式。在这种数据交换方式下，数据包会跨越多个节点，采用探测式路由选择策略容易出现探测包收集到的信息无效的情况。例如，在最小拥塞选择方法中，数据包将相邻节点中缓存占用最少的节点作为数据输出方向，由于此方向数据包的等待时间取决于其包头所在节点处的网络拥塞状况，所以会导致当前节点局部探测式失效，使数据包长时间阻塞。另一方面，现有的非探测式的路由选择策略，如最大灵活性选择策略、直线选择策略等则不用考虑收集网络拥塞信息代价的问题，但是这些策略不能适应网络状态的变化，在高负载的网络环境下效率不高。
二、静态路由选择与动态路由选择
路由算法采用静态路由选择策略时，数据包根据路由选择策略在可选通道中选择了一个通道后，则在此方向等待，直到前方缓存空闲，数据包发送出去；而采用动态路由选择策略时，数据包可以按照一定的机制在一组可选择通道中探测空闲的通道，改变数据包的发送方向，直到其最终被传送出去为止。
从适应性的角度来说，静态路由选择策略没有对网络环境变化或者探测包收集的状态信息失效时的动态反馈机制，一旦发生状态信息失效，数据包就可能长时间阻塞。在片上网络高负载多阻塞这样一个环境下，路由选择算法应该能够反映出这种情况，当数据包在一个方向阻塞时动态地改变传输方向，充分利用空闲资源发送数据。
三、动态非探测式路由选择策略
由于探测式路由选择策略是一种间接反映网络状态的方法，当探测包信息不能真实反映当前网络状态时，探测式的路由的缺点就会暴露出来，消耗了宝贵的网络资源，同时还会产生错误的仲裁结果。对于非探测式路由选择策略，如果能在不使用探测包的同时具有动态反映网络状态的能力，则是一种适合于片上网络的路由选择策略。
本文在充分研究两类路由选择策略的基础上，探索了一种即能对网络拥塞状况做出反应，同时具有非探测式路由选择策略开销小决策快等优点的路由选择策略设计方法――动态的非探测式的自适应路由选择策略。动态非探测式选择策略通过数据包本地的信息来反映网络拥塞状态，而不使用专用跨节点网络状态探测包间接地为数据包选择传输方向提供依据的方式。这是一种更直接的方法，避免了状态探测包的开销和失效。并且动态的路由选择选择策略使得数据包在未能成功传输出去之前，按一定的机制转换传输的方向，最大程度上保证自适应路由算法的自适应性。本文设计和实现了简单动态非探测式路由选择策略SDNS和数据包输出信息反馈策略DOFS两种动态非探测式选择策略的片上网络自适应路由
本文提出了一种新的片上网络自适应路由选择策略的设计方法――动态的非探测式路由选择策略，分析了其在片上网络路由中的适用性，实现了SDNS和DOFS两种动态非探测式路由选择策略，并和之前的路由选择策略进行比较。通过理论分析和实验，证明了动态非探测式路由选择策略在片上网络路由中的适用性。
转载注明来源:https://www.xzbu.com/9/view-958885.htm
