一種基于電壓島的DVFS控制算法*

劉 斌,張興明,閆佳佳

(1.國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南 鄭州 450002;2.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450000)

基于電壓島的動(dòng)態(tài)電壓頻率縮放DVFS(Dynamic Voltage and Frequency Scaling)技術(shù)能夠大幅度地降低片上網(wǎng)絡(luò)NoC(Network on Chip)的能耗,從而受到廣泛關(guān)注[1]。在基于電壓島的NoC上，電壓和頻率的改變以整個(gè)電壓島為單位，DVFS設(shè)計(jì)需要全面考慮電壓島內(nèi)所有的IP核。與針對(duì)單個(gè)IP核的DVFS控制算法相比,基于電壓島的DVFS控制算法需要考慮的因素更多，設(shè)計(jì)也更為復(fù)雜。

目前,針對(duì)基于電壓島的DVFS控制算法的研究并不多。為了應(yīng)對(duì)工作負(fù)載的快速變化，參考文獻(xiàn)[2]提出一種基于全局電壓島輸入隊(duì)列使用率的反饋控制算法。該算法使用反饋控制，較好地應(yīng)對(duì)了工作負(fù)載的變化。而參考文獻(xiàn)[3]指出參考文獻(xiàn)[2]的控制算法邏輯資源消耗過(guò)高，缺乏全局控制，在參考文獻(xiàn)[2]的基礎(chǔ)上提出CF-g反饋控制算法，該算法利用片上的g個(gè)輸入隊(duì)列,實(shí)現(xiàn)了電壓島簡(jiǎn)單、高效的工作電壓控制，達(dá)到了資源和效率的平衡，但是該算法并沒(méi)有大幅度降低片上邏輯資源的開(kāi)銷(xiāo)。同時(shí)，參考文獻(xiàn)[2]和參考文獻(xiàn)[3]的算法存在的共同問(wèn)題是只能控制電壓島的一個(gè)輸入隊(duì)列，導(dǎo)致整個(gè)系統(tǒng)的穩(wěn)定性較差。

針對(duì)上述問(wèn)題，本文依據(jù)參考文獻(xiàn)[4]提出的輸入隊(duì)列包到達(dá)模型提出一種基于島間隊(duì)列特征的DVFS控制算法。該算法使用電壓島的所有輸入/輸出隊(duì)列參與電壓島的電壓/頻率控制，提高了片上通信的穩(wěn)定性，引入島間隊(duì)列使用率和增長(zhǎng)率進(jìn)行負(fù)載預(yù)測(cè)，提高了算法的效率。

1 算法設(shè)計(jì)

1.1 電壓島間隊(duì)列使用率的數(shù)學(xué)模型

在基于電壓島的NoC上，電壓島間的每個(gè)鏈路兩端各有一個(gè)緩存隊(duì)列，如圖1所示，可將這種緩存隊(duì)列簡(jiǎn)稱(chēng)為島間隊(duì)列[4]。電壓島VFI1是隊(duì)列q的輸入電壓島，電壓島VFI2是隊(duì)列q的輸出電壓島;相應(yīng)地，隊(duì)列 q是電壓島VFI1的輸出隊(duì)列，也是電壓島VFI2的輸入隊(duì)列。設(shè)隊(duì)列 q的平均包到達(dá)速率為 f1λ，包服務(wù)速率為 f2μ，f1和 f2是第 k個(gè)控制周期內(nèi)(即[(k-1)T，kT))兩個(gè)電壓島的頻率，隊(duì)列q的使用率q(k)∈[0,1]可表示為：

使用率q(k)的增長(zhǎng)率q(k)可表示為：

