硅通孔负载全局均衡的3D NoC延迟上界优化方法

王晓蕾　胡　巧　杜高明　张多利　欧阳一鸣

(合肥工业大学微电子设计研究所, 合肥 230009)(合肥工业大学教育部IC设计网上合作研究中心, 合肥 230009)

三维集成技术日渐成熟,以它为基础的三维片上网络(3D NoC)成为片上网络领域研究中的主要方向[1-2]．与二维片上网络(NoC)相比,3D NoC具有全局互连短、封装密度高、体积小等优势,在降低芯片功耗的同时提高了网络的平均通信性能[3]．

对于NoC上的实时应用而言,不仅需要保证其平均通信性能,而且需要保证最差情形(如网络拥塞时)下的通信性能．但由于穷举、仿真等方法耗时耗力,且无法得到有效延迟上界,因此片上网络延迟上界研究成为NoC研究中的难点之一．李洋[4]针对不同业务,在确保网络服务质量的基础上分析优化了网络的通信延迟．Ahmed等[5]提出了一种新型的LA-XYZ路由算法．虞潇等[6]提出了一种面向功耗的免死锁三维全动态3D NoC路由算法,通过引入三维空间中6个方向的功耗比较,实现三维全动态路由功能,大大降低了整个系统的功耗．上述文献通过改进路由算法来优化通讯延迟、吞吐量和功耗等,取得了较好的效果,但是其考虑的延迟为平均延迟,而在很多领域,最差性能时延才是产品性能和可靠性的关键保障．

钱悦等[7]对比分析了k-ary-2-mesh网络及其对应的三维网络在最差情形下的通信性能,发现三维网络的平均通信性能虽然更优,但受垂直信道影响,其最差情形下的通信性能可能劣于其对应的二维网络,且指出垂直通道(即硅通孔)是影响性能(如延迟上界)的关键因素,但未提出解决方案．文献[8]采用一种冲突矩阵来表征网络的拥堵情况,提出了一种二维片上网络延迟上界的分析方法,但所用冲突矩阵复杂度高,对冲突的表达不够直观．

针对上述问题,本文提出了一种硅通孔负载全局均衡的3D NoC延迟上界优化方法．根据低复杂度的基于度的冲突矩阵,采用硅通孔负载全局均衡的3D NoC延迟上界优化方法,优化业务流延迟上界,提升网络性能．

1　问题描述

1.1　垂直链路特殊性问题

图1为4×3×3大小的3D-NoC结构示意图．主体为二维网格结构,分为3层,每层包含4×3个节点,每个节点包含路由节点和计算节点．其中,每个路由节点最多由东(E)、南(S)、西(W)、北(N)、上(U)、下(D)和本地(L)7个通道组成,上下通道采用TSV进行通信[9],其余通道采用片上互连线．

TSV成品率随着TSV数目的增多而显著降低．图1中TSV数量相对较少,成品率较高．但对于更大的网络规模,TSV需求较多,成品率会显著下降,垂直带宽可能会成为3D-NoC的通讯瓶颈．因此,进行性能分析时必须考虑垂直链路特殊性．

图1　3D-NoC结构示意图

1.2　业务流冲突

目前,基于片上网络的性能分析方法大多采用比较简单的路由算法,例如单路采用XY方式、随机路由等．这些路由算法设计简单,资源消耗较小,但是数据在网络传输效率较低,拥塞情况严重,会导致延迟上界增大、存储缓存空间增大、局部热点等问题[10]．

图2给出了一个简化的3×3×3大小的三维网格．将节点分别标记为v1～v27．图中共有f1,f2两条业务流,且f1，f2均流向同一个目的节点v26．若采用单路径路由,则业务流冲突明显,网路延迟较大．针对此问题,本文对业务流采取全拆分策略,以分散负载,分析业务流延迟上界,优化网络性能．

图2　3×3×3结构的多路径路由示意图

2　硅通孔负载全局均衡的延迟上界优化方法

基于广泛采用的三维网络结构NoC,研究硅通孔负载全局均衡的3D NoC延迟上界优化方法,建立三维坐标系,其中X方向和Y方向为水平平面方向,Z方向为垂直方向,并且Z方向为硅通孔的抽象．

3D NoC中目标流定义为所需要研究的业务流,冲突流定义为对目标流造成冲突的业务流,子流为全拆分情况下所产生的所有子流．全拆分是指在每个路由节点都进行拆分,且业务流拆分后可能方向上的流量是均匀的,规定业务流在源节点未拆分时的流量总和为1．网络中的业务流采用最小多路径路由的传输方式,即业务流从源节点到目的节点经过路由节点最少的路径．

2.1　优化步骤

以网络演算工具[8,11]为网络性能模型分析基础,提出硅通孔负载全局均衡的3D NoC延迟上界优化方法．图3为该优化方法流程图,根据该流程图完成三维片上网络的延迟上界优化问题．

