1 引言
随着半导体技术的快速发展，在单一芯片上集成数百个IP核已成为可能.片上网络(network on chip，NOC)的出现满足了众多IP核通信的需求.然而，传统的同步设计技术采用单一的电压时钟域，限制了NOC性能的提高和功耗的降低，已逐渐成为设计瓶颈[1].全局异步局部同步(globally asynchronous and locally synchronous，GALS)设计思想[2]，作为一种新的设计方法近年来成为了异步片上网络的研究热点.它在保持原有IP核同步工作方式的基础上，采用异步握手协议完成IP核之间的通信，一方面增加了片上网络的可扩展性，另一方面进一步降低了系统的能耗.
文[3]将电压频率岛的概念引入了GALS NOC，在节点结构的NOC中，合并相邻的电压频率岛(voltage frequency island，VFI)，在满足任务期限约束条件下，能够有效地降低系统的能耗.文[4]提出了片上网络VFI感知的能量优化框架，内容包括VFI感知划分、 VFI感知映射和VFI感知路由，能够有效地减少由混合时钟FIFO和电平转换器带来的能量损耗.文[1]通过基于处理器可靠性约束的电压频率岛划分和量子粒子群映射优化算法，降低了NOC系统的能耗.文[5]提出了一种性能约束下，基于遗传、 蚂蚁算法融合的NOC映射算法.文[6]提出了可靠性约束下，采用混合整数线性规划(MILP)方法完成VFI的分配，并提出轮询采样启发式映射算法.文[7]提出了面向实时数字信号系统关键链路延时的NOC映射方法.文[8]提出了类电磁优化的片上网络低功耗映射算法.文[9]提出了基于多目标免疫算法的NOC映射优化.文[10]提出了改进混合蛙跳优化的片上网络低功耗映射算法.
上述文献分别从使用电压频率岛及IP核映射算法两个角度优化NOC的能耗.电压频率岛的使用，能够有效降低现有NOC的能耗.然而，已发表的文献算法仍存在一定的局限性.文[4]存在电压孤岛问题，只能将电压孤岛划分到临近电压岛，能耗降低有限.文[1]未考虑可靠性带来的能耗开销问题.文[6]考虑最坏情况的可靠性约束后，能耗增加约70％.单纯考虑IP核映射算法，可以从一定程度上达到能耗的降低，但是无法从系统的角度获得最优能耗.如文[7-8]只考虑了映射算法，没有考虑电压频率岛的划分和通信可靠性约束.文[9-10]没有考虑电压频率岛的划分问题.且以上文献算法都是基于2维网格(2D-Mesh)的NOC拓扑结构，该结构简单、 易于实现、 扩展性强.但是大规模电路中，节点比较多，网路平均通信距离较长，占用面积也比较大，功耗相对较高.
针对以上文献在求解NOC能耗优化中遇到的问题，该文提出了一种新的异步NOC能耗优化方法RaVFIMAP(Reliable VFI aware NOC Mapping)算法.该方法采用递进优化的方式，包含VFI的划分和分配，以及NOC任务映射.在任务映射中考虑保证可靠性约束的通信开销，对异步NOC系统的可靠性进行优化，满足异步NOC的容错设计.采用2维环状(2D-Torus)网络拓扑结构，比较于2D-Mesh拓扑结构，片上网络直径减小，即异步路由节点平均距离缩短，因而从理论上功耗得到进一步的降低.
2 系统模型和问题描述本研究采用2D-Torus网络拓扑结构和2D-Torus异步片上网络的自适应路由算法(Asynchronous Adaptive X-Y routing algorithm，AA-XY)[11].应用模型采用应用特征图描述，应用特征图APCG(C，A)为有向图，每个顶点ci∈C代表IP核，每个有向边aij代表从源节点IP核ci到目的节点IP核cj的通信，参数vol(aij)表示从源节点IP核ci到目的节点IP核cj的通信数据流量.
NOC拓扑结构可以用资源结构图描述.资源结构图ARCG(T，P)是一个有向图，每个顶点ti∈T表示网络中的一个资源节点，每条有向边pij∈P表示从节点ti到节点tj的路由路径.本文的拓扑结构采用2D-Torus，M×N个资源节点的2D-Torus结构图如图 1所示.每个资源节点可以放置一个IP核和一个路由器R.每个路由器R由坐标表示，例如(0，0)表示位于(0，0)节点的路由器.
|
| 图 1 2D-Torus片上网络的资源结构模型 Figure 1 Resource structure model of 2D-Torus NoC |
具有VFI的NOC平台，设IP核数目为n，利用V=｛(Vi，Vthi)，i=1，2，…，n｝表示IP核供电电压和阈值电压的集合.
可靠的VFI感知的异步片上网络低功耗映射问题可以分解为： VFI的划分和分配，以及处理单元到资源节点的映射问题.本节对系统功耗模型和可靠性模型进行定义，然后对问题进行形式化描述.
2.1 系统功耗模型电压频率岛感知的异步片上网路，其系统功耗包括IP核的计算功耗，IP核之间的通信功耗和不同电压频率岛之间的转换功耗.本研究中，定义IP核的计算功耗为具有处理功能的IP核的动态能耗.根据文[4]对单个IP核的能耗计算公式，可以得到当IP核执行完所有任务后，异步片上网络所有IP核的动态处理能耗的总和为
|
(1) |
式中，Ri是有效周期数，Ceff，i是每个周期的切换电容，Vi是IP核的供电电压.
IP核之间的通信功耗主要是指链路、 缓存和交叉开关消耗的能量.采用文[12]提出的位能耗矩阵模型，并假设位能耗值在电源电压VDD处测量，则系统的动态通信能耗定义为
|
(2) |
其中，ELbi、 EBbit和ESbit分别代表节点间链路、 缓存和交叉开关所消耗的位能量，R(pij)表示从节点ti到节点tj的路由路径pij中包含的资源节点的集合.
不同VFI之间的转换能耗由电压装换器(voltage level converter，VLC)的能耗开销和混合时钟FIFO(mixed clock FIFO，MCFIFO)的能耗开销组成[4]，具体表达式为
|
(3) |
其中，EVLC和EMixClkFIFO分别代表VLC和MCFIFO所消耗的能量.m是VFI感知的NOC中电压转换器和混合时钟FIFO的个数.
系统功耗由IP核的动态处理能耗，IP核之间的通信功耗以及不同VFI之间的转换能耗组成，具体表达式为
|
(4) |
可靠性一直是同步及异步片上网络设计上的一大挑战.传统方法采用容错技术来改善系统的可靠性[13]，针对片上系统中的计算节点采用错误检测、 故障预测和错误掩蔽等方法来提高片上系统的可靠性.但是，针对片上网络可靠性的估算及优化的研究较少.片上网络通常采用OSI(open system interconnection)分层协议，分为物理层、 数据链路层和网络层.数据链路层可以采用ECCs(error correcting codes)，数据编码及链路冗余法检测在物理层可能出现的错误.网络层路由算法的可靠性可以通过采用多条路径传输同一个数据包，自适应路由算法，流控制机制和虚拟通道调节器[14]来保证.但是，这种分层提高可靠性的方法会使片上网络系统的功耗和面积增加，性能下降.文[15]提出了一种跨层可靠性解决方案，将多目标映射算法和自适应路由算法相结合，并提出了一种简单的可靠性模型，将由边界框决定的路由路径多样性和可靠性联系起来.对于采用2D-Mesh网络拓扑结构的片上网络，曼哈顿距离为d的节点ti和节点tj，节点构成的边界框越接近于正方形其可靠性越高.文[1]将所有处理任务在处理器上正确执行的概率作为片上网络处理器的可靠性，并利用可靠性作为约束条件来划分电压频率岛.但是文[1]并没有考虑由可靠性带来的能耗开销.
本文在文[15]的基础上，提出了一种适用于2D-Torus网络拓扑结构和AA-XY自适应路由算法的可靠性模型.考虑网络拓扑结构和路由算法后，设节点ti和节点tj在x方向的距离为xij，在y方向的距离为yij，xij越接近于yij其可靠性越高.则可靠性能耗可定义为
|
(5) |
其中，dij=xij+yij，biasing_term是使下式成立的可靠性能耗的最小值，const是常量.
|
(6) |
则该异步片上网络的可靠性能耗可定义为
|
(7) |
该可靠性能耗将异步片上网络资源节点的映射和路由算法相结合，可以很好地模拟路由路径故障带来的可靠性能耗开销.
2.3 问题描述可靠性约束下电压频率岛感知的异步片上网络能耗最优化问题可以形式化定义为： 给定资源结构图APCG(C，A)和由路由器R组成的2D-Torus异步片上网络，设定VFI的最大个数为VFImax，在满足处理器通信带宽和通信延时的约束下，寻找映射函数Φ： C→R，将APCG中的每一个IP核ci∈C映射到路由器rk∈R，使得如下目标函数最小化.
|
(8) |
这里，R′total和E′total分别表示归一化的可靠性功耗和系统功耗.α是用户根据对可靠性的要求自定义的参数，0≤α≤1.b(aij)表示aij的通信带宽，B(pij)表示路由路径pij的最大通信带宽.delay(aij)表示aij允许的最大传输延迟，D(pij)表示路由路径pij的路由跳数.
3 RaVFIMAP算法为了提高算法效率，本文提出的RaVFIMAP算法采用递进优化的方式，包含2大部分： VFI的划分和分配，以及处理单元到资源节点的映射.
3.1 VFI的划分和分配VFI划分的主要目的是将具有不同电压频率特性的IP核合并到相同的电压频率岛中.VFI的分配，就是在VFI划分后，确保相同电压相邻，避免电压孤岛的出现，同时尽可能减少不同VFI间复杂路由器的个数[4].文[1]提出利用可靠性作为约束条件划分电压频率岛，并利用近凸区域选择算法进行VFIs的分配，但是在划分和分配的过程中只考虑了IP核的动态处理能耗，没有考虑不同VFI之间的转换能耗和可靠性带来的能耗开销.文[16]提出了利用移动能耗函数来衡量IP核是否可以从低电压岛向高电压岛移动，从而获得优化的电压岛划分方案，未考虑IP核的频率特性和可靠性带来的能耗开销.本文的RaVFIMAP算法，结合上述3个方面的能耗进行VFI的划分和分配，并定义了IP核在电压频率岛之间移动的阈值函数，如果函数值小于0表示移动后得到的电压频率岛划分和分配方案优于移动前得到的电压频率岛划分和分配方案，如果大于或等于0则表示不可以移动.IP核在电压频率岛之间移动的阈值函数定义如下：
|
(9) |
本文的划分和分配方法需要给定资源结构图APCG(C，A)，IP核供电电压和阈值电压的集合V，以及电压频率岛个数的最大值VFImax.此外，还需要根据对可靠性的要求，将α设定为一个合适的值，α越大，可靠性越高，对应的系统能耗也会相应的增加.
具体算法如下：
步骤1： 计算每个IP核的工作频率.
步骤2： 计算片上网络IP核的VF个数n，若大于电压频率岛个数的最大值VFImax，则从中任意选择VFImax个VF进行降序排列(执行次数为CnVFImax，每次选取一种排列方案).
步骤3： 根据IP核供电电压和阈值电压的限制，判断是否能将最低的VF应用于所有IP核，若是，则按式(1)计算IP核的动态处理能耗，并转步骤2； 若否，则保留可以应用最低VF的IP核，并转步骤4.
步骤4： 将VF从低到高依次应用到尚未安排电压频率岛的IP核中，并判断是否满足其供电电压和阈值电压的要求，若是，则按式(1)计算IP核的动态处理能耗，并将相应的IP核分配到该电压频率岛中.
步骤5： 保留能耗最优的VF划分，执行次数小于CnVFImax时，转步骤2； 否则转步骤6.
步骤6： 对于任意一个IP核，利用式(9)计算IP核在电压频率岛之间移动的阈值函数值，如果小于0，则可以将其移动到高一级的电压频率岛中； 否则，保留原有划分方案.
步骤7： 计算各个VFI中IP核的个数和VFI之间的通信能耗.
步骤8： 将异步片上网路结构中的所有节点放入队列(定义为TQ)中.
步骤9： 计算当前VFI中IP核的个数.
步骤10： 从TQ队列中取出一个候选节点，按通信量由低到高将当前VFI中的IP核映射到候选节点上，如果该节点与其相邻节点有最大的通信量，且不产生电压孤岛，则将IP核映射到对应的候选节点中.否则，将IP核映射到第1个候选节点上.
步骤11： 重复步骤10，直至当前VFI中的所有IP核都映射完成.
步骤12： 如果所有VFI都分配完成，转步骤13； 否则，转步骤9.
步骤13： 输出优化后的电压频率岛划分和分配方案.
3.2 IP核映射算法TC-QPSOVFI经过VFI的划分和分配，得到了最小的IP核动态处理能耗和VFI之间的转换能耗，并充分考虑了可靠性带来的能耗开销.RaVFIMAP算法的第2部分是处理单元到资源节点的映射，目的是完成异步片上网络的能耗最优化.
本文应用基于三元相关性量子粒子群优化算法(ternary correlation QPSO，TC-QPSO)[17]来求解电压频率岛感知的NoC映射问题.TC-QPSO算法，与量子粒子群算法相比，具有更高的收敛精度和收敛速度.基于TC-QPSO的电压频率岛感知的IP核映射算法TC-QPSOVFI根据文[17]更新粒子状态，具体更新的计算见式(10)：
|
(10) |
其中，mbest(t)为所有粒子个体最好位置的平均，β为收缩扩张系数，c1为个体认知加速系数，c2为群体认知加速系数.r1、 r2、 u都是[0,1]区间内均匀分布的随机变量，ρ为对角线上的元素都为1的正定矩阵.H为三元相关因子r1、 r2、 u的联合分布函数，C为三元正态Coupla函数.粒子i在位置k表示第i个IP核映射到NoC上的第k个节点.
具体算法流程如下：
步骤1： 对TC-QPSO算法的各个参数进行初始化，利用3.1节得到的结果进行种群初始化.
步骤2： 给定相关系数矩阵ρ，生成三元相关因子r1、 r2、 u.
步骤3： 计算粒子群的平均最好位置mbest(t).
步骤4： 根据式(8)计算粒子i在当前位置x(t)的适应度，更新粒子的个体最好位置.
步骤5： 更新全局最好位置.
步骤6： 根据式(10)更新粒子的位置，并确保所有的IP核都在其对应的VFI区域范围内，如果不满足式(8)则转步骤6，否则转步骤7.
步骤7： 粒子群中的所有粒子位置都更新完毕，则转步骤8； 否则转步骤3.
步骤8： 输出获得最低异步片上网络能耗的粒子分布.
4 实验结果及分析 4.1 实验仿真结果为了验证RaVFIMAP算法的性能，将多组应用实例映射到基于VFI的异步NoC平台上，包括VOPD(video object plane decoder)[18]和多媒体应用MMS(H263编/解码器、 MP3编/解码器)[19].采取同样的方式，把E3S[20]中consumer、 auto-industry、 telecom等应用实例分别映射到3×3、 4×4和5×5异步NoC的2D-Torus网络拓扑结构上.该文的仿真机为Interl(R)Core (TM) i7，主频为3.6 GHz，内存为16 GB.使用Matlab软件编程完成.异步片上网络采用2D-Torus拓扑结构，路由算法采用AA-XY路由算法.异步片上网络系统的可靠性计算采用文[15]中的蒙特卡罗算法.根据文[15]，取α=0.6，在系统功耗和可靠性之间取得平衡.
对于每个实例，分别采用VFI-R[3](基于电压岛感知的设计方法)，VFI-S[6](基于混合整数线性规划设计方法)和RaVFIMAP算法进行求解，分别比较其片上网络功耗和可靠性.片上网络功耗的实验结果以VFI-R算法的电压岛优化结果为标准，进行归一化处理.具体结果如图 2、 图 3所示.
|
| 图 2 片上网络能量消耗比较 Figure 2 Comparison of NoC energy consumption |
|
| 图 3 片上网络可靠性比较 Figure 3 Comparison of NoC reliability |
本文在考虑可靠性带来的能耗开销后，采用递进优化的RaVFIMAP算法，从图 3可以看出，与另外两种算法相比，使用RaVFIMAP算法的异步片上网络其可靠性得到了明显的改善.分析图 2可知，虽然使用了RaVFIMAP算法的异步片上网络考虑了可靠性带来的能耗开销，但是由于其使用2D-Torus网络拓扑结构及相应的自适应路由算法，且采用了递进优化的方式，因此异步片上网络的整体功耗与使用其他算法的片上网络相比，仍有一定的优势.
4.2 硬件实施讨论该文提出的RaVFIMAP算法对可靠性的优化是基于异步片上网络2D-Torus拓扑结构及其使用的AA-XY自适应路由算法.异步片上网路可以根据对路由环境中阻塞信息的监控，并结合“最短路径策略”，动态地调整下一跳的路由节点，尽可能规避阻塞严重或出现故障的路由节点，减小路由延迟[11].文[11]采用System Verilog实现了该异步片上网络，如果路由路径中的故障或阻塞过多，异步片上网络物理层会发出报警信号，提示应用层此时不能利用RaVFIMAP算法完成IP核任务映射.
5 结论该文提出了一种可靠的电压频率岛感知的异步片上网络低功耗映射算法.该算法采用递进优化的方式，根据IP核的动态处理能耗，不同VFI之间的转换能耗和可靠性带来的能耗开销定义了IP核在电压频率岛之间移动的阈值函数，并通过对阈值函数进行判断完成VFI的划分和分配，采用基于三元相关性量子粒子群优化算法完成处理单元到资源节点的映射，并在映射过程中充分考虑了可靠性带来的功耗问题.通过对应用实例进行测试，RaVFIMAP算法可以在很大程度上提高系统的可靠性，且考虑可靠性后的片上网络整体功耗与其它算法相比，仍有一定的优势.
| [1] | 张剑贤, 周端, 杨银堂, 等. 处理器可靠性约束的电压频率岛NOC能耗优化[J]. 电子与信息学报, 2011, 33 (9): 2205–2211. Zhang J X, Zhou D, Yang Y T, et al. Energy optimization of NoC based on voltage-frequency islands under processor reliability constraints[J]. Journal of Electronics & Information Technology, 2011, 33 (9): 2205–2211. |
| [2] | Chapiro D M. Globally asynchronous locally synchronous systems[D]. Palo Alto, CA, USA:Stanford University, 1984. |
| [3] | Orgas U Y, Marculescu R, Choudhary P, et al. Voltage-frequency island partitioning for GALS-based networks-on-chip[C]//Proceedings of DAC 2007. Piscataway, NJ, USA:IEEE, 2007:110-115. |
| [4] | Jang W, Ding D, Pan D Z. A voltage-frequency island aware energy optimization framework for networks-on-chip[C]//Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design. Piscataway, NJ, USA:IEEE, 2008:264-269. |
| [5] | 任向隆, 高德远, 樊晓桠, 等. 性能约束下功耗感知的电压频率岛NOC映射[J]. 华中科技大学学报:自然科学版, 2012, 40 (12): 27–33. Ren X L, Gao D Y, Fan X Y, et al. Power aware mapping for NoC with voltage-frequency islands under performance constraints[J]. Journal of Huazhong University of Science & Technology:Natural Science Edition, 2012, 40 (12): 27–33. |
| [6] | Mahabadi A, Zahedia S M, Khonsari A. Reliable energy-aware application mapping and voltage-frequency island partitioning for GALS-based NoC[J]. Journal of Computer and System Sciences, 2013, 79 (4): 457–474. DOI:10.1016/j.jcss.2012.09.006 |
| [7] | 陈庚生, 陈亦欧, 胡剑浩. 面向实时数字信号系统关键链路延时的NoC映射方法研究[J]. 电子与信息学报, 2010, 32 (7): 1638–1643. Chen G S, Chen Y O, Hu J H. A novel critical delay-aware mapping method for real-time digital signal systems with NoC platform[J]. Journal of Electronics & Information Technology, 2010, 32 (7): 1638–1643. |
| [8] | 臧明相, 王婷, 周文宏. 类电磁优化的片上网络低功耗映射算法[J]. 西安电子科技大学学报:自然科学版, 2014, 41 (4): 99–105. Zang M X, Wang T, Zhou W H. Low energy consumption NoC mapping algorithm based on modified ectromagnetism-like mechanism[J]. Journal of Xidian University:Natural Science Edition, 2014, 41 (4): 99–105. |
| [9] | 吕兴胜, 李光顺, 吴俊华. 基于多目标免疫算法的NoC映射优化[J]. 计算机工程, 2015, 41 (4): 316–321. Lü X S, Li G S, Wu J H. NoC mapping optimization based on multi-objective immune algorithm[J]. Computer Engineering, 2015, 41 (4): 316–321. |
| [10] | 臧明相, 王勐, 周文宏, 等. 改进混合蛙跳优化的片上网络低功耗映射算法[J]. 西安电子科技大学学报:自然科学版, 2015, 42 (1): 118–123. Zang M X, Wang M, Zhou W H, et al. Improved shuffled frog-leaping algorithm for low-power network-on-chip mapping[J]. Journal of Xidian University:Natural Science Edition, 2015, 42 (1): 118–123. |
| [11] | 李贞妮, 李晶皎, 方志强, 等. 异步2D-Torus片上网络自适应路由算法[J]. 东北大学学报:自然科学版, 2015, 36 (9): 1217–1221. Li Z N, Li J J, Fang Z Q, et al. Adaptive routing algorithm of asynchronous 2D-Torus Network-on-Chip[J]. Journal of Northeastern University:Natural Science, 2015, 36 (9): 1217–1221. |
| [12] | Ye T T, Benini L, Micheli G D. Analysis of energy consumption on switch fabrics in network routers[C]//Proceedings of the 39th Design Automation Conference. Piscataway, NJ, USA:IEEE, 2002:524-529. |
| [13] | Sterbenz J P G, Hutchison D, Cetinkaya E, et al. Resilience and survivability in communication networks:Strategies, principles, and survey of disciplines[J]. Computer Networks, 2010, 54 (8): 1245–1265. DOI:10.1016/j.comnet.2010.03.005 |
| [14] | Neishaburi M H, Zilic Z. NISHA:A fault-tolerant NoC router enabling deadlock-free Interconnection of Subnets in Hierarchical Architectures[J]. Journal of System Architecture, 2013, 59 (7): 551–569. DOI:10.1016/j.sysarc.2012.12.002 |
| [15] | Ababei C, Kia H S, Yadav O P, et al. Energy and reliability oriented mapping for regular networks-on-chip[C]//Proceedings of the Fifth ACM/IEEE International Symposium. Piscataway, NJ, USA:IEEE, 2011:121-128. |
| [16] | 颛孙宗亮, 李克秋. 基于数据重传的电压岛NoC能量优化[J]. 大连理工大学学报, 2014, 54 (2): 233–239. Zhuansun Z L, Li K Q. Energy optimization of NoC based on voltage-frequency islands under ARQ[J]. Journal of Dalian University of Technology, 2014, 54 (2): 233–239. |
| [17] | 吴涛, 陈曦, 严余松. 三元相关性量子行为粒子群优化算法研究[J]. 通信学报, 2015, 36 (3): 211–218. Wu T, Chen X, Yan Y S. Study of the ternary correlation quantum-behaved PSO algorithm[J]. Journal on Communications, 2015, 36 (3): 211–218. |
| [18] | Moein-Darbarila F, Khademzade A, Gharooni-Fard G. CGMAP:A new approach to network-on-chip mapping problem[J]. IEICE Electronics Express, 2009, 6 (1): 27–34. DOI:10.1587/elex.6.27 |
| [19] | Hu J C, Marculescu R. Energy-aware mapping for tile-based NoC architectures under performance constraints[C]//Proceedings of the 2003 Asia and South Pacific Design Automation Conference. Piscataway, NJ, USA:IEEE, 2003:233-239. |
| [20] | Dick R. Embedded system synthesis benchmarks suites (E3S)[EB/OL]. (2011-01-12)[2013-01-25]. http://www.ece.northwestern.edu/~dickrp/e3s/. |