基于ＤＶＳ的實(shí)時(shí)多核嵌入式系統(tǒng)低功耗算法

（同濟(jì)大學(xué) 電信學(xué)院 計(jì)算機(jī)系， 上海 201804）



摘 要：動(dòng)態(tài)電壓調(diào)整（DVS）是低功耗設(shè)計(jì)方法中最基本的技術(shù)。然而，大部分的算法是基于單處理器平臺的，并且僅考慮了相互獨(dú)立的任務(wù)，這時(shí)使用DVS往往不能取得較好的效果。基于DVS提出了一種循環(huán)旋轉(zhuǎn)調(diào)度技術(shù)來降低功耗，通過對程序中的循環(huán)進(jìn)行重組，使得在滿足時(shí)限的同時(shí)功耗最小，同時(shí)也考慮了電壓轉(zhuǎn)換所消耗的時(shí)間和功耗。

關(guān)鍵詞：嵌入式系統(tǒng)； 動(dòng)態(tài)電壓調(diào)節(jié)； 低功耗設(shè)計(jì)； 旋轉(zhuǎn)調(diào)度

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)01012702



Realtime dynamic voltage scaling algorithm for

lowpower multicore embedded system

WANG Lisheng， GUO Zhenke



(Dept. of Computer， Institute of Telecommunication， Tongji University， Shanghai 201804， China)



Abstract:DVS(dynamic voltage scaling) is one of the most powerful techniques to reduce energy consumption. However， most algorithms are based on uniprocessor and only consider independent tasks. In this situation， DVS will not get the best solution. This paper introduced a technology to reduce energy consumption which used rotation scheduling based on DVS. The algorithm repeatedly regrouped a loop and decreased the energy as much as possible within a timing constraint. Both time and energy overhead during a voltage transition was considered in this work.

Key words：embedded system; DVS; lowpower design； rotation scheduling

低功耗設(shè)計(jì)正在成為嵌入式實(shí)時(shí)系統(tǒng)軟硬件設(shè)計(jì)中所關(guān)注的重點(diǎn)，而動(dòng)態(tài)電壓調(diào)整(dynamic voltage scaling，DVS)是一種有效的節(jié)能技術(shù)。其核心思想是：在滿足任務(wù)實(shí)時(shí)要求的前提下，動(dòng)態(tài)調(diào)整處理器的運(yùn)行頻率，使得處理器的工作電壓不必總是處于最大值，從而起到節(jié)能的作用。

近年來很多學(xué)者對利用動(dòng)態(tài)電壓調(diào)節(jié)進(jìn)行功耗優(yōu)化進(jìn)行了深入的研究。根據(jù)文獻(xiàn)[1]，Weiser等人提出了基于時(shí)間片的DVS策略，Grunwald等人的研究與Pering等人的研究共同催生出了基于任務(wù)的DVS策略。以上這些工作有效地降低了功耗，但是都沒有考慮對循環(huán)的優(yōu)化和電壓轉(zhuǎn)換的開銷。文獻(xiàn)[2]中，Saputra等人用一些經(jīng)典的面向循環(huán)的編譯優(yōu)化技術(shù)來降低執(zhí)行時(shí)間并使用DVS來減小功耗。然而，在整個(gè)循環(huán)中始終都是一種電壓。

在大部分嵌入式系統(tǒng)應(yīng)用中，遞歸和循環(huán)的運(yùn)算結(jié)構(gòu)往往是程序中最消耗運(yùn)行時(shí)間及內(nèi)存的部分。本文通過DVS在實(shí)時(shí)應(yīng)用領(lǐng)域采用循環(huán)優(yōu)化進(jìn)行了分析，并且考慮了電平轉(zhuǎn)換的開銷，通過不斷重組一個(gè)基于旋轉(zhuǎn)調(diào)度的循環(huán)體來減少功耗。

1 相關(guān)知識

1.1 循環(huán)DFG和靜態(tài)調(diào)度

