面向低功耗的片上网络虚通道分配算法

周 芳 吴 宁 周 磊 张 颖

(南京航空航天大学电子信息工程学院,南京 210016)

针对复杂MPSoC系统中互连结构所带来的吞吐量高、信号不完整以及时钟难以同步等问题,将宏观网络的概念应用于MPSoC设计中,形成了一种全新的集成电路通信结构——片上网络(network on chip,NoC).在NoC设计中,虚通道技术可在保证传输延时性能的同时有效地节约缓存,但过多的虚通道会带来巨大的面积和功耗开销[1-2].因此,设计时须考虑如何合理地分配虚通道资源.

早期的NoC研究侧重于其体系结构的研究,因而虚通道的分配多采用平均分配策略,即向NoC中各路由器的所有输入通道都分配相同个数的虚通道[3-7].而在面向特定应用的NoC中,节点与节点之间的通信流量并不均衡,如果仍采用平均分配策略,就不能最大程度地利用虚通道技术来减少传输延时和节约缓存.因此,可考虑采用非平均分配策略来优化虚通道的分配[8-10]:在通信流量小的节点输入通道上分配较少的虚通道;反之,则分配较多的虚通道.其中,文献[8]基于贪婪算法,通过计算输入端口带宽利用率,进行虚通道分配.文献[9]则是基于网络通信特征来分配虚通道的.这些算法实现简单,但在分配过程中仅从单个输入通道的角度来考虑,并未兼顾到网络整体情况,因此分配效率相对较低.文献[10]采用遗传算法的思想来实现虚通道分配,但该算法对新空间的探索能力有限,容易早熟收敛到局部最优解.

本文运用排队论理论将虚通道分配问题转化为一个数学问题,建立了一种2D mesh结构片上网络通信数学模型,用以估算网络中数据包的平均传输延时,并以此为约束条件,采用模拟退火算法来实现虚通道分配.该算法可以在满足传输延时性能要求的同时,对虚通道进行合理分配,通过提高虚通道利用率来减少虚通道总数目,从而降低系统的总功耗.最后,利用热点通信流量下的多组仿真实验,对这种优化分配算法的有效性进行了验证,并给出了精确的评估结果.

1 虚通道分配

在NoC设计中,虚通道技术的实现方式如图1(b)所示.

图1 输入端口虚通道的实现方式

在设计过程中,如果要求输入端的缓存大小为16个微片时,可采用单通道方式串行排列16个缓存;也可采用虚通道方式,按4×4(即设置4条虚通道,每条虚通道的缓存深度为4)或2×8 的方式排列.一方面,虚通道数目的增加,会提高网络性能;另一方面,受到缓存资源总数的限制,随虚通道数目的增加,缓存深度相应减小,导致来自同一个数据包的微片分散于几个路由节点中,从而加剧了节点的拥塞和数据包传输延迟现象.此外,虚通道数目还会直接影响片上网络的总功耗.文献[3]指出,当数据包注入率为2%,数据包微片宽度为8,虚通道深度为2时,增加1条虚通道,功耗会相应增加大约5 mW.本文设计的NoC路由单元门级电路功耗模型如下[2]:

Prouter=3.6+1.78ψbuffer+5.82ψvc+0.468ψfit

式中,ψbuffer为虚通道缓存深度;ψvc为虚通道数目;ψfit为数据包微片宽度.由此可知,降低片上网络功耗的有效途径之一是在保证网络延时性能的同时减少虚通道数目.

1.1 虚通道分配的问题描述

虚通道分配的思想是:针对特定的应用,已知网络的拓扑结构和路由算法,考虑如何在保证网络传输延时性能的同时,最小化路由单元各通道的虚通道数目,从而达到降低NoC整体功耗的目标.由于片上网络的数据包传输是一个动态过程,难以精确预测其传输延时,故针对特定的应用,可选择网络中所有数据流的平均延时作为约束条件.

已知条件:特定应用的节点间通信量、网络拓扑结构及路由算法.