島間隊(duì)列增長(zhǎng)率直接指示了當(dāng)前隊(duì)列使用率的變化：當(dāng) p(k)＞0時(shí)，增長(zhǎng)率為正，這時(shí)使用率 q(k)增加，即隊(duì)列中待處理的數(shù)據(jù)包增加；當(dāng)p(k)＜0時(shí)，使用率負(fù)增長(zhǎng)，此時(shí)的使用率減小，即隊(duì)列中待處理的數(shù)據(jù)包減少；當(dāng)p(k)=0時(shí)，表示當(dāng)前隊(duì)列使用率不變，該隊(duì)列處于平衡狀態(tài)。

1.2 算法思想描述

本文將電壓島的頻率和電壓劃分為幾個(gè)離散的等級(jí)，每次調(diào)整將增加或者降低一個(gè)等級(jí)。為了實(shí)現(xiàn)對(duì)工作負(fù)載的預(yù)測(cè)，引入島間隊(duì)列增長(zhǎng)率。另外，島間隊(duì)列使用率準(zhǔn)確描述了當(dāng)前隊(duì)列的使用情況，指示了當(dāng)前的片上通信狀況。本算法綜合兩者的信息得到當(dāng)前島間隊(duì)列對(duì)電壓島的頻率需求（升頻、降頻）。

針對(duì)當(dāng)前的控制算法無(wú)法達(dá)到控制所有島間隊(duì)列的問(wèn)題，通過(guò)全面考慮電壓島的輸入、輸出隊(duì)列對(duì)電壓島工作頻率的需求，綜合全局信息來(lái)配置電壓島的電壓和頻率。在保證通信穩(wěn)定的前提下盡量降低能耗，對(duì)于增頻請(qǐng)求和降頻請(qǐng)求，依據(jù)保證系統(tǒng)通信穩(wěn)定的原則，優(yōu)先處理增頻請(qǐng)求。

本算法采用全局控制方式，整體結(jié)構(gòu)如圖2所示。設(shè)控制周期為T(mén)，在第k個(gè)控制周期開(kāi)始時(shí)，對(duì)各個(gè)電壓島的頻率和島間隊(duì)列的使用率進(jìn)行采樣；然后將采樣信息輸入全局電壓/頻率控制模塊進(jìn)行運(yùn)算,得到當(dāng)前的島間隊(duì)列增長(zhǎng)率；之后，由全局電壓/頻率控制模塊依據(jù)DVFS控制算法得出各個(gè)電壓島在下個(gè)周期的電壓和頻率；最后，由電壓/頻率生成模塊對(duì)電壓和頻率進(jìn)行轉(zhuǎn)換，電壓和頻率轉(zhuǎn)換完成后，進(jìn)入第k+1個(gè)周期。

電壓島的電壓和頻率采用離散值，算法每次將電壓島的工作頻率升高或者降低一個(gè)等級(jí)。

1.3 使用島間隊(duì)列的DVFS控制算法原理

對(duì)于由J個(gè)電壓島組成的NoC，假設(shè)電壓島i有m個(gè)輸入/輸出隊(duì)列。本算法根據(jù)電壓島的輸入/輸出隊(duì)列的使用率q(k)和增長(zhǎng)率p(k)來(lái)控制電壓島的工作電壓,以實(shí)現(xiàn)DVFS控制?？紤]到輸入/輸出隊(duì)列對(duì)電壓島工作頻率的不同需求，將兩者分開(kāi)考慮，其對(duì)應(yīng)的控制請(qǐng)求可分為輸入隊(duì)列請(qǐng)求和輸出隊(duì)列請(qǐng)求。

本算法通過(guò)綜合q(k)和 p(k)的信息控制電壓島的頻率，使p(k)在區(qū)間[0，1)之內(nèi)變化。其原理如下：

