面向片上网络通信的可重构路由算法

面向片上网络通信的可重构路由算法

刘坚强
(咸宁职业技术学院，湖北咸宁437100)

上互连网络(Network orl Chip，NoC)采用包交换和路由的方法替代传统总线，没有全局的连线，具有很好的可扩展性，是未来多核处理器内核间的主要通信方式.NoC在片上系统中的应用有很多研究，片上系统在通信模式和网络负载分配等方面一般具有稳定性.在通用多核处理器中，由于受核间通信模式不确定性、系统的可重构性等诸多因素影响，NoC的研究和设计更具复杂性和挑战性.本文重点分析面向NoC通信的可重构路由算法.

NoC;路由算法;网络协议;QoS

在片上网络中，由于通信资源共享带来的竞争，需要对关键部件的网络带宽或者延迟进行保证.另外，在深亚微米工艺下，串扰和压降等问题使得部件之间的连线是不可靠的，可能会造成数据传输的错误或丢失.因此，通信服务质量(QoS)是分组交换的片上通信网络中一个重要问题.服务质量是指需求的吞吐量和保证核之间的端到端的通信延迟.为保证服务质量，需要将NoC中的链接专用化.链接专用化是指根据期望的通信量调整链接的带宽，带宽通过线的数目或数据频率调整.虽然在并行计算机中对互连网络已经有了很多研究，有许多可以借鉴的概念和技术，但是

NoC与片外网络在线宽、延迟、可靠性、结点计算能力和功耗等方面存在着一些重要的区别.设计专用的NoC要求以最小成本提供需求的通信性能QoS.成本包括面积和功耗两方面.在面积方面，链接、缓冲器和路由被裁减;在功耗方面，使用最短的路径路由［1］.

1 片上网络通信的网络协议

片上网络的通信协议也采用层次化设计，协议的每一层为它的上一层提供相应的接口.从下到上分别为:物理层、数据链路层、网络层、传输层、系统层和应用层.

NoC借鉴了开放系统互连(Open System Interconnection，OSI)参考模型中的分层思想，通常包含5个层次.

(1)物理层.主要解决通信通道的物理实现问题，包括互连结构、电气性能等.

(2)数据链路层.通过数据分包技术解决物理层信号不可靠的问题.

(3)网络层.主要研究数据包如何在网络中传输，包括路由算法.交换算法决定建立连接类型，而路由算法则决定数据传输的路径.发送节点根据接收节点的目的地址发送数据包.［2］

(4)传输层.主要研究在发送方如何将数据分解并建立数据包以及在接受方如何从数据包中获得数据信息.

(5)系统层.系统软件负责提供一个抽象的物理平台.简单地讲，NoC系统是由网络结点按照一定的拓扑结构连接成的网络，NoC体系结构设计包括拓扑结构、路由和资源网络接口的设计为基础的许多方面.a.网络拓扑.即片上网络结点和连接网络结点的链路的布局和连接方法，增加结点度，缩短网络直径，降低结点间通信的跳数，是目前拓扑结构研究的热点.b.路由策略.用来决定通过什么样的路线将消息从源结点送到目的结点.源结点和目的结点之间的线路可以是确定的，也可以是自适应的.好的路由算法能够保证消息的传输延迟尽可能地小，同时在网络中各部分的负载尽量平衡.c.资源网络接口.用来连接片上资源与网络结点，负责数据在片上资源与网络结点之间的数据传递，是片上系统的重要组成部分.网络接口的设计应该尽量简单和通用.

(6)应用层.主要是应用软件.片上网络的应用层用于处理应用程序的通信、数据传输、消息传输和同步机制.在进行应用层的设计时，要考虑片上网络的具体应用需求，针对不同应用的特点进行设计.此外，片上网络没有专用的协处理机来对协议进行处理，协议必须由硬件来实现，这就要求片上网络的协议不能太复杂［3］.

在片上网络中，通信协议比总线协议要复杂得多，为了便于扩展，同计算机网络一样，NoC也采取了分层协议的设计思想(如下图1所示)，协议的每一层提供特定的功能和接口.

图1 片上网络通信协议

