基于多核處理器的低能耗任務(wù)調(diào)度優(yōu)化算法*

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

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

基于多核處理器的低能耗任務(wù)調(diào)度優(yōu)化算法*

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

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

針對(duì)多核處理器的高性能所帶來(lái)的高能耗問(wèn)題，對(duì)TL-DVFS算法中任務(wù)遷移開(kāi)銷(xiāo)問(wèn)題進(jìn)行了分析，提出了一種基于TL面的節(jié)能調(diào)度算法ITL-DVFS.該算法在不增加算法時(shí)間復(fù)雜度的前提下，通過(guò)對(duì)堆進(jìn)行操作，有效地減少每個(gè)TL面初始時(shí)刻任務(wù)的遷移開(kāi)銷(xiāo).結(jié)合全局動(dòng)態(tài)電壓頻率調(diào)節(jié)技術(shù)，在TL面的初始時(shí)刻和偶發(fā)任務(wù)釋放時(shí)刻動(dòng)態(tài)調(diào)節(jié)多核處理器的電壓頻率.結(jié)果表明，ITL-DVFS可以有效地減少任務(wù)的遷移開(kāi)銷(xiāo)，在負(fù)載達(dá)到某一值后，可有效降低處理器功耗.

多核處理器； 節(jié)能調(diào)度； 偶發(fā)任務(wù)； 任務(wù)遷移； 處理器功耗； 負(fù)載； 任務(wù)利用率； 可靠性

隨著智能嵌入式系統(tǒng)的廣泛應(yīng)用，單核處理器的處理能力已經(jīng)不能滿(mǎn)足要求，隨之出現(xiàn)了多核處理器和多處理器，多處理器的運(yùn)行功耗較大，處理器之間的協(xié)調(diào)控制依舊是個(gè)難題，而多核處理器具有優(yōu)異的處理能力，可以很好地滿(mǎn)足嵌入式系統(tǒng)的要求，多核處理器在嵌入式領(lǐng)域越來(lái)越受到青睞.隨著“綠色計(jì)算”的提出，多核處理器的節(jié)能調(diào)度算法越來(lái)越受到學(xué)者的重視[1].

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

為了更好地實(shí)現(xiàn)節(jié)能實(shí)時(shí)調(diào)度技術(shù)的擴(kuò)展，對(duì)任務(wù)屬性部分未知的偶發(fā)任務(wù)模型進(jìn)行了研究.文獻(xiàn)[6]提出了一種電壓和頻率調(diào)節(jié)的靜態(tài)節(jié)能算法Uniform RT-SVFS，當(dāng)偶發(fā)任務(wù)集動(dòng)態(tài)釋放時(shí)，不能根據(jù)任務(wù)負(fù)載實(shí)現(xiàn)更好地節(jié)能；文獻(xiàn)[7]提出了一種基于非最優(yōu)全局EDF節(jié)能調(diào)度算法DVS-EDF，該算法只能實(shí)現(xiàn)部分任務(wù)的遷移，負(fù)載的均衡難以實(shí)現(xiàn).文獻(xiàn)[6-7]提出的針對(duì)偶發(fā)任務(wù)的節(jié)能調(diào)度算法不能適應(yīng)偶發(fā)任務(wù)釋放時(shí)間不確定的特性，嚴(yán)重影響了調(diào)度的效果.

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

文獻(xiàn)[10]對(duì)LLREF算法進(jìn)行了改進(jìn)，使調(diào)度任務(wù)在任務(wù)處于滿(mǎn)足截止期時(shí)搶占調(diào)度的情況下發(fā)生，在一定程度上減少了調(diào)度開(kāi)銷(xiāo)，提出了可調(diào)度偶發(fā)任務(wù)的LRE-TL調(diào)度算法；文獻(xiàn)[11]提出了一種基于LRE-TL的節(jié)能調(diào)度算法TL-DVFS，該算法可以在每個(gè)TL面的開(kāi)始時(shí)刻和偶發(fā)任務(wù)的釋放時(shí)刻完成動(dòng)態(tài)電壓頻率的調(diào)節(jié)，從而完成節(jié)能調(diào)度.但是，TL-DVFS算法在任務(wù)處于滿(mǎn)足截止期時(shí)，仍要對(duì)任務(wù)進(jìn)行重新調(diào)度，當(dāng)任務(wù)負(fù)載增大到一定程度后，會(huì)帶來(lái)較大的任務(wù)調(diào)度開(kāi)銷(xiāo)，影響到調(diào)度的性能和節(jié)能效果.