在圖 1中，對(duì)于隊(duì)列 q，當(dāng) p(k)＞0時(shí)，若保持電壓島VFI1的頻率 f1和電壓島VFI2的頻率 f2不變,則隊(duì)列的使用率q(k)會(huì)持續(xù)增加。這種情況下，當(dāng)q(k)較小時(shí)，無(wú)需考慮降低頻率 f2或者增加頻率 f1；當(dāng) q(k)較大時(shí)，為避免隊(duì)列擁塞(即防止 q(k)=1)，為其設(shè)置門(mén)限值 ThH，當(dāng)q(k)到達(dá)門(mén)限值ThH時(shí)，可以降低輸入電壓島的頻率f1或者增加輸出電壓島的頻率f2；當(dāng)使用率 q(k)很小時(shí)，若降低隊(duì)列的輸出電壓島頻率 f2，則增長(zhǎng)率p(k)＞0變大，加快了q(k)增加的速率。為了解決此時(shí)能否降低f2的問(wèn)題，設(shè)置了 q(k)的可降頻門(mén)限 ThD。當(dāng)p(k)＞0，q(k)＜ThD時(shí),可以降低隊(duì)列的輸出電壓島的頻率；當(dāng)增長(zhǎng)率p(k)＞0時(shí)，如果隊(duì)列的輸入電壓島的頻率f1將在下一個(gè)控制周期被提高，按照式(2)推斷增長(zhǎng)率 p(k)會(huì)變大，此時(shí)有必要降低輸出電壓島的頻率f2的門(mén)限，令這個(gè)門(mén)限值為T(mén)hI,本文稱(chēng)之為輸出電壓島從動(dòng)升頻門(mén)限。

當(dāng) p(k)＜0時(shí)，若保持 f1和 f2不變，隊(duì)列的使用率 q(k)會(huì)持續(xù)減小，此時(shí)不必考慮q(k)過(guò)高而導(dǎo)致隊(duì)列擁塞；當(dāng)使用率q(k)過(guò)低時(shí)，可以增加輸入電壓島的頻率f1或者降低輸出電壓島的頻率f2。為了降低能耗，本算法不主動(dòng)增加輸入電壓島的頻率，這時(shí)設(shè)置隊(duì)列使用率q(k)的門(mén)限ThL，當(dāng)q(k)到達(dá)此門(mén)限值時(shí)，降低輸出電壓島的頻率；若輸出電壓島的頻率f2降低，則增長(zhǎng)率變大，使用率有可能會(huì)增加，此時(shí)，若 q(k)∈[ThH,1]，則不能降低輸出電壓島的頻率 f2；若 q(k)∈[ThL,ThH），則可以降低輸出電壓島頻率f2。

當(dāng)p(k)=0時(shí)，隊(duì)列的輸入輸出達(dá)到平衡，隊(duì)列對(duì)電壓島的頻率沒(méi)有升降請(qǐng)求。

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

2 算法實(shí)現(xiàn)過(guò)程

(1)第 k個(gè)周期開(kāi)始，計(jì)算 q(k)和 p(k)。

(2)根據(jù)表 1、表 2形成輸入隊(duì)列請(qǐng)求和輸出隊(duì)列請(qǐng)求。

(3)處理輸入隊(duì)列請(qǐng)求中的增加頻率請(qǐng)求，對(duì)同一電壓島的增頻操作不疊加。

(4)對(duì)于有增頻操作的電壓島，如果其輸出隊(duì)列中有處于從動(dòng)升頻狀態(tài)的，增加其對(duì)應(yīng)電壓島的電壓、頻率，對(duì)同一電壓島的增頻操作不疊加。

(5)處理輸出隊(duì)列請(qǐng)求降頻，對(duì)被請(qǐng)求的電壓島處于可降頻狀態(tài)的進(jìn)行降壓、降頻處理。

(6)本輪電壓、頻率調(diào)整結(jié)束，返回到步驟(1)，進(jìn)行下一周期的電壓頻率調(diào)整。

表1 增長(zhǎng)率為正的島間隊(duì)列控制請(qǐng)求

表2 增長(zhǎng)率不為正的島間隊(duì)列控制請(qǐng)求

3 仿真分析

本文采用Matlab進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)可分為兩部分。第一部分進(jìn)行了能耗性能的驗(yàn)證，該部分用到了Auto-industry、Consumer、Networking、Office-automation 來(lái)自E3S[5]和一個(gè)OPD五種應(yīng)用實(shí)例[6]。第二部分采用OPD進(jìn)行了算法可靠性的驗(yàn)證。

