基于数据重传的电压岛NoC能量优化

颛孙宗亮，李克秋＊

（大连理工大学 计算机科学与技术学院，辽宁 大连 116024）

0 引 言

随着半导体工艺的发展，片上系统（system on chip，SoC）未来可能会包含几十个或上百个IP（intellectual property，IP）核.传统的总线型拓扑结构不能满足未来片上系统对系统可扩展性、灵活性和能量有效性的要求［1］.采用路由和包交换技术的片上网络（network on chip，NoC）已经在多处理器片上系统中广泛采用［2］.在片上网络系统中，系统能耗变成NoC 研究领域中的热点，为了降低系统能耗，Ogras等在NoC 系统机制中引入了电压岛的概念［3］，他们把NoC 系统划分成不同的电压频率区域（岛），使每个核能调整自己所属的电压，让整个系统能更好地降低能耗.

Jang等在混合时钟FIFO（mixed clock FIFO，MCFIFO）和不同电压转化器（voltage level converter，VLC）的路由器能量消耗基础上，设计电压岛分配和静态电压分配方案［4］.他们在感知电压岛的情况下，设计出基于电压岛的能量消耗优化框架，有效地减少了复杂路由器的个数，从而有效降低NoC 系统的能耗.文献［5］描述在可靠性约束下的能耗NoC 映射问题，利用禁忌搜索的优化方法来降低系统能耗.文献［6］设计一种基于量子粒子群的电压岛划分算法，降低了NoC系统的能耗.文献［7］利用混线性规划方案解决IP映射与电压岛划分问题，提出一个基于贪婪的启发式算法解决此类问题.

以上方案是在NoC 支持电压岛（voltagefrequency island，VFI）的体系结构下来进行能耗的优化.然而在NoC 系统中，片上网络互连线上的误码是由于片上各种干扰源如电源干扰、电磁干扰等引起的.数据误码率计算公式可以由文献［8］得到.可以看出，供应电压（supply voltage）对数据传输误码率有很大的影响，在其他条件同等的情况下，路由器供应电压越低，其数据传输误码率越高.比如在噪声δ＝0.2的情况下，电压为1 V 和1.6V 数据误码率分别为6.2×10－3和3.16×10－5，相差将近200倍.

数据接收端的处理节点发现数据错误后，要求数据发送端的处理节点必须重新发送数据.在满足IP核计算周期和通信带宽的情况下，电压岛供应电压越低，系统能耗越低.

然而路由器供应电压越低，数据传输的误码率就越高，要求数据发送端重新发送的次数就越多，重新发送数据需要消耗通信能耗，特别在数据交换比较频繁的应用实例中，这种消耗十分明显［9］，因而在进行IP核映射与路由算法选择过程中应充分考虑这个因素.

现有的工作利用电压岛进行能耗优化［3－7］，但是没有考虑供应电压对误码率的影响及数据重传引起的能量消耗问题.另外也存在一定的局限，如文献［3］的方案存在容易形成电压孤岛的问题，文献［3－7］也没有考虑可以利用IP核从低电压岛往高电压岛移动的机制，来降低NoC 整体能耗.本文针对这些问题，提出一种基于数据重传机制的能耗模型，并定义考虑供应电压对数据传输影响情况的能耗优化问题.在此基础上设计能耗优化方案，其中包括电压岛划分、IP 核映射和路由路径选择等3个部分.

1 系统模型

本章首先描述支持电压岛的NoC 平台模型，处理节点放置一个IP核和一个路由器，每个处理节点有自己固定的电压和时钟频率.当相邻的处理节点的电压和时钟频率不一致时，用混合时钟FIFOs进行时钟频率转换.在考虑供应电压对数据传输可靠性影响下，重新定义NoC 系统能耗模型，并在此基础上，提出基于电压岛分配、IP 核映射和路由算法的NoC系统能耗优化设计方法.描述这个问题需要以下简单的定义.

1.1 定 义

定 义 1 应 用 通 信 图 （application communication graph）ACG（T，A）是一个有向图.顶点ti∈T表示一个IP核，边ai，j∈A表示从ti到tj通信任务.C（ai，j）表示从ti到tj通信量，B（ai，j）表示从ti到tj需要的通信带宽.每一个IP核都有自己的供应电压和阈值电压.

定义2 系统拓扑结构图（architecture topology graph）ATG（P，L）是一个有向图.顶点pi∈P表示系统结构一个节点，边li，j∈L表示相邻节点通信链路.Si，j表示pi到pj可用通信路径 的 集 合，si，j表 示pi到pj一 条 通 信 路 径表示pi到pj一位数据通信链路能耗.

