一种多重约束下的NoC 电压频率岛划分方法

周 芳 吴 宁 叶云飞 葛 芬

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

随着集成电路技术的发展，MPSoC 系统逐渐成为下一代单芯片处理器的主要设计形式，其规模将会扩展至数百个处理核.相对于飞速增长的计算性能，传统的总线片内通信方式已经无法适应MPSoC 中日益复杂的互联结构、通信效率以及可扩展性需求.因此，作为一种复杂MPSoC 系统互联的有效解决方案，片上网络日渐受到学术界的关注.

能耗问题一直是NoC 研究的热点之一.近年来，研究人员根据不同的NoC 能耗模型，提出了动态电压调整(DVS)、动态电压频率调整(DVFS)和电压频率岛(VFI)等低功耗技术［1-12］.其中，VFI 技术是依据NoC 所具有的全局异步局部同步(globally asynchronous locally synchronous，GALS)固有机制，综合考虑电压与性能间的折中关系，将NoC系统在逻辑上划分为多个VFI，为它们分配不同的电压和频率值，使同一个VFI 上的PE 都工作于相同的电压和频率.在已有的关于VFI 的研究中［4-12］，有些致力于将已知的NoC 网格结构划分为VFI，有些为给定的岛屿选择最佳的电压与频率.如文献［4］首先为每个PE 分配不同的VFI，然后反复合并相邻的岛屿，以最小化系统的总能耗.但该方法在合并VFI 时只考虑相邻岛，对于不相邻的相同电压频率岛则无法合并，容易形成孤岛.文献［6］提出了一种基于改进的遗传模拟退火算法的NoC 电压岛划分方法，该方法以牺牲求解时间为代价，来获得更低的系统能耗.文献［7］则采用了禁忌搜索优化算法来最小化NoC 能耗，该方法只针对基于VFI 的NoC 进行电压分配，而未解决VFI 的划分问题.

由于系统芯片电源电压的降低和特征尺寸的缩小，导致芯片中瞬时故障数目的增加［13］，因此MPSoC 可靠性已成为NoC 设计中需要考虑的一个重要问题［14］.电压和频率值的改变会同时影响NoC 系统的能耗和可靠性，但现有的VFI 研究主要以优化能耗为目标，没有过多关注可靠性问题［4-9］，或者仅考虑了可靠性约束，而未考虑传输延时等其他约束条件［11-12］.因此在VFI 划分过程中，综合考虑传输延时、能耗和可靠性等性能指标，提出多重约束条件才更加合理.

基于上述分析，本文以NoC 系统总能耗为优化目标，综合考虑数据包传输延时、VFI 数量及PE可靠性等多重约束条件，提出了一种基于整数线性规划(integer linear program，ILP)的VFI 划分方法.该方法首先研究适用于ILP 的数学模型，并使用LPSolve 求解该模型，以完成NoC 电压频率岛的划分，达到能耗优化目标.

1 VFI 划分问题分析

NoC 的VFI 划分方案对NoC 系统复杂度、总能耗、延时和可靠性等性能指标都有着重要的影响.其基本的划分原则是系统中对可靠性和延时要求高的PE 划分到高电压频率域，要求相对低的PE则划分到低电压频率域，以控制系统的整体能耗;同时，从物理设计的角度考虑，过多的VFI 碎片会增加版图电源布线和时钟树的复杂性［7］，且不同VFI 之间的电平转换器也会带来额外的能耗成本.因此，VFI 的划分数目不宜过多，复杂度不能过高.图1所示为VFI 的划分对NoC 的影响.

图1中3 ×3 二维Mesh 结构的片上网络中包含9 个PE 节点，均可分别工作在高电压频率域或低电压频率域中.如果不考虑VFI 的数目限制，在完成任务图到NoC 的映射后，仅为了满足各PE 的性能和它们之间的通信关系来设置电压频率，相邻的PE 可能工作于不同的VFI 中，它们之间通信都要通过电平转换器，这样就会带来额外的通信能耗成本，可能导致NoC 的通信能耗和延时很大，系统复杂度过高(碎片多).可能出现的最坏情况如图1(a)所示，整个片上网络被划分为9 个岛;如果要求降低NoC 通信能耗、延时和系统复杂度，VFI 数目不能高于2 个，则部分PE 需要调整电压频率域.一种可能的划分结果如图1(b)所示，将PE1划分于高电压频率域中，剩余的PE 划分于低电压频率域中.这样可降低系统的复杂度和能耗，但由于大部分PE 工作于低电压频率域，系统可靠性会较差.因此，需要研究一种合理的VFI 划分方法，综合考虑系统复杂度、能耗和可靠性等性能指标，达到它们之间的均衡，如图1(c)所示的划分结果较为合理.

