一种基于电压岛的DVFS控制算法*

刘 斌,张兴明,闫佳佳

(1.国家数字交换系统工程技术研究中心,河南 郑州 450002;2.郑州大学 信息工程学院，河南 郑州450000)

基于电压岛的动态电压频率缩放DVFS(Dynamic Voltage and Frequency Scaling)技术能够大幅度地降低片上网络NoC(Network on Chip)的能耗,从而受到广泛关注[1]。在基于电压岛的NoC上，电压和频率的改变以整个电压岛为单位，DVFS设计需要全面考虑电压岛内所有的IP核。与针对单个IP核的DVFS控制算法相比,基于电压岛的DVFS控制算法需要考虑的因素更多，设计也更为复杂。

目前,针对基于电压岛的DVFS控制算法的研究并不多。为了应对工作负载的快速变化，参考文献[2]提出一种基于全局电压岛输入队列使用率的反馈控制算法。该算法使用反馈控制，较好地应对了工作负载的变化。而参考文献[3]指出参考文献[2]的控制算法逻辑资源消耗过高，缺乏全局控制，在参考文献[2]的基础上提出CF-g反馈控制算法，该算法利用片上的g个输入队列,实现了电压岛简单、高效的工作电压控制，达到了资源和效率的平衡，但是该算法并没有大幅度降低片上逻辑资源的开销。同时，参考文献[2]和参考文献[3]的算法存在的共同问题是只能控制电压岛的一个输入队列，导致整个系统的稳定性较差。

针对上述问题，本文依据参考文献[4]提出的输入队列包到达模型提出一种基于岛间队列特征的DVFS控制算法。该算法使用电压岛的所有输入/输出队列参与电压岛的电压/频率控制，提高了片上通信的稳定性，引入岛间队列使用率和增长率进行负载预测，提高了算法的效率。

1 算法设计

1.1 电压岛间队列使用率的数学模型

在基于电压岛的NoC上，电压岛间的每个链路两端各有一个缓存队列，如图1所示，可将这种缓存队列简称为岛间队列[4]。电压岛VFI1是队列q的输入电压岛，电压岛VFI2是队列q的输出电压岛;相应地，队列 q是电压岛VFI1的输出队列，也是电压岛VFI2的输入队列。设队列 q的平均包到达速率为 f1λ，包服务速率为 f2μ，f1和 f2是第 k个控制周期内(即[(k-1)T，kT))两个电压岛的频率，队列q的使用率q(k)∈[0,1]可表示为：

使用率q(k)的增长率q(k)可表示为：

岛间队列增长率直接指示了当前队列使用率的变化：当 p(k)＞0时，增长率为正，这时使用率 q(k)增加，即队列中待处理的数据包增加；当p(k)＜0时，使用率负增长，此时的使用率减小，即队列中待处理的数据包减少；当p(k)=0时，表示当前队列使用率不变，该队列处于平衡状态。

1.2 算法思想描述

本文将电压岛的频率和电压划分为几个离散的等级，每次调整将增加或者降低一个等级。为了实现对工作负载的预测，引入岛间队列增长率。另外，岛间队列使用率准确描述了当前队列的使用情况，指示了当前的片上通信状况。本算法综合两者的信息得到当前岛间队列对电压岛的频率需求（升频、降频）。

针对当前的控制算法无法达到控制所有岛间队列的问题，通过全面考虑电压岛的输入、输出队列对电压岛工作频率的需求，综合全局信息来配置电压岛的电压和频率。在保证通信稳定的前提下尽量降低能耗，对于增频请求和降频请求，依据保证系统通信稳定的原则，优先处理增频请求。

本算法采用全局控制方式，整体结构如图2所示。设控制周期为T，在第k个控制周期开始时，对各个电压岛的频率和岛间队列的使用率进行采样；然后将采样信息输入全局电压/频率控制模块进行运算,得到当前的岛间队列增长率；之后，由全局电压/频率控制模块依据DVFS控制算法得出各个电压岛在下个周期的电压和频率；最后，由电压/频率生成模块对电压和频率进行转换，电压和频率转换完成后，进入第k+1个周期。