循環(huán)可以用數(shù)據(jù)流圖(data flow graph，DFG)來表達(dá)，稱為循環(huán)DFG。一個(gè)循環(huán)DFG表示為G=〈V， E， d，T〉。其中：G是一個(gè)帶有節(jié)點(diǎn)權(quán)重和邊權(quán)重的有向圖；V是一個(gè)節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)表示循環(huán)中的一個(gè)計(jì)算任務(wù)，節(jié)點(diǎn)邊的數(shù)字表示每個(gè)節(jié)點(diǎn)的計(jì)算時(shí)間T(u)；E是一個(gè)邊集，邊代表節(jié)點(diǎn)間的數(shù)據(jù)依賴，一般用延遲（delay）來表示。同一次循環(huán)的數(shù)據(jù)依賴用無延遲的邊表達(dá)，不同次循環(huán)間的數(shù)據(jù)依賴用帶延遲的邊表示。對于任意一條邊，d(e)代表了該邊的延遲；延遲用“｜”符號來表示，d(e)的值表示“｜”的個(gè)數(shù)。

一個(gè)循環(huán)DFG的靜態(tài)調(diào)度是一個(gè)循環(huán)的重復(fù)執(zhí)行格式。靜態(tài)調(diào)度必須符合依賴關(guān)系，這種依賴關(guān)系表現(xiàn)為DFG的有向無環(huán)圖DAG部分。把所有有延遲的邊從DFG中取出便得到DAG。圖1（a）是一個(gè)循環(huán)過程，（b）是對應(yīng)的循環(huán)DFG，（c）是靜態(tài)調(diào)度的結(jié)果。

1.2 重定時(shí)和旋轉(zhuǎn)調(diào)度

重定時(shí)（retiming）是軟件流水的一種重要技術(shù)，它通過重新分配DFG中的延遲來達(dá)到減少循環(huán)周期的目的。對于DFG圖G（V，E，d，t），將來自節(jié)點(diǎn)v的每條輸入邊的延遲，通過v推向其每條輸出邊。這種方法保持了節(jié)點(diǎn)間的數(shù)據(jù)依賴，僅僅改變節(jié)點(diǎn)初始分配值，而初始分配可以通過裝入來實(shí)現(xiàn)。

通過一個(gè)例子來觀察重定時(shí)的效果。如圖2所示，將輸入節(jié)點(diǎn)A的一個(gè)延遲推向其輸出，節(jié)點(diǎn)A的第i次與節(jié)點(diǎn)B的第i-1次由于無數(shù)據(jù)依賴，在滿足資源限制的條件下可以同時(shí)運(yùn)行，循環(huán)周期也從原來的2變?yōu)?（假設(shè)每個(gè)節(jié)點(diǎn)的計(jì)算時(shí)間為1）。

一般地，當(dāng)一個(gè)循環(huán)DFG中沒有資源的限定時(shí)可以通過重定時(shí)來優(yōu)化調(diào)度。然而，重定時(shí)技術(shù)算法復(fù)雜，需要專門的判決準(zhǔn)則，而且未考慮資源限制的影響。

旋轉(zhuǎn)調(diào)度[3，4]常被用來對有資源限制的循環(huán)進(jìn)行調(diào)度，它把一個(gè)調(diào)度轉(zhuǎn)換成更加復(fù)雜的迭代。通過旋轉(zhuǎn)調(diào)度，可以有機(jī)會得到更少的調(diào)度長度，給DVS提供了更多功耗優(yōu)化的機(jī)會。從程序的角度來看，旋轉(zhuǎn)調(diào)度重組了循環(huán)體并且減少了節(jié)點(diǎn)間的內(nèi)依賴。這樣，轉(zhuǎn)換后得到的新的循環(huán)具有更好的并行性。

2 模型

CMOS電路的功耗由兩部分組成：靜態(tài)功耗和動(dòng)態(tài)功耗。靜態(tài)功耗主要由泄漏電流和開啟電流產(chǎn)生，其功耗非常小，可以忽略。由電容的充電與放電形成的動(dòng)態(tài)功耗是CMOS電路的主要功耗來源。根據(jù)文獻(xiàn)[5]，動(dòng)態(tài)功耗的計(jì)算公式為E=CswV 2ddf 。其中：Vdd是工作電壓；Csw是負(fù)載電容；f是時(shí)鐘頻率。而處理器速度fCLK與供電電壓Vdd之間的關(guān)系為

fCLK=η*[(Vdd-Vth)2/Vdd](1)