綜上，本文提出了一種基于偶發(fā)任務(wù)的最優(yōu)節(jié)能實(shí)時(shí)調(diào)度算法ITL-DVFS(improved time local remaining execution plane based dynamic voltage frequency scaling)，該算法通過(guò)改進(jìn)TL-DVFS的TL面初始化程序來(lái)有效地減少任務(wù)的調(diào)度開(kāi)銷(xiāo)，在每一個(gè)TL面的初始時(shí)刻和偶發(fā)任務(wù)的釋放時(shí)刻進(jìn)行動(dòng)態(tài)電壓頻率調(diào)節(jié)，以此達(dá)到節(jié)能目的.實(shí)驗(yàn)結(jié)果證明，ITL-DVFS節(jié)能調(diào)度算法可以滿(mǎn)足節(jié)能調(diào)度需求.

1 系統(tǒng)模型

1.1 任務(wù)模型

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

1.2 多核處理器及能耗模型

多核處理器由m個(gè)電壓和頻率為全局統(tǒng)一調(diào)度的同構(gòu)處理器組成，m為常數(shù).多核處理器功耗可以歸一化為處理器頻率為α(0≤α≤1)的函數(shù)，多核處理器的總功耗Ptotal由與頻率相關(guān)的功耗Pdynamic和泄露功耗Pleakage組成，其表達(dá)式為

Ptotal=Pdynamic+Pleakage

(1)

與頻率相關(guān)的功耗主要由動(dòng)態(tài)功耗構(gòu)成，動(dòng)態(tài)功耗由電路的充放電而形成，Pdynamic可以表示為供電電壓Vdd、時(shí)鐘頻率f和充放電電容Ceff的函數(shù)，即

(2)

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

(3)

Vth=Vth1-K1Vdd-K2Vbs

(4)

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

(5)

Isubn=K3eK4VddeK5Vbs

(6)

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

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

α=f/fmax

(7)

因此，功耗函數(shù)可近似表示為

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

(8)

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

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

(9)

式中，Δt為處理器在某一固定頻率α下的運(yùn)行時(shí)間.將整個(gè)偶發(fā)任務(wù)集在相應(yīng)頻率下的能耗求和，就得到了整個(gè)處理器的能耗.

1.3 TL面模型

定義1在任意時(shí)刻t，[t，tf]是一個(gè)TL面，在t時(shí)刻，任務(wù)Ji均有一個(gè)局部剩余執(zhí)行時(shí)間li，t，任務(wù)的局部利用率ui，t可以定義為Ji的局部剩余執(zhí)行時(shí)間在當(dāng)前TL面的剩余時(shí)間內(nèi)所占的比例，即

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

(10)

初始時(shí)刻的任務(wù)利用率為

ui，0=Ci/Pi

(11)

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

(12)

任務(wù)Ji的有效局部利用率為

(13)

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

(14)

2 ITL-DVFS算法

2.1 ITL-DVFS算法思想

本文基于TL面上偶發(fā)任務(wù)集提出了ITL-DVFS節(jié)能調(diào)度算法，旨在保證偶發(fā)任務(wù)集在最優(yōu)可調(diào)度情況下實(shí)現(xiàn)節(jié)能，并減少調(diào)度開(kāi)銷(xiāo).在TL面進(jìn)行節(jié)能調(diào)度算法會(huì)發(fā)生三類(lèi)事件：在任務(wù)的局部剩余執(zhí)行時(shí)間為0時(shí)發(fā)生，叫做事件B；偶發(fā)任務(wù)在TL面內(nèi)釋放時(shí)刻發(fā)生，叫做事件A；在任務(wù)的有效局部利用率為1時(shí)發(fā)生，叫做事件C.涉及到兩個(gè)數(shù)據(jù)結(jié)構(gòu)最小堆HB和最小堆HC，最小堆HB包含所有在t時(shí)刻分配給處理器核的任務(wù)，其鍵值為堆中Ji將被執(zhí)行的時(shí)刻.最小堆HC包含了活躍任務(wù)中沒(méi)有被分配處理器核的任務(wù)，其鍵值為堆中Ji將被執(zhí)行的時(shí)刻.