约束条件:TN≤Tmax,其中TN为网络中所有数据流的平均延时,Tmax为网络中所允许的最大平均延时.

优化目标:min(N).

1.2 NoC路由器的数学模型

片上网络中数据包的传输具有动态特性,传输延时与网络结构、路由算法及节点间通信流量等因素有关.为了较为精确地计算传输延时,可采用排队论方法构建片上网络的数学通信模型.

一个面向片上网络的特定应用通常由多个数据流构成,片上网络的平均传输延时即为这些数据流延时的平均值,故平均传输延时可表示为

(1)

式中,m为特定应用中数据流个数;TLi为第i个数据流中的数据包在片上网络中的传输延时.计算TLi时可以由该数据流的源节点出发,沿传输路径递推到目的节点,计算所经各路由节点 (x,y)的z方向输入缓冲区阻塞延迟时间Bx,y,z和数据包微片头在源节点的等待时间WSi,最后得到该数据流在片上网络中的传输延时,即

式中,Tb表示一个微片无阻塞地通过路由节点的时间;d表示数据包从源节点到目的节点所经过的跳数;M表示数据包微片长度.

由此可知,计算传输延时的关键是计算阻塞延迟时间Bx,y,z和源节点的等待时间WSi.其中,Bx,y,z可由下式计算得到:

Bx,y,z=θx,y,zωx,y,z

(3)

式中,θx,y,z，ωx,y,z分别为数据包被阻塞在路由节点(x,y)的z方向缓冲区的概率和等待时间.为计算等待时间ωx,y,z,可将路由节点的每一输入通道都视为1个队列,根据排队论可以得到

(4)

式中,Sx,y,z，λx,y,z分别为数据包在路由节点(x,y)的z方向上的平均服务时间和达到率.λx,y,z的计算公式如下:

(5)

Sx,y,z的计算可参考图2.在采用虚通道技术的NoC中,同一个数据包的微片会同时存在于多个路由节点中,传输延时的计算应从包头进入传输链路开始,直到最后一个微片离开该链路结束,具体过程如图2所示.

图2 数据包传输延时示意图

由图2可知,假设数据包由源节点1传输至目的节点6,数据包长度为6个微片,路由节点的虚通道缓存深度为2.数据包由源节点出发,当数据包中所有微片都离开源节点时,包头微片还未到达目的节点,此时数据包的平均服务时间受到链路上所有下游节点的影响(图2(a)中下游节点是路由节点3,4,5,6).当数据包尾部还未离开路由节点4时,包头微片已经进入目的节点,故影响数据包服务时间的路由节点应固定为节点4,5,6.因此,第j个路由节点的平均服务时间为

(6)

式中,Bl为数据包经过下游节点l时的缓冲区阻塞延迟时间;Aj为影响平均服务时间的下游路由节点个数,具体可以表示为

(7)

式中,H为虚通道缓存深度.

计算θx,y,z时,首先需要计算转发概率矩阵F.以4×4的2维网格结构为例,其转发概率矩阵为

(8)

式中,fzz′表示数据包由z方向转发至z′方向的转发概率,具体可由下式计算:

(9)

式中,λzz′表示路由节点中从z方向输入,转发至z′方向的数据包达到率.

设置z方向为东,并以此为例计算θx,y,z,即

θx,y,E=fENPx,y+1,S+fESPx,y-1,N+fEWPx-1,y,W+fELθx,y,L

(10)

式中,Px,y,z为路由节点(x,y)中转发到z方向上缓冲区被占用的概率.对于采用虚拟通道技术的路由节点,Px,y,z的取值与虚拟通道数以及虚拟通道分配机制有关.而在采用非平均分配虚通道策略的片上网络中,则可考虑为所有虚通道均被占用的概率,即

Px,y,z=(λx,y,zSx,y,z)Vx,y,z

(11)

在计算源节点的平均等待时间时,可把源节点中的虚通道模拟为一个队列模型,即

