基于多核處理器的低能耗任務調度優化算法*

劉亞秋， 陳雨佳， 景維鵬， 王 鹍

(1. 東北林業大學 信息與計算機工程學院， 哈爾濱 150040； 2. 佳木斯大學 信息電子技術學院， 黑龍江 佳木斯 154007)

基于多核處理器的低能耗任務調度優化算法*

劉亞秋1， 陳雨佳1， 景維鵬1， 王 鹍2

(1. 東北林業大學 信息與計算機工程學院， 哈爾濱 150040； 2. 佳木斯大學 信息電子技術學院， 黑龍江 佳木斯 154007)

針對多核處理器的高性能所帶來的高能耗問題，對TL-DVFS算法中任務遷移開銷問題進行了分析，提出了一種基于TL面的節能調度算法ITL-DVFS.該算法在不增加算法時間復雜度的前提下，通過對堆進行操作，有效地減少每個TL面初始時刻任務的遷移開銷.結合全局動態電壓頻率調節技術，在TL面的初始時刻和偶發任務釋放時刻動態調節多核處理器的電壓頻率.結果表明，ITL-DVFS可以有效地減少任務的遷移開銷，在負載達到某一值后，可有效降低處理器功耗.

多核處理器； 節能調度； 偶發任務； 任務遷移； 處理器功耗； 負載； 任務利用率； 可靠性

隨著智能嵌入式系統的廣泛應用，單核處理器的處理能力已經不能滿足要求，隨之出現了多核處理器和多處理器，多處理器的運行功耗較大，處理器之間的協調控制依舊是個難題，而多核處理器具有優異的處理能力，可以很好地滿足嵌入式系統的要求，多核處理器在嵌入式領域越來越受到青睞.隨著“綠色計算”的提出，多核處理器的節能調度算法越來越受到學者的重視[1].

為了使節能更加高效，當前多核處理器廣泛采用了動態電壓頻率調節(dynamic voltage frequency scaling，DVFS)和動態功耗管理(dynamic power management，DPM)技術對多核處理器的節能調度算法進行研究.文獻[2]針對采用全局DVFS的多核處理器提出了基于幀任務模型的靜態節能實時調度算法；文獻[3]基于啟發式劃分法，針對周期任務在多核系統上提出了動態節能實時調度算法；文獻[4]針對周期任務模型提出了一種基于全局最早截止期優先(earliest deadline first，EDF)的多核系統動態節能實時調度算法；文獻[5]針對軟實時任務模型提出了一種動態節能調度算法.文獻[2-5]提出的節能調度算法考慮的是基于幀任務模型或者是周期性任務模型，任務模型的苛刻條件對節能實時調度技術的應用范圍有較大限制，因此，這些節能調度算法對現實中實際調度任務的可移植性較差.

為了更好地實現節能實時調度技術的擴展，對任務屬性部分未知的偶發任務模型進行了研究.文獻[6]提出了一種電壓和頻率調節的靜態節能算法Uniform RT-SVFS，當偶發任務集動態釋放時，不能根據任務負載實現更好地節能；文獻[7]提出了一種基于非最優全局EDF節能調度算法DVS-EDF，該算法只能實現部分任務的遷移，負載的均衡難以實現.文獻[6-7]提出的針對偶發任務的節能調度算法不能適應偶發任務釋放時間不確定的特性，嚴重影響了調度的效果.

文獻[8]提出了一種利用TL面調度周期任務的LLREF算法，TL面是一個二維平面，水平軸表示時間，垂直軸表示任務的局部剩余執行時間，所有任務實例的絕對截止期di，j在時間軸上表示為從任務實例被釋放至其局部剩余執行時間為零的區間，任意兩個相鄰的絕對截止期之間就是一個TL面[9]，通過TL面可以靈活地調度釋放偶發任務.當調度事件被觸發時，LLREF算法按照最大當前剩余時間對當前的各個核重新分配任務，從而完成調度，這種調度算法只適用于周期任務，并且頻繁地對任務進行重分配造成了巨大的調度開銷.