文獻(xiàn)[10]提出了一種基于LRE-TL的節(jié)能調(diào)度算法，在設(shè)置完頻率后對(duì)任務(wù)進(jìn)行初始化處理時(shí)，以及在為處理器分配任務(wù)時(shí)，隨機(jī)選擇活躍任務(wù)分配給空閑的處理器，在處理器處理過(guò)程中，當(dāng)調(diào)度事件C發(fā)生時(shí)，會(huì)引起任務(wù)實(shí)例在核之間的遷移，從而帶來(lái)較大的調(diào)度開(kāi)銷(xiāo).表1中包含了例1任務(wù)集中8個(gè)任務(wù)的最大處理時(shí)間時(shí)鐘數(shù)、最小釋放時(shí)間時(shí)鐘數(shù)和當(dāng)前剩余執(zhí)行時(shí)間的時(shí)鐘數(shù).

表1 例1任務(wù)集
Tab.1 Task set in example 1

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

如果在一個(gè)四核處理器上調(diào)度這8個(gè)任務(wù)，HB和HC將被初始化，結(jié)果如表2所示.

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

HBJ4J2J3J1HCJ6J8J7J52 83 34 54 71 51 78 89 0

由表2可知，任務(wù)6將在1.5時(shí)刻觸發(fā)事件C，任務(wù)8將在1.7時(shí)刻觸發(fā)事件C，從而導(dǎo)致任務(wù)在處理器核間的遷移.

在初始化TL且分配處理器任務(wù)時(shí)，按照最大剩余處理時(shí)間分配任務(wù)，結(jié)果如表3所示.

表3 例2任務(wù)集
Tab.3 Task set in example 2

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

如果在一個(gè)四核處理器上調(diào)度這8個(gè)任務(wù)，HB和HC將被初始化，結(jié)果如表4所示.

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

由表4可知，在HB中的任務(wù)完成之前，沒(méi)有事件C被觸發(fā)，這樣就減少了處理器核間任務(wù)的遷移，減少了調(diào)度開(kāi)銷(xiāo).

考慮到如果在TL面初始化時(shí)，對(duì)任務(wù)集按照當(dāng)前剩余可處理時(shí)間排序，會(huì)增加TL面初始化程序的時(shí)間復(fù)雜度，本文提出了利用HC來(lái)克服這一問(wèn)題.在TL面初始化時(shí)，對(duì)于活躍的任務(wù)，計(jì)算其當(dāng)前時(shí)刻的松弛時(shí)間，放入HC中，當(dāng)前松弛時(shí)間越小，此任務(wù)的剩余可執(zhí)行任務(wù)時(shí)間越長(zhǎng)，然后在HC中取m個(gè)任務(wù)，分配給m個(gè)處理器，并將這m個(gè)任務(wù)放入HB中，從而在沒(méi)有增加TL面初始化程序時(shí)間復(fù)雜度的前提下，實(shí)現(xiàn)了對(duì)任務(wù)按照最大當(dāng)前可執(zhí)行時(shí)間的排序工作，進(jìn)而有效地減少了ITL-DVFS節(jié)能調(diào)度算法的任務(wù)遷移開(kāi)銷(xiāo).

2.2 ITL-DVFS算法描述

α=max{umax，U/m′}

(15)

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

3 實(shí)驗(yàn)結(jié)果及分析

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

Ptotal(α)=1.52α3+0.08

(16)

實(shí)驗(yàn)1ITL-DVFS算法的任務(wù)遷移實(shí)驗(yàn)

為了驗(yàn)證ITL-DVFS算法能夠有效地減少TL面調(diào)度過(guò)程中任務(wù)的遷移開(kāi)銷(xiāo)，本文通過(guò)獲得處理相同任務(wù)數(shù)任務(wù)的處理時(shí)間，來(lái)比較TL-DVFS算法和ITL-DVFS算法其任務(wù)的遷移開(kāi)銷(xiāo).任務(wù)集的參數(shù)設(shè)置如下：

1) 由TGFF測(cè)試程序集產(chǎn)生100個(gè)偶發(fā)任務(wù)，任務(wù)的局部利用率在(0，1)之間，符合正態(tài)分布；

2) 任務(wù)數(shù)由20個(gè)增加到100個(gè)，步長(zhǎng)為10；

3) 每種算法在每個(gè)任務(wù)數(shù)的調(diào)度節(jié)點(diǎn)處重復(fù)實(shí)驗(yàn)5次，取其任務(wù)調(diào)度周期的平均值.

圖1為2種算法的任務(wù)處理時(shí)間比較.由圖1可知，隨著任務(wù)數(shù)的增加，ITL-DVFS調(diào)度算法在處理相同任務(wù)時(shí)的處理時(shí)間明顯小于TL-DVFS算法，在對(duì)TL-DVFS算法的改進(jìn)中，有效地減少了任務(wù)遷移的開(kāi)銷(xiāo).