其中：η是設(shè)備相關(guān)常數(shù)，Vth是系統(tǒng)門限電壓。可以看出，當(dāng)Vdd＞＞Vth時(shí)，fCLK與壓Vdd之間幾乎是線性的關(guān)系。由于時(shí)鐘周期和處理器速度成反比，即TC=f-1CLK。對于節(jié)點(diǎn)u，N(u)代表節(jié)點(diǎn)u所需要的時(shí)鐘周期數(shù)，則節(jié)點(diǎn)u的執(zhí)行時(shí)間為

tu=N(u)×TC=N(u)×[η(Vdd-Vth)2/Vdd](2)

執(zhí)行節(jié)點(diǎn)u所消耗的功耗為

Eu=N(u)×CSW×V2dd(3)

可以看出，當(dāng)降低處理器供電電壓時(shí)，任務(wù)的功耗將平方級減少，而任務(wù)的執(zhí)行時(shí)間則會線性地增長。本文的策略就是在滿足任務(wù)時(shí)限的條件下，以任務(wù)的執(zhí)行時(shí)間的線性增長來換取功耗的平方級降低。假設(shè)節(jié)點(diǎn)在低電壓時(shí)的執(zhí)行時(shí)間是高電壓時(shí)的兩倍，高電壓時(shí)的功耗是低電壓時(shí)的四倍。

轉(zhuǎn)換時(shí)間和轉(zhuǎn)換功耗方面，每個(gè)處理器核都有一個(gè)電壓的有限集，通過電壓設(shè)置指令，每個(gè)處理器核可以獨(dú)立地改變自身的供應(yīng)電壓而不影響其他的處理器核。根據(jù)文獻(xiàn)[6]，當(dāng)電壓從Vdd1→Vdd2時(shí)，轉(zhuǎn)換的時(shí)間和轉(zhuǎn)換功耗只隨電壓差改變，與任務(wù)的執(zhí)行無關(guān)，因此本文將轉(zhuǎn)換時(shí)間和轉(zhuǎn)換功耗設(shè)為定值。對于帶有睡眠模式的處理器，考慮到像存儲器之類組件的同步延遲，時(shí)間轉(zhuǎn)換會比較大。睡眠模式下的轉(zhuǎn)換時(shí)間和功耗可以從芯片手冊中查到。

3 算法描述

本算法用列表調(diào)度得出一個(gè)初始的調(diào)度，通過循環(huán)調(diào)度不斷重組一個(gè)循環(huán)，在循環(huán)的過程中用DVS來盡可能地降低功耗，并且整個(gè)過程都在時(shí)限允許的條件下。

假設(shè)當(dāng)前的嵌入式系統(tǒng)中有兩個(gè)處理器核，每個(gè)DVS處理器有兩種電壓/頻率級別，根據(jù)文獻(xiàn)[5]的功率模型，假設(shè)CSW=1 nF；電壓/頻率對為（2 V，1 GHz）和（1 V，0.5 GHz）。因此可得執(zhí)行一條指令的功耗和時(shí)間分別為PH=4 W，PL=0.5 W，TH=1 ns，TL=2 ns。這里PH和PL分別代表高功耗和低功耗，TH和TL分別代表兩種時(shí)鐘周期。一個(gè)節(jié)點(diǎn)所需要的時(shí)鐘周期個(gè)數(shù)是不能被DVS改變的，因此可以得到每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間和功耗。表1列出了圖1（b）的DFG中每個(gè)節(jié)點(diǎn)分別在高低電壓下的功耗和執(zhí)行時(shí)間。時(shí)鐘的單位是ns，功耗的單位是nJ。電壓的轉(zhuǎn)變會導(dǎo)致時(shí)間和功耗的開銷，假設(shè)電壓每轉(zhuǎn)變一次消耗1 ns的時(shí)間和1 nJ的功耗。算法中將執(zhí)行一次循環(huán)所需要的時(shí)間設(shè)置為時(shí)限的上限。如圖1（b）的調(diào)度長度為9，則可以設(shè)置時(shí)限為10，如圖1（c）所示。

以圖1（c）的調(diào)度作為例子，這里兩個(gè)處理器核都工作在高電壓狀態(tài)，有最佳的時(shí)間性能。將圖1（c）的靜態(tài)調(diào)度的所有的空槽都用NOP指令填充，并給每個(gè)節(jié)點(diǎn)指派最大電壓即可得到初始調(diào)度。

