基于電壓島的動態電壓頻率縮放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]可表示為：
　　

    島間隊列增長率直接指示了當前隊列使用率的變化：當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)&isin;[ThH,1]，則不能降低輸出電壓島的頻率f2；若q(k)&isin;[ThL,ThH），則可以降低輸出電壓島頻率f2。
    當p(k)=0時，隊列的輸入輸出達到平衡，隊列對電壓島的頻率沒有升降請求。
    本算法的控制方法如表1、表2所示。

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

    本文提出了一種使用島間隊列的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.