式中,TR为网络延时;λx,y,L为从源节点输入到网络的数据包到达率.

2 虚通道分配算法

模拟退火算法(simulated annealing,SA)是一种通用的概率元启发式算法.在解决全局优化问题时,如果搜索空间是离散的,则可应用模拟退火算法在解空间中随机定位目标函数的全局最优解.对于某些问题,模拟退火算法可能比穷举迭代法更有效.目前,该算法已在工程领域中得到广泛应用[11].

为了在片上网络虚通道分配过程中应用模拟退火算法,必须确定以下参数:状态空间、优化的目标函数、新解空间产生方法、接受概率函数、退火时间表温度和初始温度.这些参数的选择会对算法的有效性产生显著影响.基于模拟退火算法进行虚通道优化分配的步骤如下:

① 初始化.设初始温度T=100,初始解状态V为所有随机产生的虚通道个数Vx,y,z组成的三维数组,且Vx,y,z≤4.每个T值的迭代次数L=1 000.

③ 计算新解空间V′下的平均传输延时TN(V′).若TN(V′)满足约束条件,即TN(V′)≤Tmax,则保留该新解空间V′;否则转到步骤③,再次生成新解空间V′.

④ 计算增量Δt=N(V′)-N(V),其中优化目标函数N(V)表示虚通道总数.

⑤ 若Δt<0,则设V′为新的当前解;否则以概率exp(-Δt/T)接受V′为新的当前解.

⑥ 重复步骤②～⑤L次.如果连续若干个新解都没有被接受,则输出当前解为最优解,结束程序.

⑦ 降低温度T,并判断其是否为0.若为0,则结束算法;否则转步骤②.为了保证算法具有合适的收敛速度,并能搜索到全局最优解,根据已有的研究经验,这里设置温度T以0.95的衰减速度逐渐减少,并趋向于0.

3 实验结果与分析

本文算法采用C++语言实现.为了验证算法的有效性,根据虚通道分配结果,采用Verilog HDL语言完成NoC的RTL级设计,并基于SMIC 0.18 μm工艺库,利用Design Compiler软件进行综合.综合得到的门级网表通过VCS仿真验证,并在Prime Time PX软件中进行功耗分析.

实验中使用的主要参数设置如下:片上网络结构为4×4的2D mesh结构;路由算法为XY固定路由算法；数据包微片长度为8；Tb=4，即路由单元在无阻塞情况下,传输一个微片需要4个时钟周期.

实验中需要对节点间的数据包流量进行设置.本文选取了热点流量(hotspot traffic)方式来验证优化算法的有效性:分别设置节点(2,2)和(1,1)为热点,即它们收到数据包的概率是其他节点的2倍.每个节点以相同的注入率λ发送数据包.调整注入率的大小,由仿真平台采集到对应的数据包延时.在每组实验中共计发送大约1×105个数据包,为了避免采集到网络不稳定时的包延时,将前1×104个数据包的延时数据丢弃.此外,还可以面向特定应用,由固定的源节点向固定的目的节点发送特定数量的数据包,以验证算法的有效性.

采用热点流量方式时,不同的注入率下平均分配算法与本文算法的延迟性能比较结果见图3.由图可知,随着注入率的增加,2种分配算法所导致的数据包平均传输延时均增加.但在同一注入率下,采用平均分配算法时的传输延时略小于本文算法.这是由于平均分配时,路由节点的每个输入端口都分配有4个虚通道;而采用本文算法时,每个输入端口的虚通道数目可能小于等于4,从而导致数据包的平均传输延时增加.由于本文以数据包的平均传输延时作为约束条件,因此传输延迟并没有受到很大影响,尤其在注入率比较小的情况下,2种分配算法所导致的传输延时基本一致.

图3 不同注入率下传输延迟性能比较