树结构在片上互连中也有应用，其布局比较复杂，扩展性较差，树的不同分支之间的通信延迟比较大，它的主要优势是片上通信具有较好的局部性.不规则的网络拓扑结构主要是在一个网络中混合使用不同形式的拓扑结构［4］.如改变原来的规则拓扑结构的链路，或者是将若干不同的规则拓扑结构链路连接起来实现的，或者是在网络的不同层次使用不同的拓扑结构等.由于应用程序对网络的需求存在不对称性，实际的网络拓扑结构会是一种不规则的结构.考虑到深亚微米下芯片中存在的不确定性，会有一些部件出现损坏，即使规则的网络拓扑，也会因为一些结点的损坏而破坏网络的规整性.研究不规则网络拓扑结构具有很重要的意义.

2 虫孔路由问题

NoC设计的一个重要问题之一是决定路由类型，这对网络的性能和功耗有重要影响.路由策略越复杂，设计面积越大，因此需要在面积和性能之间进行折衷.实现的复杂性和性能需求是选择路由策略要考虑的两大问题.自适应路由、确定性路由需要的资源少，同时确保有序的分组到达，另外，自适应路由根据网络拥塞而改变路径，从而可提供更好的吞吐量和低延迟.然而无序的消息到达在自适应算法中是个难题.另外，避免死锁和活锁对NoC也是个关键，因为死锁(活锁)探测和恢复机制代价大且会导致不可预测的延迟［5］.确定性和部分自适应算法可以避免死锁和活锁操作，但完全自适应策略要求额外的预防.

如果考虑的应用生成的通信是可预测的，确定性路由更合适，因为那样的话，应用依赖，路由算法可被定制(Cmstomized)，如通过路由表分配、通信划分等以匹配应用通信模式，另外，还有对随机路由在NoC中的研究.(1)死锁.因为wormhole交换对片上网络实现有很多优点，这里主要讨论wormhole中的死锁和活锁问题.(2)活锁.活锁是许多自适应路由方案中潜伏的问题.当一个分组以循环方式围着它的目的地一直运行下去时，就产生了活锁.

3 交换技术与路由算法

电路交换是一种面向连接的交换机制，在源结点和目的结点之间建立电路连接，直到数据传输完成.AEthereal、 Nostrum和MANGO都使用了电路交换.由于具有低延迟和低存储需求的特点，基于虫孔寻径的包交换是目前片上互连网络所采用的主要交换方式.在确定性路由算法中，包的传送路径是由源结点和目的结点决定的，可分为源路由算法和X－Y维序路由算法.在自适应路由算法中，使用从其他结点收集来的有关网络流量的信息来计算路由.路由算法的选择应该考虑应用程序的通信特性.根据应用程序的通信特征设计合适的路由算法，可以从总体上降低网络传输的平均延迟，提高系统的性能.自适应路由和确定性路由都有其适用范围.当网络中某结点损坏或关闭时，会破坏网络的规整性，确定性路由往往无法完成其他结点间的通信.这就需要研究混合的动态路由算法.

4 片上网络的典型路由算法

通信网络中的数据流通信来自处理器之间和处理器与存储器之间的事务.片上通信的性能和功耗不仅与网络的物理特征(电压摆动、线延迟和输出负载电容等)有关，还依赖于处理器节点之间的交互.

分组(Packet)，也称为包，是NoC中消息的传输形式.MPSoC网络支持的分组传输由头部、有效负荷(Payload)和尾部三个部分组成.一个分组的头部包括目的地址、源地址和请求的操作类型(Read，Write，Invalidate等).有效负荷包含传输的数据.尾部包括检错和纠错码.片上网络的分组有不同的来源，它们可分为以下类型［6］:

(1)存储器访问请求分组.分组头包括目标存储器(节点ID和存储器地址)的目的地址和存储器操作的类型(如存储器读)，因为没有数据传输，有效负荷为空.

(2)Cache一致同步分组.由来自存储器的Cache一致操作引起.这种类型的包来自被更新的存储器，被发送到所有具有被更新数据副本的Caches中.分组头包含存储器标志和数据的模块地址.如果同步使用更新的方法，包的有效负载是更新数据.如果同步使用“Invalidate”方法，分组头包括操作类型(Invalidate)，有效负载为空.

(3)取数据分组.是来自存储器的应答分组，含有请求的数据.分组头包括目的地址(请求数据的Cache的节点D).数据包含在分组的有效负载内.

(4)数据更新分组.分组包括将被写到存储器的数据.这个数据来自要求进行存储器写操作的L2 Cache.分组头包括目的存储器地址，有效负载中含有数据.

(5)I/0和中断分组.供I/0操作或中断操作使用.分组头包含目的地址或节点D.如果涉及数据交换，有效负载中就含有数据.