文獻[10]對LLREF算法進行了改進，使調度任務在任務處于滿足截止期時搶占調度的情況下發生，在一定程度上減少了調度開銷，提出了可調度偶發任務的LRE-TL調度算法；文獻[11]提出了一種基于LRE-TL的節能調度算法TL-DVFS，該算法可以在每個TL面的開始時刻和偶發任務的釋放時刻完成動態電壓頻率的調節，從而完成節能調度.但是，TL-DVFS算法在任務處于滿足截止期時，仍要對任務進行重新調度，當任務負載增大到一定程度后，會帶來較大的任務調度開銷，影響到調度的性能和節能效果.

綜上，本文提出了一種基于偶發任務的最優節能實時調度算法ITL-DVFS(improved time local remaining execution plane based dynamic voltage frequency scaling)，該算法通過改進TL-DVFS的TL面初始化程序來有效地減少任務的調度開銷，在每一個TL面的初始時刻和偶發任務的釋放時刻進行動態電壓頻率調節，以此達到節能目的.實驗結果證明，ITL-DVFS節能調度算法可以滿足節能調度需求.

1 系統模型

1.1 任務模型

考慮由n個偶發任務構成的偶發任務集J={J1，J2，…，Jn}，偶發任務Ji可由(Si，Ci，Pi)三元組描述，其中，Si表示第i個偶發任務的釋放時刻；Ci表示第i個偶發任務的最大執行時間時鐘數；Pi表示第i個偶發任務再次被調度的最小釋放時間時鐘數.

1.2 多核處理器及能耗模型

多核處理器由m個電壓和頻率為全局統一調度的同構處理器組成，m為常數.多核處理器功耗可以歸一化為處理器頻率為α(0≤α≤1)的函數，多核處理器的總功耗Ptotal由與頻率相關的功耗Pdynamic和泄露功耗Pleakage組成，其表達式為

Ptotal=Pdynamic+Pleakage

(1)

與頻率相關的功耗主要由動態功耗構成，動態功耗由電路的充放電而形成，Pdynamic可以表示為供電電壓Vdd、時鐘頻率f和充放電電容Ceff的函數，即

(2)

處理器的時鐘頻率f可由供電電壓Vdd、閾值電壓Vth和處理器制造工藝參數常量(ε、Ld、Vth1、Vbs、K1、K2、K6)求得，即

(3)

Vth=Vth1-K1Vdd-K2Vbs

(4)

泄露功耗Pleakage由泄露電流引起，可以表示為低于閾值的泄漏電流Isubn、反轉偏移電流Ij和處理器制造工藝參數常量(Lg、K3、K4、K5)的函數，即

(5)

Isubn=K3eK4VddeK5Vbs

(6)

由式(2)、(4)可知，Pdynamic為處理器供電電壓Vdd嚴格凸函數，由式(3)可以獲知頻率f和Vdd的關系，由式(5)、(6)可知，Pleakage為常量.

歸一化頻率α可由即時頻率f和處理器最大頻率fmax求得，即

α=f/fmax

(7)

因此，功耗函數可近似表示為

Ptotal(αfmax)=λ(αfmax)3+β(λ>0，β>0)

(8)

式中，λ和β為常量.因此，處理器的能耗函數可以表示為

Etotal(αfmax)=∑ΔtPtotal(αfmax)

(9)

式中，Δt為處理器在某一固定頻率α下的運行時間.將整個偶發任務集在相應頻率下的能耗求和，就得到了整個處理器的能耗.

1.3 TL面模型

定義1在任意時刻t，[t，tf]是一個TL面，在t時刻，任務Ji均有一個局部剩余執行時間li，t，任務的局部利用率ui，t可以定義為Ji的局部剩余執行時間在當前TL面的剩余時間內所占的比例，即

ui，t=li，t/(tf-t)

(10)

初始時刻的任務利用率為

ui，0=Ci/Pi

(11)

定義2如果任務Ji的局部剩余執行時間為li，t，則稱Ji在t時刻處于活躍狀態，active(t)為在t時刻處于活躍狀態的所有任務的集合.任務Ji在t時刻的有效局部剩余執行時間為

(12)