不同注入率下,平均分配算法与本文算法的功耗性能比较结果见图4.由图可知,随着注入率的增加,2种分配算法所导致的片上网络功耗均增加;但在同一注入率下,采用本文算法时功耗普遍低于平均分配算法.当节点注入率为0.016数据包/周期时,相比平均分配算法,采用本文算法可降低功耗2.3%,此时的优化效果最差;当节点注入率为0.006数据包/周期时,功耗可降低14.9%,此时优化效果最佳.此外,随着注入率的降低,本文算法对功耗的优化效果更加明显.这是因为注入率较低时,虚通道的利用率也较低,此时可在保证延时性能的前提下,采用优化算法来减少虚通道数目,因此具有更大的优化空间.

图4 不同注入率下功耗性能比较

4 结语

针对2D网格结构NoC的通信特点,本文提出了一种面向功耗的虚通道分配算法.对于特定应用的片上网络,以传输延时为约束条件,寻求最优虚通道分配和最小化虚通道总数,以达到降低功耗的目标.利用热点通信流量下的多组仿真实验来验证该算法的性能.实验结果表明,在保证传输延时性能的同时,本文算法可合理地分配虚通道资源,有效减少虚通道总数,相比平均分配算法可降低系统功耗2.3%～14.9%.此外,该算法还可推广至其他拓扑结构和其他路由算法下的虚通道分配问题中.

)

[1]洪佳杰.高性能低功耗片上网络设计中的功耗与延时模型研究[D].南京:南京航空航天大学信息科学与技术学院,2010.

[2]段振华.可重构的片上网络功耗建模与优化[D].南京:南京航空航天大学电子信息工程学院,2011.

[3]Mostafa R, Hamid S. The effect of virtual channel organization on the performance of interconnection net-

works [C]//Proceedingsofthe19thIEEEInternationalParallelandDistributedProcessingSymposium. Denver, Colorado,USA, 2005: 26-31.

[4]Mullins R, West A, Moore S. Low-latency virtual-channel routers for on-chip networks [J].ACMSIGARCHComputerArchitectureNews, 2004,32(2): 188-197.

[5]Rahmani A M, Daneshtalab M, AfzaliKusha A, et al. Forecasting-based dynamic virtual channels allocation for power optimization of network-on-chips[C]//Proceedingsofthe22ndInternationalConferenceonVLSIDesign. New Delhi, India, 2009: 151-156.

[6]Mirza-Aghatabar M, Koohi S, Hessabi S, et al. An adaptive approach to manage the number of virtual channels[C]//Proceedingsofthe22ndInternationalConferenceonAdvancedInformationNetworkingandApplications. Ginowan, Japan, 2008: 353-358.

[7]Hu J, Ogras U Y, Marculescu R. System level buffer allocation for application specific networks-on-chip router design [J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2006,25(12): 2919-2933.

[8]Ting H, Umit Y O, Radu M. Virtual channels planning for networks-on-chip [C]//Proceedingsofthe8thInternationalSymposiumonQualityElectronicDesign. San Jose, Costa Rica, 2007: 879-884.

[9]王力纬,曹阳,李晓辉,等. 片上网络虚通道分配算法[J]. 华中科技大学学报:自然科学版, 2009, 37(3): 54-57.

Wang Liwei, Cao Yang, Li Xiaohui, et al. Virtual channel allocation algorithm for network-on-chips[J].JournalofHuazhongUniversityofScienceandTechnology:NaturalScienceEdition, 2009,37(3): 54-57. (in Chinese)

[10]李晓辉,曹阳,王力纬,等. 基于遗传算法的片上网络虚通道分配算法[J]. 华中科技大学学报:自然科学版, 2010, 38(3): 42-45.

Li Xiaohui, Cao Yang, Wang Liwei, et al. Genetic algorithm-based virtual channel allocation of network-on-chips[J].JournalofHuazhongUniversityofScienceandTechnology:NaturalScienceEdition, 2010,38(3): 42-45. (in Chinese)

[11]Rutenbar R. Simulated annealing algorithms: an overview[J].IEEECircuitsandDevicesMagazine, 1989(5): 19-26.