当系统规模扩大，NoC 中PE 节点达到上百个，电压频率岛的划分问题变得非常复杂，这就需要结合多性能指标优化算法来实现电压频率岛的划分.ILP 是一种适合用于多重约束条件的优化算法.基于ILP 算法来解决多重约束条件下的NoC电压频率岛划分问题时，首先需要根据已知的NoC 体系结构图和各PE 节点的工作电压集，分析VFI 划分问题中多重约束条件、优化目标与其之间的关系，然后构建适用于ILP 算法的数学模型.下面给出VFI 划分问题的数学描述.给定条件如下:①有向图NAG(NoC architecture graph)(VP，EP)，是已完成任务映射的NoC 体系结构图，图中每个顶点pi∈VP表示NoC 中的一个处理核PE;每条边ei，j∈EP表示从顶点pi到pj的通信路径，其权重ci，j表示PE 节点pi和pj之间的通信量.②每个PE节点pi∈VP的工作电压集其中表示PE 节点pi的工作电压.约束条件为VFI最大数目n，最大通信延时Tmax和PE 最小可靠性要求Pmin.优化目标是最小化NoC 系统总能耗E，即minE.

2 VFI 模型建立

2.1 能耗模型

片上网络VFI 划分问题的能耗优化目标由3部分组成:NoC 中所有PE 节点的计算能耗E1，NoC 各路由节点之间的通信能耗E2以及各VFI之间的转换器能耗E3.文献［11］只考虑了前2 个能耗.

2.1.1 PE 节点的计算能耗E1

PE 节点的计算能耗是指在不同的工作电压和工作频率下，PE 节点所消耗的能耗，可表示为

式中，Ri为PE 节点的活动周期数;Ceff为每个周期的翻转电容;Ti为PE 节点的空闲周期数;ki为设计参数;St为工艺参数;Vti为阈值电压.

根据式(1)可计算出在不同工作电压vki 下，所对应的PE 节点计算能耗值E1.

2.1.2 NoC 各路由节点之间的通信能耗E2

对于NoC 中所有通信链路，其通信能耗可表示为

式中，dij表示PE 节点pi和pj之间的跳数;φl(i，j)表示从PE 节点pi传输1 bit 数据到节点pj时的链路能耗，其值和链路电压的平方成正比.当VFI 的电压降低时，其频率也随之降低，如果相邻的2 个路由节点位于不同的VFI 中，则它们之间的数据传输速率应满足两者中较低的频率值，它们之间的链路电压应是两者中较低的电压值，因此φl(i，j)可用下式计算:

式中，lpq为相邻2 个路由节点pp和pq之间的链路，它位于路由节点pi到pj的链路lij中;Elij为NoC 中所有PE 节点均为最高电压Vmax时，节点pi到pj之间传输1 bit 数据的能耗;vp和vq分别为路由节点pp和pq的工作电压值.

由以上分析可看出通信能耗E2与各节点PE之间的电压关系，从而可计算出在不同电压值下所对应的通信能耗值.

2.1.3 各VFI 之间的转换能耗E3

NoC 系统中每增加一个电压岛都会带来额外的能耗开销，主要是岛间频率转换器的能耗和电平转换器能耗.当相邻的2 个PE 工作在不同的电压和时，所需要的转换能耗可根据下式计算:

式中，η 为电压转换器的效率，这里可设置η=0.9;C 为电源的滤波电容值，可取100 μF.因此，只要知道NoC 中各PE 节点之间的电压转换关系，就可计算出总转换能耗E3.

2.2 可靠性模型

片上网络VFI 划分问题中，各PE 节点的可靠性是指所有处理任务在PE 上正确执行的概率，其值Pi可用下式计算［15］:

式中，τi为任务在PE 节点pi上的执行时间;μi为每秒钟的平均故障数，与PE 的工作电压vki 有关，其计算公式为

其中，Vmax和Vmin分别为PE 的最高和最低工作电压;d 为一个由芯片参数等决定的常数，这里可设置d=1;μ0为PE 对应于最高电压Vmax的故障率，这里可设置μ0=10－6.

由式(5)、(6)可看出，各PE 节点的可靠性Pi与PE 的工作电压vki 之间为指数关系.当Vmax和Vmin分别被设置为1.5 和1.0 V 时，可发现可靠性Pi的值无限趋近于1，因此可设置 Pmin=0.999 999 99［12］.

3 基于ILP 的片上网络VFI 划分方法

基于ILP 算法构建片上网络VFI 划分问题的数学模型，一般包括3 个步骤:决策变量定义、确定约束条件和确定目标函数.

3.1 决策变量

首先根据所要优化目标的影响因素找到决策变量.根据NoC 的能耗模型，发现影响能耗大小的主要因素是各PE 的工作电压、PE 节点之间的电压转换关系以及VFI 的个数.因此，该模型中所用到的变量可定义如下.

定义变量xik表示PE 节点pi的工作电压是否为，

定义变量ri，k，j，l表示PE 节点pi和pj之间的电压转换关系，

在极端情况下，VFI 最大数目n 即为片上网络中PE 的个数.将所有NoC 中的VFI 按序排列编号，则∀pi∈VP，1≤m≤n.定义变量yim表示PE 节点pi是否分配到编号为m 的VFI 中，

定义变量tm表示编号为m 的VFI 中是否分配了PE 节点，

3.2 约束条件

针对NoC 的VFI 划分问题，需要综合考虑传输延时、VFI 最大个数和PE 最小可靠性等约束条件.此外，还需要由决策变量所受的限制条件确定决策变量本身所要满足的约束条件.约束条件设定如下:

式中，tlatency(i，j)为路由节点pi和pj之间的延时，

其中，μk为数据包通过传输路径上路由节点k 时的周期数;fk为该节点所属电压频率岛的频率;tFIFO为数据包在异步FIFO 上的延迟;W 为通道带宽.

式(7)是为了限制每个PE 节点只能配置唯一一个电压值;式(8)是为了限制每个PE 节点只能划分到唯一一个电压岛上;式(9)是为了限制电压岛的个数不超过n;式(10)保证了当tm=0 时，电压岛m 上PE 节点的个数为0;同样，式(11)保证了当电压岛m 上PE 节点个数为0 时，tm也为0;式(12)保证了只有当pi的工作电压为vki 且pj的工作电压为时，ri，k，j，l才为1;式(13)是为了满足系统的通信延时要求;式(14)是为了保证各PE 节点的可靠性Pi满足要求.

通过设置上述一系列约束条件，完成了VFI划分过程中，传输延时、VFI 最大个数和PE 最小可靠性等多重约束条件的设置.

3.3 目标函数

目标函数由决策变量和优化目标之间的函数关系确定.片上网络VFI 划分问题的能耗优化目标由3 部分组成:NoC 中所有PE 节点的计算能耗E1，NoC 各路由节点之间的通信能耗E2以及各VFI 之间的转换器能耗E3.

PE 的计算能耗E1可表示为

式中，ηki为PE 节点pi的工作电压为vki时的能耗，可由式(1)计算得到.

NoC 各路由节点之间的通信能耗E2可表示为

各VFI 之间的转换能耗E3可表示为

式中，αkl表示当相邻的2 个PE 工作在不同的电压和时，它们之间的电平转换器所消耗的能耗，可由式(4)计算得到.

因此，基于ILP 的NoC 电压频率岛划分问题的目标函数可表示如下:

4 实验结果及分析

对建立的适用于ILP 优化算法的VFI 数学模型，使用LPSolve 求解器来求解该模型.本文从嵌入式系统综合评测E3S(embedded systems synthesis benchmarks suite)测试基准［16］中选取了多组应用实例和一个多媒体系统(MMS)进行仿真实验，验证了所提出的VFI 划分方法的有效性，并给出了实验结果.所有实验均运行在配置为Intel Ceon 2.4 GHz CPU，3.48 GB RAM，Windows XP 操作系统的HP 工作站上.