任務Ji的有效局部利用率為

(13)

活躍任務總的任務局部利用率U可以表示為

(14)

2 ITL-DVFS算法

2.1 ITL-DVFS算法思想

本文基于TL面上偶發任務集提出了ITL-DVFS節能調度算法，旨在保證偶發任務集在最優可調度情況下實現節能，并減少調度開銷.在TL面進行節能調度算法會發生三類事件：在任務的局部剩余執行時間為0時發生，叫做事件B；偶發任務在TL面內釋放時刻發生，叫做事件A；在任務的有效局部利用率為1時發生，叫做事件C.涉及到兩個數據結構最小堆HB和最小堆HC，最小堆HB包含所有在t時刻分配給處理器核的任務，其鍵值為堆中Ji將被執行的時刻.最小堆HC包含了活躍任務中沒有被分配處理器核的任務，其鍵值為堆中Ji將被執行的時刻.

文獻[10]提出了一種基于LRE-TL的節能調度算法，在設置完頻率后對任務進行初始化處理時，以及在為處理器分配任務時，隨機選擇活躍任務分配給空閑的處理器，在處理器處理過程中，當調度事件C發生時，會引起任務實例在核之間的遷移，從而帶來較大的調度開銷.表1中包含了例1任務集中8個任務的最大處理時間時鐘數、最小釋放時間時鐘數和當前剩余執行時間的時鐘數.

表1 例1任務集
Tab.1 Task set in example 1

JCiPili，0J18174 7J210303 3J35114 5J48292 8J51101 0J611138 5J73261 2J815188 3

如果在一個四核處理器上調度這8個任務，HB和HC將被初始化，結果如表2所示.

表2 TL面HB和HC的初始化
Tab.2 Initialization ofHBandHCon TL plane

HBJ4J2J3J1HCJ6J8J7J52 83 34 54 71 51 78 89 0

由表2可知，任務6將在1.5時刻觸發事件C，任務8將在1.7時刻觸發事件C，從而導致任務在處理器核間的遷移.

在初始化TL且分配處理器任務時，按照最大剩余處理時間分配任務，結果如表3所示.

表3 例2任務集
Tab.3 Task set in example 2

JCiPili，0J611138 5J815188 3J18174 7J35114 5J210303 3J48292 8J73261 2J51101 0

如果在一個四核處理器上調度這8個任務，HB和HC將被初始化，結果如表4所示.

表4 排序后TL面HB和HC的初始化Tab.4 Initialization of HB and HCon TL plane after sorting

由表4可知，在HB中的任務完成之前，沒有事件C被觸發，這樣就減少了處理器核間任務的遷移，減少了調度開銷.

考慮到如果在TL面初始化時，對任務集按照當前剩余可處理時間排序，會增加TL面初始化程序的時間復雜度，本文提出了利用HC來克服這一問題.在TL面初始化時，對于活躍的任務，計算其當前時刻的松弛時間，放入HC中，當前松弛時間越小，此任務的剩余可執行任務時間越長，然后在HC中取m個任務，分配給m個處理器，并將這m個任務放入HB中，從而在沒有增加TL面初始化程序時間復雜度的前提下，實現了對任務按照最大當前可執行時間的排序工作，進而有效地減少了ITL-DVFS節能調度算法的任務遷移開銷.

2.2 ITL-DVFS算法描述

α=max{umax，U/m′}

(15)

利用堆HC來完成任務的分配，之后各個處理器核開始執行任務，監聽事件B、事件C和事件A是否被觸發.若在時刻t，偶發任務Js釋放，觸發事件A，根據此偶發任務的任務利用率us，t來確定處理器的頻率α，然后按照α來更新HB和HC的鍵值，并根據式(12)計算出Js在時刻t的局部剩余執行時間，判斷HB中可執行任務的個數是否小于處理器核的個數，若小于，將偶發任務Js直接分配給處理器，并將其放到HB中，否則，判斷Js的任務利用率us，t是否小于當前任務的頻率α，若us，t小于α，將Js放到HC中，并更新其鍵值.為了偶發任務Js能夠在截止期完成，必須立即執行，從HB中取出鍵值最小的任務放入HC中，將Js分配給處理器，并放入HB中，更新兩個任務的鍵值.若監聽到事件B觸發了，則從HC中取出堆頂任務放到HB中，更新其鍵值，并以當前頻率執行任務.若監聽到事件C，則立即在HC中取出觸發事件C的任務，并從HB中取出堆頂任務放到HC中，將從HC中取出的任務放到HB立即執行，更新兩個任務的鍵值，直到TL面結束.按上述方法分別進行各個TL面的調度，直到所有任務處理完畢，調度結束.