首先找到可旋轉(zhuǎn)的節(jié)點(diǎn)并對可旋轉(zhuǎn)節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)調(diào)度。可旋轉(zhuǎn)節(jié)點(diǎn)的判定過程如下：如果節(jié)點(diǎn)是第一個(gè)被調(diào)度的節(jié)點(diǎn)并且在它的入邊上至少有一個(gè)延遲，則這個(gè)節(jié)點(diǎn)是可旋轉(zhuǎn)的；對于非第一個(gè)調(diào)度的節(jié)點(diǎn)u，如果滿足下面兩個(gè)條件，則u是可旋轉(zhuǎn)的：a)每個(gè)入邊上至少有一個(gè)延遲；b)同一個(gè)處理器上位于u前面的調(diào)度節(jié)點(diǎn)都是可旋轉(zhuǎn)的。

得到旋轉(zhuǎn)集以后，將節(jié)點(diǎn)按執(zhí)行時(shí)間排序，這樣執(zhí)行時(shí)間長的節(jié)點(diǎn)將會被更早地調(diào)度。首先，將要調(diào)度的節(jié)點(diǎn)插入一個(gè)空的時(shí)隙中，然后調(diào)整節(jié)點(diǎn)的電壓級別以降低功耗。具體的做法是嘗試所有電壓級別，并且把空時(shí)隙用NOP指令填充，挑選有最低功耗的電壓。如果時(shí)限滿足，則記錄這種調(diào)度的功耗作為最小功耗。

表1 DFG中每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間和功耗

m)輸出STMIN。

根據(jù)上面的算法對DFG進(jìn)行旋轉(zhuǎn)調(diào)度，圖3~5是每一次調(diào)度后的等價(jià)循環(huán)體、DFG和調(diào)度結(jié)果。其中：第一次調(diào)度結(jié)果E=PN×18+2×Etransit=4×18+2×1=74 nJ;第二次調(diào)度結(jié)果E=PN×7+4×Etransit+PL×9=4×7+4×1+0.5×9=36.5 nJ;第三次調(diào)度結(jié)果E=PL×20=0.5×20=10 nJ。經(jīng)過三次旋轉(zhuǎn)調(diào)度后得到了如圖5（c）的結(jié)果，最終得到了循環(huán)DFG的最小的功耗。

可以看出，經(jīng)過旋轉(zhuǎn)調(diào)度后，循環(huán)體的長度不但沒有增加，反而從初始的5N+4條代碼減少到5N-1條。同時(shí)，功耗由初始的80 nJ減少到10 nJ。

4 結(jié)束語

本文提出了一種DVS 實(shí)時(shí)調(diào)度算法。

通過在循環(huán)中運(yùn)用循環(huán)調(diào)度技術(shù)并結(jié)合DVS來減小功耗，并且考慮了電壓轉(zhuǎn)換的開銷。算法基于旋轉(zhuǎn)調(diào)度來不斷重組一個(gè)循環(huán)，并且運(yùn)用DVS在一個(gè)固定的時(shí)限下盡可能地減少功耗。本算法可以集成在實(shí)時(shí)操作系統(tǒng)的編譯器中以產(chǎn)生具有低功耗效果的代碼，但是該算法并沒有考慮通信延遲和泄漏電流。

參考文獻(xiàn)：

[1]王彪，王小鴿.功耗管理中的動(dòng)態(tài)電壓調(diào)整綜述[J].計(jì)算機(jī)應(yīng)用研究，2007，24(8)：812.

[2]SAPUTRA H， KANDEMIR M， VIJAYKRISHNAN N， et al.. Energyconscious compilation based on voltage scaling[C]//Proc of the Joint Conference on Languages，Compilers and Tools for Embedded System. New York:ACM Press， 2002:211.

［3］CHAO L F， LAPAUGH A S， SHA E H M. Rotation scheduling:a loop pipelining algorithm[J]. IEEE Trans on Computeraided Design of Integrated Circuits and Systems， 1997，16(3):229239.

[4]傅一平，任俊，李志能.一種受限資源的軟件流水滾動(dòng)調(diào)度算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)：工學(xué)版，2005，39(4)：506510.

[5]KANG S M， LEBLEBICI Y. CMOS digital integrated circuits analysis and design[M]. 北京: 清華大學(xué)出版社，2002.

[6]BURD T D. Energyefficient processor system design[D]. Berkeley:Universityof California， 2000.