图3　硅通孔负载全局均衡的3D NoC延迟上界优化方　 　 法流程图

2.2　路径搜索

采用业务流均匀拆分策略,搜索整个网络,找出网络中所有业务流的源节点和目的节点之间所有可行路径．从源节点开始,在X,Y,Z三个方向上开始拆分,给定每个方向的业务流拆分比,即节点拆分比．业务流流经所有节点的节点拆分比的乘积即为链路拆分比．定义每条子流的到达曲线为主流到达曲线乘以该子流的链路拆分比．

以图2网络中的2条流f1,f2为例,f1从源节点v2流向目的节点v26,f2从源节点v5流向目的节点v26．进行业务流全拆分时,首先优化业务流f1,将其设为目标流,则f2为冲突流．采用树的遍历算法分别搜索业务流f1,f2源节点到目的节点的所有可行路径．如图4所示,目标流f1共有6条可行路径,冲突流f2共有3条可行路径,每条路径对应1条子流,目标子流与冲突子流经过相同的链路节点,即目标流和冲突流在路径1,2,3上产生冲突．

(a)f1(目标流)

(b)f1可行路径

(c)f2(冲突流)

(d)f2可行路径

图4路径搜索

2.3　基于度的矩阵

2.3.1基于度的邻接矩阵

通过树的遍历算法,不仅能够求出每条业务流所有子流的到达曲线,也可得到每条子流需要流经的所有链路．由此便可推出每条子流在每条链路上的节点拆分比,得到业务流基于度的邻接矩阵．

对于图1中的三维片上网络结构,网络中路由节点的度为6,即网络中的节点最多和6个方向的节点相邻,分别为东(E)、西(W)、南(S)、北(N)、上(U)、下(D)．按上述方向顺序,邻接矩阵的每一列对应一个方向,建立基于度的邻接矩阵Asi,di为

(1)

式中,si,di分别为业务流i的源节点和目的节点;v为网络的路由节点总数;w为网络中路由节点的度;pmn为业务流i在第m个节点n方向上的节点拆分比,且

(2)

式中,pav为该业务流到达路由节点v的所有拆分比之和;pv_w为该业务流在节点v的w方向上的流量与该业务流从节点v流出的总流量的比值．

2.3.2基于度的冲突矩阵

通过基于度的邻接矩阵建立基于度的冲突矩阵,以表征网络的冲突情况．若网络中存在k条业务流,则每条业务流都有一个属于自己的邻接矩阵．遍历所有业务流,可得到整个网络的业务流分配信息．定义目标流l基于度的冲突矩阵Csl,dl为

(As1,d1+As2,d2+…+Ask,dk)∧Asl,dl-Asl,dl

(3)

式中,cmn为路由节点m指向n方向的相邻节点的路径链路冲突系数,利用链路冲突系数可以描述整个网络中的路径冲突大小;∧运算定义为

假设矩阵A,B均为2×2大小的矩阵,且

则有

(4)

图2中冲突流f2源节点为v5,其在节点v5上的总拆分比为1．在节点v5进行均匀拆分,则北(N)和上(U)方向的拆分比均为0.5．采用最小多路径路由方式,冲突流f2在节点v8处只能流向上(U)方向,因此,冲突流在节点v8的U方向上拆分比为0.5．同理可得其他节点的拆分比．定义业务流在不经过节点方向上的拆分比为0,便可得出该冲突流基于度的邻接矩阵,如图5(a)所示．根据式(3),进而得到基于度的冲突矩阵,如图5(b)所示．

图5基于度的冲突矩阵实例

2.4　TSV冲突系数

由已得的冲突矩阵,依次求出每条目标子流的TSV冲突系数．以图5(b)中的冲突矩阵为例,对于目标流f1,它共有6条子流．路径1经过2条TSV链路,即v8→v17和v17→v26,这2条链路在目标流基于度的冲突矩阵中分别对应于节点v8的上(U)方向和节点v17的上(U)方向．而在冲突矩阵中,这2个位置的元素值分别为0.50和0.75,因此可以得到2条链路的TSV冲突系数分别为0.50和0.75．选择较大的数值,得出路径1的TSV冲突系数为0.75．同理可以求出其余5条链路的TSV冲突系数,即路径2～路径6的TSV冲突系数分别为0.50,0.75, 0.75, 0.25和0．

2.5　业务流流量新分配

得到每条目标子流对应的TSV冲突系数后,选择TSV冲突系数最小的路径作为最优路径,其次为次优路径,以此类推．按照路径的TSV冲突系数大小把目标流的流量分配到部分最优路径上,冲突系数大的路径流量分配少,冲突系数小路径流量分配多．此例中路径6的TSV冲突系数最小为0,对应路径为最优路径,路径5为次优路径,以此类推,路径3和路径4的TSV冲突系数相同且都为最大值,因而对应路径均为最差路径．由此可知,目标流流量按路径v2→v11→v20→v23→v26分配,其余路径不分配流量．