电压岛的电压和频率采用离散值，算法每次将电压岛的工作频率升高或者降低一个等级。

1.3 使用岛间队列的DVFS控制算法原理

对于由J个电压岛组成的NoC，假设电压岛i有m个输入/输出队列。本算法根据电压岛的输入/输出队列的使用率q(k)和增长率p(k)来控制电压岛的工作电压,以实现DVFS控制。考虑到输入/输出队列对电压岛工作频率的不同需求，将两者分开考虑，其对应的控制请求可分为输入队列请求和输出队列请求。

本算法通过综合q(k)和 p(k)的信息控制电压岛的频率，使p(k)在区间[0，1)之内变化。其原理如下：

在图 1中，对于队列 q，当 p(k)＞0时，若保持电压岛VFI1的频率 f1和电压岛VFI2的频率 f2不变,则队列的使用率q(k)会持续增加。这种情况下，当q(k)较小时，无需考虑降低频率 f2或者增加频率 f1；当 q(k)较大时，为避免队列拥塞(即防止 q(k)=1)，为其设置门限值 ThH，当q(k)到达门限值ThH时，可以降低输入电压岛的频率f1或者增加输出电压岛的频率f2；当使用率 q(k)很小时，若降低队列的输出电压岛频率 f2，则增长率p(k)＞0变大，加快了q(k)增加的速率。为了解决此时能否降低f2的问题，设置了 q(k)的可降频门限 ThD。当p(k)＞0，q(k)＜ThD时,可以降低队列的输出电压岛的频率；当增长率p(k)＞0时，如果队列的输入电压岛的频率f1将在下一个控制周期被提高，按照式(2)推断增长率 p(k)会变大，此时有必要降低输出电压岛的频率f2的门限，令这个门限值为ThI,本文称之为输出电压岛从动升频门限。