定义3 映射函数MF（mapping function）：ACG→ATG映射一个IP核ti∈T到节点pi∈P上.φ（t，p）表示ACG中的IP核映射到ATG上，满足如下性质：

1.2 能耗模型

基于电压岛的NoC 系统能耗主要由处理器动态计算能耗、数据传输能耗和不同电压岛之间转换能耗组成.

根据文献［2］，动态计算能耗定义为

其中Ri是有效周期数，Ceff是有效切换电容，Vdd是IP核的供应电压.

其中f为时钟频率，Vth为阈值电压，k和α为常数.

在文献［2］中没有考虑电压岛概念情况下，所有链路传输一位数据能耗是相同的，定义为

其 中El，bit表 示 链 路 能 耗，Eb，bit表 示 缓 冲 区 能 耗，Es，bit表示交 换能耗.

在支持电压岛的NoC系统中，假设片上系统供应电压最大为Vmax，每一个路由器供应电压为Vi，则每传输一位数据从源节点ps到终节点pd能耗可以定义为

其中pi为定义2中从源节点ps到终节点pd通信路径上路由器.

每一个通信任务能耗为

其中Ck为通信任务k的通信流量.

不同电压岛之间转换能耗由MCFIFO 和VLC能耗构成，定义为

其中EMCFIFO和EVLC分别为MCFIFO 和VLC 能耗，m为MCFIFO 个数.

1.3 数据传输误码的模型

片上网络的模块化和可重用性等性质决定可以使用ECC（error control coding，ECC）方法来解决发生在瞬时的数据传输错误.ECC 方法一般有两种.一种是在数据链路层（hop－to－hop ECC），在每一个路由器配置一个ECC 编码器／解码器，每一个路由器能检测出错误数据，当数据错误发生时，数据接收端可以要求数据发送端重新发送或者用冗余线路来解决数据传输错误问题［10］.这种传输错误控制机制能有效地控制错误的传播，但是在每一个路由器上增加一个ECC 编码器／解码器就会增加系统能量的消耗和芯片面积的消耗.另一种可以替代的纠错机制发生在数据网络层（end－to－end ECC），这种纠错机制不发生在数据传输的中间路由器中，数据接收终点路由器发现数据错误，要求数据发送端路由器重新发送数据.这种纠错机制和链路层数据纠错相比，不会增加片上网络的能耗和面积消耗.在设计NoC 系统过程中，对芯片面积消耗有严格的限制.因此，本文采用在数据网络层的纠错机制，并采用片上网络数据传输超时重传机制ARQ（automatic repeat request，ARQ）［11］.

片上网络互连线上的误码是由片上各种干扰源如电源干扰、电磁干扰等引起的.一般用δ2N高斯白噪声电压来表示所有不同噪声源的总和的方差，ε表示一条信号线进行一次数据传输时发生错误的概率，根据文献［10］，ε定义为

从上面的模型可以得到一个报文在两个相连路由器传输的误码概率模型

其中k表示数据报文（packet）的数据位长度.

在数据接收端报文误码概率模型为

这里pi表示数据通信路径中的路由器，rpi是在pi路由器数据发生错误的概率.

在数据接收端的处理节点如果发现报文是不正确的，需要数据发送端重新传输数据.根据rps，pd可以得到平均正确数据传输的次数NARQ：

1.4 重新定义系统通信能耗模型

在基于电压岛的NoC 系统中，IP 核在考虑供应电压对数据误码率的影响下，采用片上网络数据传输超时重传机制.整个NoC系统数据通信的整体能耗可以重新定义为

1.5 问题定义

在基于电压岛的NoC 系统中，系统能耗问题可以形式化定义为给定应用通信图ACG（T，A）、NoC系统拓扑结构图ATG（P，L）和电压岛最大数，在考虑通信带宽约束和供应电压对数据传输误码率的影响下，考虑电压岛划分和寻找核集合C与资源节点集合T一一对应的映射函数φ（C），并在此基础上设计数据传输路由算法，使得NoC系统能耗最优.

其中

2 设计方法

本章描述整个设计方法和主要算法.设计方法主要包含3个部分：电压岛的划分、IP 核的映射和路由算法.本文在电压岛划分方面不但考虑计算能耗，同时考虑了通信能耗；IP 核的映射部分主要考虑总体通信流量最少和电压孤岛问题；在路由算法设计方面主要考虑数据通信能耗优化问题.下面从3个方面进行描述.

2.1 电压岛划分