由此便可完成目标流f1的优化．随后,变换目标流,将业务流f2作为目标流,根据图3对f2进行优化．本例中,优化业务流f1后,业务流f2中所有子流的TSV冲突系数都为0,已经是最优路径,故无需进行流量再分配．

2.6　算法复杂度分析

假设子流fp经过的节点总数为j,网络中所有业务流(包括冲突流和目标流)经过的节点总数为r,则计算单条目标子流的等价服务曲线的时间复杂度为O((j(j+1)/2)r)．设h为目标子流数,则计算目标流的延迟上界的时间复杂度为O(h(j(j+1)/2)r)．

3　实验结果及分析

3.1　参数设置

通过实验验证3D NoC中延迟上界与业务流拆分比的关系,证明所提方法的正确性和有效性．

以SoCLib[12]中的DSPIN片上网络为基础,搭建了一个3×3×3大小的3D NoC仿真模型(见图6)．网络中所有路由器是统一的,具有相同的服务性能．设路由节点均提供延迟-速率函数的服务曲线β(t)=0.33(t-3)+,其中t表示时间．该服务曲线表示路由节点每3个时钟周期转发1个微包,路由器进行路由转发时有3个时钟周期的最大处理延迟．配置网络中的流发包器每40个周期发送4个微包,且这4个数据包是被连续发送的．根据漏桶模型[8],目标流和冲突流都满足到达曲线α(t)=0.1t+3.7．设该3D NoC中有3条业务流,业务流f1为目标流,则f2和f3为冲突流,目标流和冲突流都采用全拆分策略．

图6　3×3×3三维片上网络目标流优化示例

3.2　延迟与业务流拆分比的关系

3.2.1延迟与冲突流拆分比的关系

采用控制变量法,将目标流拆分比设为固定值,设目标流X方向拆分比为0.3,Y,Z方向拆分比分别为0.3和0.4,实验结果见图7．其中,冲突流在X,Y,Z方向的流量总拆分比为1．

图7　延迟与冲突流拆分比的关系

由图7可知,当X方向拆分比或Y方向拆分比为0,或者两者都为0时,目标流延迟上界较小;当它们均不为0时,目标流延迟上界较大,但比较稳定．X方向拆分比和Y方向拆分比变化时,延迟上界变化较小,即在冲突流全拆分情况下,延迟上界对拆分比不敏感．

3.2.2延迟与目标流拆分比例的关系

固定冲突流的拆分比,设X,Y方向拆分比均为0.3,Z方向拆分比为0.4,实验结果见图8．

图8　延迟与目标流拆分比的关系

由图8可知,当目标流X,Y方向拆分比至少有一个为0时,目标流延迟上界较小．当X,Y方向拆分比均不为0时,目标流延迟上界较大,但较稳定．当X,Y方向拆分比总和为1时,延迟上界偏大,这是因为此时Z方向拆分比为0,所有目标子流通过同一条TSV通道,加大了此通道的负担,同时此TSV通道的冲突也较大,导致延迟上界偏大．

3.3　模拟分析

对图9中目标流f1进行优化．假设对于每个路由节点,非优化情况下目标流X,Y方向拆分比都为0.3,Z方向拆分比为0.4．对于优化和非优化情况,冲突流X方向拆分比设为0.1．

图9　目标流f1的子流

采用树的遍历法搜索目标流和冲突流中每一条子路径,得到冲突流f2共包含90条子流,冲突流f3共包含6条子流,目标流共包含12条子流,搜索路径见图6,具体路径见图9．根据TSV冲突系数分配目标流流量,改变冲突流Y方向上的拆分比,分析利用本文方法优化前、后的延迟上界,结果见图10和图11．

图10　优化对比实验

图11　优化效率

由图10和图11可知,对于任意的冲突流Y方向拆分比,优化后的延迟上界均小于优化前的延迟上界．但是对于不同的冲突流Y方向拆分比,利用本文方法对延迟上界的优化效果却差别很大．这是因为不同的冲突流Y方向拆分比会得到不同的TSV冲突系数,导致每次选择的流量分配路径不相同,从而产生不同的优化效果．实验结果表明,利用本文方法对延迟上界优化效果明显,且最大延迟上界优化了58.9%．

3.4　算法性能比较

与文献[8]中方法相比,本文方法的主要优势在于:① 利用网络演算将2D NoC拓展到3D NoC．② 提出的基于度的冲突矩阵不仅能直观地表现网络的冲突状态,还能大大降低空间存储复杂度．以3×3×3大小的网络为例,利用文献[8]中的冲突矩阵,最多需要使用(3×3×3)2=729个元素来表现网络中的冲突状态,而本文方法只需要使用(3×3×3)×6=162个元素,所占存储空间仅为原冲突矩阵的22.2%,存储复杂度从O(n2)降为O(n),大大减少了所需的存储空间．