圖1 任務(wù)處理時(shí)間Fig.1 Task processing time

實(shí)驗(yàn)2ITL-DVFS算法的節(jié)能調(diào)度實(shí)驗(yàn)

為了驗(yàn)證ITL-DVFS算法在節(jié)能調(diào)度上的優(yōu)越性，將ITL-DVFS算法與LRE-TL、Uniform RT-SVFS、DVS-EDF、TL-DVFS算法進(jìn)行了比較.任務(wù)集的參數(shù)設(shè)置如下：

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

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

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

4) 實(shí)驗(yàn)中對(duì)于每個(gè)偶發(fā)任務(wù)集模擬時(shí)間為60 min，由式(9)可以計(jì)算出各個(gè)節(jié)能實(shí)時(shí)調(diào)度算法的能耗，以此來(lái)衡量各種算法在該時(shí)間內(nèi)的功耗(歸一化能耗，即各個(gè)節(jié)能實(shí)時(shí)調(diào)度算法的能耗相對(duì)于LRE-TL算法的比值).

本實(shí)驗(yàn)以LRE-TL算法的能耗作為標(biāo)準(zhǔn)進(jìn)行歸一化，圖2給出了在不同參數(shù)設(shè)置下偶發(fā)任務(wù)集的歸一化能耗.

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

由初始時(shí)刻任務(wù)利用率ui，0=Ci/Pi可知，任務(wù)的利用率越小，其任務(wù)再次被調(diào)度的執(zhí)行時(shí)間就越長(zhǎng)，任務(wù)數(shù)n、處理器核數(shù)m越小，任務(wù)在調(diào)度過(guò)程中的遷移就相對(duì)越小.

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

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

多核處理器任務(wù)節(jié)能調(diào)度算法的可調(diào)度性是衡量算法可靠性的一個(gè)重要指標(biāo)，調(diào)度算法的可調(diào)度性是可調(diào)度任務(wù)占總?cè)蝿?wù)集的比率，為了更好地衡量ITL-DVFS算法的性能，圖3給出了不同參數(shù)下算法的可調(diào)度性.

圖3 算法的可調(diào)度性Fig.3 Schedulability of algorithms

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

由圖2、3可知，ITL-DVFS算法不僅在能耗上可以實(shí)現(xiàn)較大的能耗節(jié)約，而且也是基于偶發(fā)任務(wù)的最優(yōu)可調(diào)度性算法.

4 結(jié) 論

本文針對(duì)ITL-DVFS算法在TL面初始化時(shí)，會(huì)在事件C觸發(fā)時(shí)產(chǎn)生任務(wù)遷移，從而給任務(wù)調(diào)度帶來(lái)較大的開(kāi)銷(xiāo)問(wèn)題，提出了一種利用堆來(lái)對(duì)任務(wù)按照最大可執(zhí)行時(shí)間排序，在不增加調(diào)度算法時(shí)間復(fù)雜度的前提下，有效減少調(diào)度開(kāi)銷(xiāo)的節(jié)能調(diào)度算法ITL-DVFS.該算法在每個(gè)TL面的初始時(shí)刻利用堆來(lái)完成排序，利用TL面節(jié)能實(shí)時(shí)調(diào)度的思想，在每個(gè)TL面初始時(shí)刻和偶發(fā)任務(wù)釋放時(shí)刻完成動(dòng)態(tài)電壓和頻率的調(diào)節(jié)，保證了算法的可調(diào)度性.實(shí)驗(yàn)結(jié)果表明，ITL-DVFS算法不僅明顯減少了任務(wù)的開(kāi)銷(xiāo)，而且在負(fù)載增加到某值后，節(jié)能效果略?xún)?yōu)于現(xiàn)有算法，可以有效節(jié)能20%～22%.

[1]李新，賈智平，鞠雷，等.一種面向同構(gòu)集群系統(tǒng)的并行任務(wù)節(jié)能調(diào)度優(yōu)化方法 [J].計(jì)算機(jī)學(xué)報(bào)，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]袁龍，楊頻，梁剛，等.一種基于同構(gòu)多核處理器的動(dòng)態(tài)節(jié)能調(diào)度算法 [J].計(jì)算機(jī)工程與應(yīng)用，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.

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

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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(31370565)； 哈爾濱市科技創(chuàng)新人才研究基金資助項(xiàng)目(2015RAYXJ005).

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

17∶42在中國(guó)知網(wǎng)優(yōu)先數(shù)字出版.

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