除I/O和中断操作，大多数分组在存储器和Cache之间传输.不同的分组来自不同的源，但是分组的长度由有效负载的大小决定.实际上，MPSoC网络中有两种不同大小的分组:短分组和长分组.短分组是没有有效负载的分组，如存储器访问请求分组和Cache一致分组(使用Invalidate方法)，这些分组只有头和尾组成，有两个Flits长度.长分组是含有有效负载的分组，如取数据分组、数据更新分组和Cache一致分组(使用更新方法).有效负载中包含的数据或来自Cache模块，或发送回节点Cache来更新Cache模块.

在片上网络的路由中，每个输入端口的缓冲区的大小对路由所占的面积有较大的影响，增加缓冲区的大小会使路由的面积急剧增加.与此同时，增加缓冲区会极大地改善整个片上网络的性能，不过由于片上网络各部分之间传输的不均衡，可能在整个片上网络中，增加的缓冲区起作用的只是一个较小的范围.有的研究给出了通过确定网络中负载最重的通道并为其分配较大缓冲区的方法.在片上互连网络的设计中，应该选择合适的网络链路通道宽度，从而达到如下目的:在符合面积、线长和功耗的限制下，使网络消息传递的延迟最小化或者使整个网络的吞吐量最大化.由于在确定链路的宽度时，会同时影响到连线的尺寸及间距，从而会影响到网络的频率，所以不能简单地只单独考虑频率和通道宽度中的某一方面.网络接口是计算资源与通信网络间的接口，它主要考虑地址信号、数据的打包、解包、编码和同步等问题.通过网络接口，计算资源与网络通信实现分离，允许计算资源和通信结构分别设计.网络接口的设计需要与现存的总线协议兼容，如OCP、AXI协议.在片上网络中，由于通信资源共享带来的竞争，需要对关键部件的网络带宽或者延迟进行保证.因此，通信服务质量(QoS)是分组交换的片上通信网络中一个重要问题.

设计NoC是MPSoC的主要任务之一.系统的一大部分延迟花在互连上的信号传播上，一大部分的能量消耗在连线的负载电容的充放电上.因此，优化互连网络版图对MPSoC性能和功耗都非常重要.片上互连网络(Networkon-Chip，NoC)采用包交换和路由的方法替代传统总线，没有全局的连线，具有很好的可扩展性，是未来多核处理器内核间的主要通信方式.虽然在并行计算机中对互连网络已经有了很多研究，有许多可以借鉴的概念和技术，但是NoC与片外网络在线宽、延迟、可靠性、结点计算能力和功耗等方面存在着一些重要的区别.NoC在片上系统中的应用有很多研究，片上系统在通信模式和网络负载分配等方面一般具有稳定性，可以针对应用的特点对片上网络进行设计和优化.在通用多核处理器中，由于受核间通信模式不确定性、系统的可重构性等诸多因素影响，NoC的研究和设计更具复杂性和挑战性.库中元件的高度参数化是通过使用全局专用网络参数和局部专用模块参数实现的.全局专用网络参数包括Flit大小、差错冗余度控制逻辑、核地址空间、两个节点之间的最大跳数、为端到端流控制分组分配的位的最大数目等.另一方面，网络接口的专用参数是:接口类型(主、从或主/从)、输出端口Flit缓冲器的大小等.

5 结论

目前，片上网络方面的研究才刚起步，未形成产品.片上通信网络还有很多问题如专门平台结构、片上网络的物理布局、容错和鲁棒性传输、异构网络路由算法、编程抽象、任务层分析和优化、代码优化和分布式操作系统等需要研究.

［1］李静梅，冯刚，王海霞，等编著.现代计算机体系结构［M］.北京:清华大学出版社，2009.

［2］马光胜，冯刚编.SOC设计与IP核重用技术［M］.北京:国防工业出版社，2006.

［3］潘中良.系统芯片SOC的设计与测试［M］.北京:科学出版社，2009.

［4］孙光，张媛媛.基于虚拟化片上网络的二级优先维序路由算法［J］.清华大学学报(自然科学版)，2011，(3): 77～78.

［5］付斌章，韩银和.面向高可靠片上网络通信的可重构路由算法［J］.计算机辅助设计与图形学学报，2011，(3):152～153.

［6］张磊，李华伟，李晓维.用于片上网络的容错通信算法［J］.计算机辅助设计与图形学学报，2007，19(4):508～514.

TN47

A

1006－5342(2012)06－0041－03

2012－02－15