4　结语

1) 针对3D NoC中的硅通孔特殊结构,提出一种负载全局均衡的3D NoC延迟上界优化方法．

2) 所提的基于度的冲突矩阵可以清晰直观地表现出业务流在网络中的冲突情况．对于3×3×3大小的网络,采用基于度的冲突矩阵可将存储空间降低为文献[8]中冲突矩阵的22.2%,存储复杂度从O(n2)降为O(n)．

3) 实验结果表明,采用硅通孔负载全局均衡的3D NoC延迟上界优化方法可以有效减少传输延迟、优化业迟上界,最大的优化效果将延迟上界减小了58.9%．

参考文献(References)

[1] Gaur M S, Laxmi V, Zwolinski M, et al. Network-on-chip: Current issues and challenges[C]//2015IEEEComputerSociety,InternationalSymposiumonVlSIDesignandTest. Ahmedabad, India, 2015:1-3.

[2] Katabami H, Saito H, Yoneda T. Design of a GALS-NoC using soft-cores on FPGAs[C]//2013IEEE7thInternationalSymposiumonEmbeddedMulticoreSocs. Tokyo, Japan, 2013:31-36. DOI:10.1109/mcsoc.2013.35.

[3] Khayambashi M, Yaghini P M, Eghbal A, et al. Analytical reliability analysis of 3D NoC under TSV failure[J].JEmergTechnolComputSyst, 2015,11(4): 1-16. DOI:10.1145/2700236.

[4] 李洋. 基于QoS保证的2D-mesh片上网络延时评价与性能优化研究[D]. 长春:吉林大学通信工程学院,2015.

[5] Ahmed A B, Abdallah A B. LA-XYZ: Low latency, high throughput look-ahead routing algorithm for 3D network-on-chip (3D-NoC) architecture[C]//2012IEEEInternationalSymposiumonEmbeddedMulticoreSoCs. Aizu-Wakamatsu, Japan, 2012:167-174. DOI:10.1109/mcsoc.2012.24.

[6] 虞潇,李丽,张宇昂,等.一种面向功耗免死锁三维全动态3D NoC路由算法[J]. 电子学报,2013,41(2):329-334. DOI: 10.3969/j.issn.0372-2112.2013.02.019.

Yu Xiao, Li Li, Zhang Yu’ang, et al. A power-aware dead lock avoid three-dimensional full-adaptive routing algorithm for 3D NoC[J].ActaElectronicaSinica, 2013,41(2):329-334.DOI: 10.3969/j.issn.0372-2112.2013.02.019.(in Chinese)

[7] 钱悦,鲁中海,窦强,等. 片上网络二维和三维结构的通信性能分析[J].计算机工程与科学, 2011, 33(3):34-40.DOI: 10.3969/j.issn.1007-130X.2011.03.007.

Qian Yue, Lu Zhonghai, Dou Qiang, et al. Communication performance analysis of the NoCs in 2D and 3D architectures[J].ComputerEngineering&Science, 2011,33(3):34-40. DOI: 10.3969/j.issn.1007-130X.2011.03.007.(in Chinese)

[8] Du G, Zhang C, Lu Z, et al. Worst-case performance analysis of 2-D mesh NoCs using multi-path minimal routing[C]//ACMInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis. Tampere, Finland, 2012:123-132. DOI:10.1145/2380445.2380469.

[9] 欧阳一鸣,袁吴铃,梁华国,等. 3D NoC的冗余双向TSV容错设计[J].电子测量与仪器学报,2013,27(4):326-333.DOI:10.3724/SP.J.1187.2013.00326.

Ouyang Yiming, Yuan Wuling, Liang Huaguo, et al. Fault-tolerant design of redundant bidirectional TSV on 3D NoC[J].JournalofElectronicMeasurement&Instrument, 2013,27(4):326-333. DOI:10.3724/SP.J.1187.2013.00326.(in Chinese)

[10] 秦光. 多路径路由网络负载均衡算法研究[J]. 计算机仿真, 2011, 28(11):118-121.DOI:10.3969/j.issn.1006-9348.2011.11.028.

Qin Guang. Research of load balance algorithm over multipath network[J].ComputerSimulation, 2011,28(11):118-121. DOI:10.3969/j.issn.1006-9348.2011.11.028.(in Chinese)

[11] Viswanathan N, Paramasivam K, Somasundaram K. Performance comparison of 3D NoC topologies using network calculus[J].LifeScienceJournal, 2013,10(3):4379-4385.

[12] SoClib. Soclib simulation environment [EB/OL]. (2016-10-31)[2018-01-18]. http://soclib.lip6.fr/.