3 實驗結果及分析

測試環境包括：CPU為Intel(R)Core(TM)i5-3230M，主頻為2.6 GHz，內存為4 GB，操作系統為Ubuntu14.04，內核版本linux 4.2.0.本文采用Intel XScale處理器模型來評價算法的遷移開銷和各種節能實時調度算法的能耗.由于處理器核采用Intel XScale處理器模型，可以確定式(8)中λ的值為1.52、β的值為0.08和fmax的值為1 GHz[9]，Intel XScale處理器的功耗函數為

Ptotal(α)=1.52α3+0.08

(16)

實驗1ITL-DVFS算法的任務遷移實驗

為了驗證ITL-DVFS算法能夠有效地減少TL面調度過程中任務的遷移開銷，本文通過獲得處理相同任務數任務的處理時間，來比較TL-DVFS算法和ITL-DVFS算法其任務的遷移開銷.任務集的參數設置如下：

1) 由TGFF測試程序集產生100個偶發任務，任務的局部利用率在(0，1)之間，符合正態分布；

2) 任務數由20個增加到100個，步長為10；

3) 每種算法在每個任務數的調度節點處重復實驗5次，取其任務調度周期的平均值.

圖1為2種算法的任務處理時間比較.由圖1可知，隨著任務數的增加，ITL-DVFS調度算法在處理相同任務時的處理時間明顯小于TL-DVFS算法，在對TL-DVFS算法的改進中，有效地減少了任務遷移的開銷.

圖1 任務處理時間Fig.1 Task processing time

實驗2ITL-DVFS算法的節能調度實驗

為了驗證ITL-DVFS算法在節能調度上的優越性，將ITL-DVFS算法與LRE-TL、Uniform RT-SVFS、DVS-EDF、TL-DVFS算法進行了比較.任務集的參數設置如下：

1) 任務集采用與文獻[12]相同的任務集，主要由FFT1、FFT2(快速傅里葉變換)、Laplace(拉普拉斯變換)、Karp10(卡勒音樂合成法)和TGFF測試程序集隨機得到，假設每個任務的截止周期等于其最小釋放周期，每個任務的實際執行時間等于其最壞執行時間.

2) 測試任務數10 000組，在上述任務集中隨機選擇，處理器核數m分別設為4、8、16；系統利用率usys的設置采用文獻[6]的方法，以步長為10%從10%遞增到100%，任務個數n分別設為10、20、40個.每個任務利用Uunifast算法[12]產生符合正態分布的利用率ui，其范圍為0.01≤ui≤1.0，整個任務集的總負載為usysm.

3) 由公式usys=U/m可以得到任務的總利用率U值，再根據式(14)來選取，首先假定任務集為空，然后根據U和ui來選定任務.

4) 實驗中對于每個偶發任務集模擬時間為60 min，由式(9)可以計算出各個節能實時調度算法的能耗，以此來衡量各種算法在該時間內的功耗(歸一化能耗，即各個節能實時調度算法的能耗相對于LRE-TL算法的比值).

本實驗以LRE-TL算法的能耗作為標準進行歸一化，圖2給出了在不同參數設置下偶發任務集的歸一化能耗.

圖2 不同負載下的能耗Fig.2 Energy consumption under different loads

由初始時刻任務利用率ui，0=Ci/Pi可知，任務的利用率越小，其任務再次被調度的執行時間就越長，任務數n、處理器核數m越小，任務在調度過程中的遷移就相對越小.