電壓島的工作電壓的值域由參考文獻(xiàn)[7]給出，電壓的取值范圍是0.5 V,0.7 V、0.9 V、1 V及1.1 V。相應(yīng)的最大工作頻率為0.8 GHz、0.9 GHz、1 GHz、1.1 GHz 及 1.2 GHz。整個(gè)系統(tǒng)由3個(gè)電壓島組成，共有20個(gè)島間隊(duì)列。實(shí)驗(yàn)中用到的ThL、ThH參照參考文獻(xiàn)[8]。

3.1 能耗性能對(duì)比

實(shí)驗(yàn)以沒(méi)有實(shí)現(xiàn)DVFS控制NoC的能耗為參照，將本算法與參考文獻(xiàn)[3]提出的CF-g算法進(jìn)行了總能耗、EDP兩方面的歸一化對(duì)比，其結(jié)果如圖3所示,其中未進(jìn)行DVFS控制的能耗稱(chēng)為NOP。

從圖3可以看出，本算法的總能耗和CF-g算法相近。在五種應(yīng)用中，相比于NOP，CF-g算法平均降低了16.19%的總能耗，本文算法平均降低了19.85%的總能耗。本文算法沒(méi)有獲得較大的能耗降低空間，這是由于算法采用了全局控制機(jī)制，增加了可控的島間隊(duì)列的數(shù)量，犧牲了一定的能耗降低空間。從圖4的EDP對(duì)比中可以看出，本文算法的能耗性能大大提升，相比于NOP，本算法獲得了21.82%的性能提高。相比于CF算法，本文算法也有6.14%的性能提高。

3.2 算法穩(wěn)定性驗(yàn)證

為了驗(yàn)證本算法的穩(wěn)定性，實(shí)驗(yàn)采用應(yīng)用實(shí)例OPD，在其工作負(fù)載從1 000倍到0.01倍變化時(shí)，分別使用三種算法進(jìn)行DVFS控制。三種算法曾達(dá)到飽和的島間隊(duì)列數(shù)量的變化如圖5所示。從實(shí)驗(yàn)數(shù)據(jù)中可以看出，在過(guò)載的情況下，使用三種算法所有的島間隊(duì)列都曾達(dá)到飽和。隨著工作負(fù)載降低，本算法曾達(dá)到飽和的島間隊(duì)列數(shù)量明顯減少。當(dāng)負(fù)載強(qiáng)度降至10倍時(shí)，本文算法只有6個(gè)隊(duì)列曾達(dá)到飽和，而FC和CF-g算法由于只有3個(gè)可控隊(duì)列，其他不可控隊(duì)列都曾達(dá)到飽和，因此有17個(gè)島間隊(duì)列曾達(dá)到飽和。在正常負(fù)載下，本算法能夠穩(wěn)定控制各島間隊(duì)列沒(méi)有達(dá)到飽和，而FC和CF-g分別有8個(gè)和5個(gè)島間隊(duì)列曾達(dá)到飽和。實(shí)驗(yàn)數(shù)據(jù)表明，相比于FC和CF-g算法，本文算法的通信穩(wěn)定性較強(qiáng)。

本文提出了一種使用島間隊(duì)列的DVFS控制算法，利用島間隊(duì)列增長(zhǎng)率和使用率兩個(gè)參數(shù)來(lái)控制電壓島的電壓/頻率變化。仿真結(jié)果表明，本算法保障了片上通信的穩(wěn)定性，明顯提高了系統(tǒng)吞吐量。

[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.