电压岛划分问题是在给定电压等级集合和最大电压岛数的情况下，给每个IP核分派一个供应电压.假设给定最大电压岛数是m，电压等级为N，那么就有M＝C（N，m）种VF＝ ｛vf1，vf2，…，vfm｝的电压组合.用式（1）和（2）算出每个IP核所需要的最低供应电压Vi，对于任何vfi中最大的电压大于或者等于最大Vi，这个就是候选的vfi.这仅是IP核的计算能耗，没有考虑通信能耗和转换能耗.本文的算法结合这3个方面的能耗来进行电压岛分配.本文定义IP核从低电压岛往高电压岛移动能耗函数，如果函数值大于零表示可以移动，如果小于或等于零表示不可以移动.移动能耗函数定义如下：

其中D是IP核的映射平均距离.具体算法如下：

算法1 电压岛分配算法

2.2 IP核映射

进行IP核映射时应考虑电压孤岛的问题，因为这会带来算法效率和通信能耗优化方面的问题［3］.本文算法在保证整体通信流量最小的情况下，结合考虑电压孤岛问题.本文用算法2来解决这个问题，首先IP核之间按照通信流量进行降序排序，然后把电压岛候选的Tile放到CT 列表中.接下来在候选的CT 表中选择一个Tile来进行映射，如果此Tile有最大的相邻节点和已经映射IP核通信流量最少，再判断是否产生电压孤岛，如果不产生电压孤岛，则映射此候选Tile，如果产生电压孤岛，则再选择其他的候选Tile，如果找不到这样的Tile，选择第一个Tile来进行映射.映射此IP核以后，把该Tile相邻的节点都放到与IP 核具有相同电压岛CT 列表中，再进行剩余的IP核映射.算法描述如下：

算法2 IP核映射算法

2.3 路由算法

设计NoC系统中的路由算法时，路由死锁和活锁问题要充分考虑.本文用通信两个节点最短路由来解决路由活锁问题.在解决路由死锁问题方面，本文参照文献［12］解决路由死锁技术，首先找到所有通信任务的两点最短路径的集合.判断通信最短路径构成的链路依赖图［12］中是否有环路.如果没有环路，就进行路由选择.如果链路依赖图构成环路，则必须去掉一些链路来消除所有的环路，否则构成死锁.本文用最小代价函数η去掉这些环路，具体细节参考文献［12］.首先按通信流量进行排序，考虑供应电压对数据通信可靠性的影响，用式（11）和（6）计算通信能耗和转换能耗，选择通信能耗最少的路径，然后依次选择路由路径.

算法3 路由算法

3 性能评价

为了验证设计方案的性能，将6个具体应用实例映射到NoC系统结构上.把VOPD［13］（video object plane decoder）和MMS［14］（H263 编／解码器、MP3编／解码器）两种应用映射到4×4和5×5 NoC二维Mesh拓扑结构上.采取同样的方式，把E3S［15］中consumer、networking、auto－industry和telecom 等应用实例分别映射到3×3、3×3、4×4 和5×5NoC二维Mesh拓扑结构上.

将本文VFI－ARQ 方法与下列3种方法进行了比较：

（1）VFI－P：第一次提出电压岛设计方法［3］；

（2）VFI－R：基于电压岛感知设计方法［4］；

（3）VFI－S：基于整数线性规划设计方法［7］.

对6个应用实例在白噪声δ和供应电压取不同值的情况下做了3组实验.实验结果以VFI－P算法的电压岛优化结果为标准，进行归一化处理.第一组实验用比较大的供应电压V1＝｛1.5，1.6，1.7，1.8，1.9，2.0｝V，在白噪声δ1＝0.1情况下比较各种方法，系统能耗比较如图1所示.第二组实验在供应电压V1＝｛1.5，1.6，1.7，1.8，1.9，2.0｝V 不变和δ2＝0.2情况下比较各种方法，系统能耗比较如图2所示.第三组实验在δ1＝0.1，但是供应电压比较小，即V2＝｛0.6，0.8，0.9，1.0，1.2，1.5｝V 的情况下比较各种设计方法，能耗比较如图3所示.

图1 能量消耗比较（δ1，V1）Fig.1 Energy consumption comparison for（δ1，V1）

图2 能量消耗比较（δ2，V1）Fig.2 Energy consumption comparison for（δ2，V1）

图3 能量消耗比较（δ1，V2）Fig.3 Energy consumption comparison for（δ1，V2）

从图1～3可以看出，在基于电压岛NoC 系统中，考虑数据传输可靠性的情况下，供应电压数值越小，数据传输可靠性越差，要求重新传输的次数就越多，本文的设计方法更有效.在其他参数相同的情况下，噪声越大，数据传输可靠性越小，本文的设计方法同样表现出明显的优势.