当 p(k)＜0时，若保持 f1和 f2不变，队列的使用率 q(k)会持续减小，此时不必考虑q(k)过高而导致队列拥塞；当使用率q(k)过低时，可以增加输入电压岛的频率f1或者降低输出电压岛的频率f2。为了降低能耗，本算法不主动增加输入电压岛的频率，这时设置队列使用率q(k)的门限ThL，当q(k)到达此门限值时，降低输出电压岛的频率；若输出电压岛的频率f2降低，则增长率变大，使用率有可能会增加，此时，若 q(k)∈[ThH,1]，则不能降低输出电压岛的频率 f2；若 q(k)∈[ThL,ThH），则可以降低输出电压岛频率f2。

当p(k)=0时，队列的输入输出达到平衡，队列对电压岛的频率没有升降请求。

本算法的控制方法如表1、表2所示。

2 算法实现过程

(1)第 k个周期开始，计算 q(k)和 p(k)。

(2)根据表 1、表 2形成输入队列请求和输出队列请求。

(3)处理输入队列请求中的增加频率请求，对同一电压岛的增频操作不叠加。

(4)对于有增频操作的电压岛，如果其输出队列中有处于从动升频状态的，增加其对应电压岛的电压、频率，对同一电压岛的增频操作不叠加。

(5)处理输出队列请求降频，对被请求的电压岛处于可降频状态的进行降压、降频处理。

(6)本轮电压、频率调整结束，返回到步骤(1)，进行下一周期的电压频率调整。

表1 增长率为正的岛间队列控制请求

表2 增长率不为正的岛间队列控制请求

3 仿真分析

本文采用Matlab进行仿真实验，实验可分为两部分。第一部分进行了能耗性能的验证，该部分用到了Auto-industry、Consumer、Networking、Office-automation 来自E3S[5]和一个OPD五种应用实例[6]。第二部分采用OPD进行了算法可靠性的验证。

电压岛的工作电压的值域由参考文献[7]给出，电压的取值范围是0.5 V,0.7 V、0.9 V、1 V及1.1 V。相应的最大工作频率为0.8 GHz、0.9 GHz、1 GHz、1.1 GHz 及 1.2 GHz。整个系统由3个电压岛组成，共有20个岛间队列。实验中用到的ThL、ThH参照参考文献[8]。

3.1 能耗性能对比

实验以没有实现DVFS控制NoC的能耗为参照，将本算法与参考文献[3]提出的CF-g算法进行了总能耗、EDP两方面的归一化对比，其结果如图3所示,其中未进行DVFS控制的能耗称为NOP。

从图3可以看出，本算法的总能耗和CF-g算法相近。在五种应用中，相比于NOP，CF-g算法平均降低了16.19%的总能耗，本文算法平均降低了19.85%的总能耗。本文算法没有获得较大的能耗降低空间，这是由于算法采用了全局控制机制，增加了可控的岛间队列的数量，牺牲了一定的能耗降低空间。从图4的EDP对比中可以看出，本文算法的能耗性能大大提升，相比于NOP，本算法获得了21.82%的性能提高。相比于CF算法，本文算法也有6.14%的性能提高。

3.2 算法稳定性验证

为了验证本算法的稳定性，实验采用应用实例OPD，在其工作负载从1 000倍到0.01倍变化时，分别使用三种算法进行DVFS控制。三种算法曾达到饱和的岛间队列数量的变化如图5所示。从实验数据中可以看出，在过载的情况下，使用三种算法所有的岛间队列都曾达到饱和。随着工作负载降低，本算法曾达到饱和的岛间队列数量明显减少。当负载强度降至10倍时，本文算法只有6个队列曾达到饱和，而FC和CF-g算法由于只有3个可控队列，其他不可控队列都曾达到饱和，因此有17个岛间队列曾达到饱和。在正常负载下，本算法能够稳定控制各岛间队列没有达到饱和，而FC和CF-g分别有8个和5个岛间队列曾达到饱和。实验数据表明，相比于FC和CF-g算法，本文算法的通信稳定性较强。

本文提出了一种使用岛间队列的DVFS控制算法，利用岛间队列增长率和使用率两个参数来控制电压岛的电压/频率变化。仿真结果表明，本算法保障了片上通信的稳定性，明显提高了系统吞吐量。

[1]Liang Guang,LILJEBERG P,NIGUSSIE E,et al.A review of dynamic power management methods in NoC under emerging design considerations[C].In:Norchip Conference,2009.Trondheim,2009.

[2]OGRARS U Y,MARCULESCU R,MARCULESCU D.Variation-adaptive feedback control for networks-on-chip with multiple clock domains[C].New York:Proceedings of the 45th annual Design Automation Conference,2008:614-619.

[3]GARG S,MARCULESCU D,MARCULESCU R.Custom feedback control:enabling truly scalable on-chip power management for MPSoCs[C].Austin:Low-Power Electronics and Design,2010 ACM/IEEE International Symposium on,2010:425-430

[4]JUANG P,Wu Qian.Coordinated,distributed,formal energy management of chip multiprocessors[C].Princeton Univ:Low Power Electronics and Design,2005.Proceedings of the 2005 International Symposium on,2005:127-130.

[5]DICK R.Embedded system synthesis benchmarks suites(E3S)[EB/OL](2011.12.14).http://www.ece.northwestern.edu.

[6]ERIK B,VAN D T,JASPERS E G T Jaspers.Mapping of MPEG-4 decoding on flexible architecture platform[A].In:SPIE Conference on Visualization and Data Analysis[C].San Jose,CA,USA:IEEE,2002:1-13.

[7]HOWARD J,DIGHE S,SRIRAM R,et al.A 48-Core IA-32 processor in 45 nm CMOS using on-die messagepassing and DVFS for performance and power scaling[J].IEEE Journal of Solid-State Circuits,2011,46(1):173-183.

[8]RAHIMI A,SALEHI M E.MOHAMMADI S,et al.Dynamic voltage scaling for fully asynchronous NoCs using FIFO threshold levels[C].Tehran:Computer Architecture and Digital Systems,2010 15th CSI International Symposium on,2010:43-48.