由圖2a可知，當任務總負載小于0.8時，Uniform RT-SVFS、DVS-EDF、TL-DVFS、ITL-DVFS能耗幾乎相同，但負載繼續增大時，Uniform RT-SVFS和DVS-EDF能耗節余越來越少，而TL-DVFS、ITL-DVFS還可以實現大約20%的能耗節約.在圖2b、c中可以得到和圖2a相似的結論，由于Uniform RT-SVFS算法是一種靜態的節能調度算法，事先確定處理器的電壓和頻率，在運行時不再改變處理器的電壓和頻率，不能適應于偶發任務集所帶來的動態負載變化，因此，隨著偶發任務數的增多，處理器的動態負載變大，多核處理器處于滿負荷運行狀態，致使其能耗和LRE-TL算法的能耗相同.

DVS-EDF算法是基于非最優EDF調度算法而實現的，僅可以實現部分任務的遷移，因此在低負載的情況下，處理器處于正常的運行狀態，當負載增加時，由圖2可知，當圖2a中負載大于3.6，圖2b中負載大于5.6，圖2c中負載大于6.4時，此算法的歸一化能耗不存在，這是由于此算法是基于非最優EDF實現全局的任務調度，僅考慮了可調度的任務，所以在高負載時，可調度性為0，其歸一化能耗是不存在的.ITL-DVFS、TL-DVFS算法是基于最優偶發任務調度算法LRE-TL提出的，能夠完成動態任務集在處理器核之間的動態遷移，實現核間任務的均勻分布，能夠較好地實現任務的節能調度，二者算法在圖2a、b、c中可以看出，ITL-DVFS的節能效果優于TL-DVFS，ITL-DVFS算法在TL面初始化的改進，有效地減少了任務遷移，在不同的負載下能夠節約20%～22%的能耗.

多核處理器任務節能調度算法的可調度性是衡量算法可靠性的一個重要指標，調度算法的可調度性是可調度任務占總任務集的比率，為了更好地衡量ITL-DVFS算法的性能，圖3給出了不同參數下算法的可調度性.

圖3 算法的可調度性Fig.3 Schedulability of algorithms

由圖3可知，Uniform RT-SVFS、TL-DVFS、ITL-DVFS均為最優可調度的算法，三者算法的實現均是基于最優偶發任務集實時調度算法實現的，其算法的可調度性為100%；而DVS-EDF是基于非最優EDF調度算法實現的，僅可以實現部分任務的遷移，隨著任務總負載的增加，偶發任務數的增多，處理器中的任務遷移增多，致使算法的可調度性由原來的100%逐漸降低，當負載增加到一定程度時，算法失效，可調度性降為0，不再具有最優可調度性.

由圖2、3可知，ITL-DVFS算法不僅在能耗上可以實現較大的能耗節約，而且也是基于偶發任務的最優可調度性算法.

4 結 論

本文針對ITL-DVFS算法在TL面初始化時，會在事件C觸發時產生任務遷移，從而給任務調度帶來較大的開銷問題，提出了一種利用堆來對任務按照最大可執行時間排序，在不增加調度算法時間復雜度的前提下，有效減少調度開銷的節能調度算法ITL-DVFS.該算法在每個TL面的初始時刻利用堆來完成排序，利用TL面節能實時調度的思想，在每個TL面初始時刻和偶發任務釋放時刻完成動態電壓和頻率的調節，保證了算法的可調度性.實驗結果表明，ITL-DVFS算法不僅明顯減少了任務的開銷，而且在負載增加到某值后，節能效果略優于現有算法，可以有效節能20%～22%.

[1]李新，賈智平，鞠雷，等.一種面向同構集群系統的并行任務節能調度優化方法 [J].計算機學報，2012，35(3)：591-602.

(LI Xin，JIA Zhi-ping，JU Lei，et al.Energy efficient scheduling and optimization for parallel tasks on homo-geneous clusters [J].Chinese Journal of Computers，2012，35(3)：591-602.)

[2]Seol Y I，Kim Y K.Applying dynamic priority sche-duling scheme to static systems of pinwheel task model in power-aware scheduling [J].The Scientific World Journal，2014，2014：1-9.