4.1 E3S 实验结果

本文所用的E3S 测试基准涵盖了自动化、消费电子、网络、办公处理和通信5 个应用领域，收集了17 种来自工业界的嵌入式处理器单元作为PE库，每个测试用例中都包含一组完整的任务图信息.实验中所用到的测试用例，其网络规模分别为5 ×5，4 ×4，4 ×4，3 ×3 和4 ×4.所选用的PE 均为AMD K6-2E 处理器.实验中的主要参数设置如下:每个PE 选取了6 个电压等级V= {1.0，1.1，1.2，1.3，1.4，1.5 V}，最小可靠性要求Pmin=0.999 999 99［12］.

在实验中，VFI 数量的上限n 分别设置为3 和7［5］，延时约束Tmax也选取较高和较低2 个不同的数值，这样约束条件Tmax和n 就有4 种可能的组合((low，low)，(low，high)，(high，low)，(high，high)).在每种组合下，应用本文方法对每组测试用例进行VFI 划分，实验结果如图2所示.

图2 4 种不同约束条件下的能耗开销

从图2中可看出，随着Tmax和n 的改变，5 种测试用例的变化趋势相同.当(Tmax，n)为(low，low)时，由于约束条件变得最为严格，电压调节空间较小，各PE 都工作在较高的电压下，因此能耗开销最大.当(Tmax，n)为(low，high)或(high，low)时，只放宽其中一个约束条件，能耗开销比前一种情况要小些.当(Tmax，n)为(high，high)时，约束条件变得最宽松，电压可调空间较大，从而使能耗开销最小.

此外，本文对于每组测试用例分别与随机划分方法和文献［6］所用划分方法进行能耗比较，以随机方法的能耗值为标准，作归一化处理.比较结果如图3所示.

图3 4 种不同约束条件下能耗结果比较

由图3可看出，对于所有的测试用例，本文方法的能耗值优于其他2 种方法.相比于随机方法，可降低能耗9.1% ～33.6%;而相比于文献［6］所用方法，最高可降低能耗16.7%.

4.2 MMS 实验结果

以一个由H.263 视频编/解码器以及MP3 音频编/解码器组成的多媒体系统为例，采用本文方法对该系统进行VFI 划分.该多媒体系统包含25个任务，并可分配至若干个PE 节点，PE 节点可以是DSP、通用处理器、嵌入式DRAM 及专用ASIC等.该系统的通信任务图及各任务所属PE 节点类型如图4所示.

图4 MMS 系统通信任务图

首先采用文献［17］所提出的映射算法将MMS 系统中的各任务分配至16 个PE 节点，并映射至一个4 ×4 的二维Mesh NoC 中，再用本文所提出的方法对其进行VFI 划分，最小可靠性要求Pmin=0.999 999 99，VFI 最大数目限制为3.最终划分结果如图5所示.

图5 MMS 的VFI 划分结果

图5中，每个PE 节点中的括号里面标识了该PE 核上分配的任务，如ASIC1(1，3，5)表示任务1，3，5 分配至PE 节点ASIC1上.其中，VFI1的电压值为1.5 V，VFI2的电压值为1.2 V，VFI3的电压值为1.0 V.该结果相比于所有PE 节点均工作于最高电压1.5 V 下，可节约能耗37.9%，相比于文献［6］，可节约能耗10.1%.进一步验证了多重约束条件下的VFI 划分方法的有效性.

5 结语

为了解决NoC 的VFI 划分问题，本文提出了一种多约束条件下的VFI 划分方法，综合考虑数据包传输延时、VFI 数量及PE 可靠性等多重约束条件，采用ILP 算法优化NoC 系统总能耗.选取嵌入式系统综合评测E3S 测试基准中的多组应用实例和一个多媒体系统实例进行仿真实验，验证了所提出的VFI 划分方法的有效性，并给出了精确的评估结果.实验结果表明:在满足多重约束条件的同时，所提出的划分方法可有效降低NoC 总能耗，系统性能得到了提高.此外，该方法还可推广解决三维NoC 的VFI 划分问题，下一步的研究工作主要是三维NoC 中IP 核映射与VFI 划分问题的协同设计.