本文在考虑数据重传的基础上，设计了新的降低系统能耗的方案VFI－ARQ.与VFI－P、VFIR、VFI－S 方案比较表明，系统能耗平均降低了17%、11%、7%.VFI－P方案只是考虑相邻电压岛的合并问题，没有考虑不相邻的电压岛合并问题，容易形成电压孤岛的现象.所以在VFI－P 方案中，会造成更多系统能量的消耗.方案VFI－S 和VFI－R 虽然考虑了电压孤岛的现象，也分析了电压孤岛产生的原因，有进一步降低系统能耗的效果，但是没有考虑IP核可以从低电压岛往高电压岛移动的问题，所以降低NoC整体能耗的效果不明显.本文在电压岛划分问题上不仅考虑了IP核的计算能耗，还考虑了IP核之间数据在重传下的通信能耗问题和电压孤岛等问题，实验结果表明该设计方案能有效地降低系统能耗.

4 结 语

已有的NoC映射设计方法中，没有考虑供应电压对数据传输重传的影响.本文将供应电压对通信数据误码率的传输模型引入NoC 设计方法中，改进数据传输能耗模型.实验结果表明在多级电压NoC模型中，考虑供应电压对数据传输可靠性的影响，能很好地优化数据通信能耗.下一步的研究工作主要在数据重传情况下电压岛分配机制中延长NoC系统的生存周期.

［1］ Dally W J，Towles B.Route packets，not wires：onchip interconnection networks ［C］／／ Design Automation Conference 2001，June 18－22，2001，Las Vegas，Nevada，USA.New York：ACM，2001：683－689.

［2］ Ye T T，Benini L，De Micheli G.Analysis of power consumption on switch fabrics in network routers［C］／／ The 39th Annual Design Automation Conference，June 10－14，2002，New Orleans，Louisiana，USA.New York：ACM，2002：524－529.

［3］ Ogras U Y，Marculescu R，Choudhary P，etal.Voltage－frequency island partitioning for GALSbased networks－on－chip ［C］／／The 44th Annual Design Automation Conference，June 4－8，2007，San Diego，California，USA.New York：ACM，2007：110－115.

［4］ Jang W，Ding D，Pan D Z.A voltage－frequency island aware energy optimization framework for networks－on－chip ［C］ ／／ 2008 IEEE／ACM International Conference on Computer－Aided Design.Piscataway：IEEE，2008：264－269.

［5］ 常政威，熊光泽，桑 楠，等.基于电压岛的能量和可靠性感知NoC映射［J］.计算机辅助设计与图形学学报，2009，21（1）：19－26.CHANG Zheng－wei，XIONG Guang－ze，SANG Nan，etal.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）

［6］ 张剑贤，周 端，杨银堂，等.处理器可靠性约束的电压频率岛NoC 能耗优化［J］.电子与信息学报，2011，33（9）：2205－2211.ZHANG Jian－xian，ZHOU Duan，YANG Yin－tang，etal.Energy optimization of NoC based on voltagefrequency islands under processor reliability constraints ［J］.Journal of Electronics ＆Information Technology，2011，33（9）：2205－2211.（in Chinese）

［7］ Ghosh P，Sen A.Efficient mapping and voltage islanding technique for energy minimization in NoC under design constraints ［C］／／The 2010 ACM Symposium on Applied Computing.New York：ACM，2010：535－541.

［8］ Raghunathan V，Srivastava M B，Gupta R K.A survey of techniques for energy efficient on－chip communication ［C］／／ The 40th Annual Design Automation Conference，June 2－6，2003，Anaheim，California，USA.New York：ACM，2003：900－905.

［9］ Varatkar G，Marculescu R.Traffic analysis for onchip networks design of multimedia applications［C］／／ The 39th Annual Design Automation Conference，June 10－14，2002，New Orleans，Louisiana，USA.New York：ACM，2002：795－800.

［10］ Bertozzi D，Benini L，De Micheli G.Error control schemes for on－chip communication links：the energy－reliability tradeoff［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2005，24（6）：818－831.

［11］ YU Qiao－yan，Ampadu P.A flexible parallel simulator for networks－on－chip with error control［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2010，29（1）：103－116.

［12］ Palesi M，Holsmark R，Kumar S，etal.Application specific routing algorithms for networks on chip ［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（3）：316－330.

［13］ 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.

［14］ HU Jing－cao，Marculescu R.Energy－aware mapping for tile－based NoC architectures under performance constraints［C］／／The 2003Asia and South Pacific Design Automation Conference，January 24，2003，Kitakyushu，Japan.New York：ACM，2003：233－239.

［15］ Dick R.Embedded system synthesis benchmarks suites（E3S）［EB／OL］.［2013－01－25］.http：／／www.ece.northwestern.edu／～dickrp／e3s／.