[3]Devadas V，Aydin H.Coordinated power management of periodic real-time tasks on chip multiprocessors [C]//Proceedings of the International Green Computing Conference.Chicago，USA，2010：61-72.

[4]Pagani S，Chen J J，Li M.Energy efficiency on multi-core architectures with multiple voltage islands [J].IEEE Transactions on Parallel and Distributed Systems，2015，26(6)：1608-1621.

[5]袁龍，楊頻，梁剛，等.一種基于同構多核處理器的動態節能調度算法 [J].計算機工程與應用，2013，49(2)：76-79.

(YUAN Long，YANG Pin，LIANG Gang，et al.Dynamic energy-efficient scheduling algorithm based on homogeneous multi-core system [J].Computer Engineering and Applications，2013，49(2)：76-79.)

[6]Funaoka K，Kato S，Yamasaki N.Energy-efficient optimal real-time scheduling on multiprocessors [C]//The 11th IEEE Symposium on Object Oriented Real-time Distributed Computing.Barcelona，Spain，2008：23-30.

[7]Huang X，Li K L，Li R F.A energy efficient scheduling base on dynamic voltage and frequency scaling for multi-core embedded real-time system [C]//International Conference on Algorithms & Architectures for Parallel Processing.Taipei，China，2009：137-145.

[8]Xu C，Xiao J，Zeng L N，et al.An energy-aware dynamic algorithm based on variable interval DVFS technology [J].Advanced Materials Research，2014，950：185-195.

[9]Cho H，Ravindran B，Jensen E D，et al.T-L plane-based real-time scheduling for homogeneous multiprocessors [J].Journal of Parallel and Distributed Computing，2010，70(3)：225-236.

[10]Funk S.LRE-TL：an optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines [J].Real-Time Systems，2010，46(3)：332-359.

[11]Zhang D，Guo D，Chen F，et al.TL-plane-based multi-core energy-efficient real-time scheduling algorithm for sporadic tasks [J].ACM Transactions on Architecture and Code Optimization，2012，8(4)：146-149.

[12]Zhang D S，Chen F Y，Li H H，et al.An energy-efficient scheduling algorithm for sporadic real-time tasks in multiprocessor systems [C]//The 13th IEEE International Conference on High Performance Computing and Communications.Banff，Canada，2011：187-194.

(責任編輯：鐘 媛 英文審校：尹淑英)

Optimization algorithm for task scheduling with low energy consumption based on multi-core processor

LIU Ya-qiu1, CHEN Yu-jia1, JING Wei-peng1, WANG Kun2

(1. College of Information and Computer Engineering, Northeast Forestry University, Harbin 150040, China; 2. College of Information and Electronic Technology, Jiamusi University, Jiamusi 154007, China)

In order to solve the problem of high energy consumption caused by the high performance of multi-core processor, the task migration overhead problem in TL-DVFS algorithm was analyzed, and an energy saving scheduling algorithm ITL-DVFS based on TL plane was proposed. Without increasing the time complexity of the algorithm, the migration overhead of each TL plane at initial time can be effectively reduced through the operation on the heap. In combination with the global dynamic voltage frequency modulation technology, the voltage and frequency of multi-core processor at both initial time and the sporadic task release time on the TL plane algorithm were dynamically adjusted. The results show that ITL-DVFS can effectively reduce the task migration overhead, and can effectively decrease the power consumption of multi-core processor when the load reaches a certain value.

multi-core processor; energy saving scheduling; sporadic task; task migration; processor power consumption; load; task utilization; reliability

2016-05-23.

國家自然科學基金資助項目(31370565)； 哈爾濱市科技創新人才研究基金資助項目(2015RAYXJ005).

劉亞秋(1971-)，男，遼寧法庫人，教授，博士生導師，主要從事信息控制與智能計算等方面的研究.

17∶42在中國知網優先數字出版.

http：∥www.cnki.net/kcms/detail/21.1189.T.20161222.1742.042.html

10.7688/j.issn.1000-1646.2017.01.10

TP 332

A

1000-1646(2017)01-0048-07