References)

［1］ Arjomand M，Sarbazi-Azad H.Voltage-frequency planning for thermal-aware，low-power design of regular 3-D NoCs［C］//23rd International Conference on VLSI Design.Bangalore，India，2010:57-62.

［2］ Jung H，Pedram M.Supervised learning based power management for multicore processors［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2010，29(9):1395-1408.

［3］ Sharifi S，Coskun A K，Rosing T S.Hybrid dynamic energy and thermal management in heterogeneous embedded multiprocessor SoCs ［C］//Proceedings of the 2010 Asia and South Pacific Design Automation Conference.Taipei，China，2010:873-878.

［4］ Ogras U Y，Marculescu R，Choudhary P，et al.Voltage frequency island partitioning for GALS-based networks-on-chip ［C］//Proceedings of the 44th Annual Conference on Design Automation.New York，2007:110-115.

［5］ Ogras U Y，Marculescu R，Marculescu D，et al.Design and management of voltage-frequency island partitioned networks-on-chip ［J］.IEEE Transactions on Very Large Scale Integration Systems，2009，17(3):330-341.

［6］ 刘斌，常振超，张兴明，等.一种基于遗传算法的片上网络电压岛划分方法［J］.计算机应用研究，2012，29(10):3740-3743.Liu Bin，Chang Zhenchao，Zhang Xingming，et al.Genetic algorithm based NoC voltage-frequency island partition method［J］.Application Research of Computers，2012，29(10):3740-3743.(in Chinese)

［7］ Lee W，Liu H Y，Chan Y W.Voltage island aware floorplanning for power and timing optimization［C］//IEEE/ACM International Conference on Computer-Aided Design.San Jose，CA，USA，2006:389-394.

［8］ Sengupta D，Saleh R A.Application-driven voltage-island partitioning for low-power system-on-chip design［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2009，28(3):316-326.

［9］ Ghosh P，Sen A.Energy efficient mapping and voltage islanding for regular NoC under design constraints［J］.International Journal of High Performance Systems Architecture，2010，2(3/4):132-144.

［10］ Popovich M，Friedman E G，Sotman M，et al.Onchip power distribution grids with multiple supply voltages for high performance integrated circuits ［C］//Proceedings of the 15th ACM Great Lakes symposium on VLSI.Chicago，IL，USA，2005:2-7.

［11］ 常政威，熊光泽，桑楠，等.基于电压岛的能量和可靠性感知NoC 映射［J］.计算机辅助设计与图形学学报，2009，21(1):19-26.Chang Zhengwei，Xiong Guangze，Sang Nan，et al.Energy-and reliability-aware mapping for NoC implemented with voltage islands［J］.Journal of Computer-Aided Design ＆ Computer Graphics，2009，21(1):19-26.(in Chinese)

［12］ 张剑贤，周端，杨银堂，等.处理器可靠性约束的电压频率岛NoC 能耗优化［J］.电子与信息学报，2011，33(9):2205-2211.Zhang Jianxian，Zhou Duan，Yang Yintang，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.(in Chinese)

［13］ Zhao B X，Aydin H，Zhu D.Reliability-aware dynamic voltage scaling for energy-constrained real-time embedded systems ［C］//2008 IEEE International Conference on Computer Design.Lake Tahoe，CA，USA，2008:633-639.

［14］ Yamamoto A Y，Ababei C.Unified system level reliability evaluation methodology for multiprocessor systems-on-chip［C］//2012 International Green Computing Conference.San Jose，CA，USA，2012:1-6.

［15］ Zhu D K，Melhem R，Mosse D.The effects of energy management on reliability in real-time embedded systems ［C］//Proceedings of the International Conference on Computer Aided Design.San Jose，CA，USA，2004:35-40.

［16］ Dick R.Embedded system synthesis benchmarks suite(E3S)［EB/OL］.(2013-06-20)［2014-6］.http://ziyang.eecs.umich.edu/ ～dickrp/e3s/.

［17］ Ge F，Wu N.Genetic algorithm based mapping and routing approach for network on chip architectures［J］.Chinese Journal of Electronics，2010，19(1):91-96.