基于異構(gòu)多核平臺(tái)低能耗周期任務(wù)調(diào)度算法

夏軍 袁帥 楊逸

摘 要：針對(duì)異構(gòu)多核平臺(tái)存在的高能耗問題，提出一種運(yùn)用優(yōu)化理論求解周期任務(wù)最優(yōu)能耗分配方案的算法。該算法對(duì)周期任務(wù)的最優(yōu)能耗問題進(jìn)行建模，并對(duì)模型添加限制條件。根據(jù)優(yōu)化理論將二進(jìn)制整數(shù)規(guī)劃問題松弛化后得到凸優(yōu)化問題，通過內(nèi)點(diǎn)法求解優(yōu)化問題并得到松弛化的分配矩陣，對(duì)分配矩陣進(jìn)行判決處理后得到部分任務(wù)的分配方案。在此基礎(chǔ)上，通過迭代的方式求得剩余任務(wù)的分配方案。實(shí)驗(yàn)結(jié)果表明，該分配方案產(chǎn)生的能耗與同類優(yōu)化理論算法相比能耗降低約1.4%，

與能耗相當(dāng)?shù)膬?yōu)化理論算法相比執(zhí)行時(shí)間減少86%，且僅比理論最優(yōu)能耗值高2.6%。

關(guān)鍵詞：多處理器;節(jié)能調(diào)度;周期任務(wù);利用率;優(yōu)化理論

中圖分類號(hào)：TP316.2

文獻(xiàn)標(biāo)志碼：A

Abstract： Concerning at the high energy consumption of heterogeneous multi-core platforms， an algorithm for solving the optimal energy allocation scheme of periodic tasks by using optimization theory was proposed.The optimal energy consumption problem of periodic tasks was modeled and added constraints to the model.According to the optimization theory， the binary integer programming problem was relaxed to obtain the convex optimization problem. The interior point method was used to solve the optimization problem and the relaxed distribution matrix was obtained. The allocation scheme for partial tasks was obtained after the judgement processing of the decision matrix. On this basis， the iterative method was used to find the allocation scheme for the remaining tasks. Experimental results show that the energy consumption of this distribution scheme is reduced by about 1.4% compared with the similar optimization theory algorithm， and compared with the optimization theory algorithm with the similar energy consumption， the execution time of this scheme is reduced by 86%. At the same time， the energy consumption of the scheme is only 2.6% higher than the theoretically optimal energy consumption.Key words：? multiprocessor; energy saving scheduling; periodic task; utilization rate; optimization theory

0 引言

隨著嵌入式系統(tǒng)復(fù)雜度和性能要求的提升，多處理器片上系統(tǒng)（System on Chip， SoC）得到了廣泛的應(yīng)用，同時(shí)，如何降低系統(tǒng)產(chǎn)生的高能耗成為社會(huì)關(guān)注的焦點(diǎn)。所以，在多處理器片上系統(tǒng)中能耗優(yōu)化技術(shù)起到了重要的作用。在現(xiàn)有平臺(tái)中，處理器核心大多嵌入動(dòng)態(tài)電壓頻率調(diào)節(jié)（Dynamic Voltage Frequency Scaling， DVFS）技術(shù)和動(dòng)態(tài)電源管理（Dynamic Power Management， DPM）技術(shù)。DPM負(fù)責(zé)管理系統(tǒng)產(chǎn)生的靜態(tài)功耗，當(dāng)處理器處于空閑狀態(tài)時(shí)，該技術(shù)將處理器工作模式切換到低功耗狀態(tài)。但是，DPM切換處理器狀態(tài)需要時(shí)間并產(chǎn)生一定的能耗。對(duì)于周期性任務(wù)來說，頻繁地切換處理器的工作狀態(tài)所產(chǎn)生的能耗不可以忽略。

DVFS調(diào)度技術(shù)則負(fù)責(zé)管理系統(tǒng)產(chǎn)生的動(dòng)態(tài)功耗，利用處理器工作頻率和功耗之間的凸關(guān)系，降低處理器核心工作頻率已達(dá)到減小能耗的目的，同時(shí)延長(zhǎng)執(zhí)行時(shí)間，減少處理器的空閑狀態(tài)，從而可以減小處理器狀態(tài)切換帶來的能耗。

隨著計(jì)算系統(tǒng)架構(gòu)的發(fā)展，DVFS調(diào)度技術(shù)已經(jīng)從單核處理器DVFS調(diào)度技術(shù)[1-3]，

發(fā)展到多核/多處理器DVFS調(diào)度技術(shù)[4-6]，而多核/多處理器DVFS調(diào)度技術(shù)從同構(gòu)多核/多處理器DVFS調(diào)度技術(shù)發(fā)展到異構(gòu)多核/多處理器DVFS調(diào)度技術(shù)[7-8]。根據(jù)應(yīng)用于實(shí)時(shí)系統(tǒng)和非實(shí)時(shí)系統(tǒng)的差異進(jìn)行分類，DVFS調(diào)度技術(shù)可以分為基于實(shí)時(shí)系統(tǒng)的DVFS調(diào)度技術(shù)[9-10]和基于非實(shí)時(shí)系統(tǒng)的DVFS調(diào)度技術(shù)。

在異構(gòu)多核平臺(tái)實(shí)時(shí)系統(tǒng)DVFS調(diào)度技術(shù)中，啟發(fā)式算法使用較為廣泛。文獻(xiàn)[11]中針對(duì)幀任務(wù)提出了min-min啟發(fā)式算法，該算法首先計(jì)算未分配任務(wù)的最小完成時(shí)間，然后選擇預(yù)期完成時(shí)間最小的任務(wù)分配給對(duì)應(yīng)的處理器;文獻(xiàn)[12]中提出了max-min啟發(fā)式算法，該算法與min-min區(qū)別在于計(jì)算完任務(wù)最小完成時(shí)間后，將預(yù)期完成時(shí)間最大的任務(wù)分配給相應(yīng)的處理器，優(yōu)點(diǎn)在于保證了平臺(tái)的負(fù)載均衡。啟發(fā)式算法能夠快速地得到處理器的任務(wù)分配方案，但是算法產(chǎn)生的能耗較大。文獻(xiàn)[13]中針對(duì)周期任務(wù)提出了最大本地剩余執(zhí)行時(shí)間優(yōu)先（Largest Local Remaining Execution Time First， LLREF）算法，根據(jù)任務(wù)剩余時(shí)間對(duì)各個(gè)處理器核心分配任務(wù)，但頻繁的算法調(diào)用和任務(wù)遷移同樣產(chǎn)生了巨大能耗。

近年來，基于優(yōu)化理論的算法已經(jīng)運(yùn)用到DVFS任務(wù)調(diào)度技術(shù)中。文獻(xiàn)[14]中將多處理器任務(wù)調(diào)度問題表示為無限維最優(yōu)控制問題，建立了三種優(yōu)化理論模型，但沒有對(duì)模型進(jìn)行詳細(xì)的求解;同時(shí)還提出了可調(diào)度性算法的概念，如果算法產(chǎn)生的任務(wù)分配方案沒有超過任務(wù)截止期限的情況出現(xiàn)，即滿足可調(diào)度性條件。

文獻(xiàn)[15]中提出了基于松弛簡(jiǎn)單取整算法（Relaxation-based Naive Rounding Algorithm， RNRA），并在此基礎(chǔ)上提出了基于松弛的迭代取整算法（Relaxation-based Iterative Rounding Algorithm， RIRA），兩種算法假設(shè)不同任務(wù)在不同處理器的執(zhí)行效率不同，對(duì)最小處理器能耗問題建立凸優(yōu)化模型，并運(yùn)用優(yōu)化理論求解最優(yōu)能耗問題。這類算法雖然產(chǎn)生的能耗較低，但是算法復(fù)雜度較高，求解時(shí)間較長(zhǎng)，而且沒有考慮算法可調(diào)度性條件，使得算法求解結(jié)果可用價(jià)值不高。

本文針對(duì)周期任務(wù)調(diào)度算法存在的問題，提出了減少迭代算法（Decrease Iteration Algorithm， DIA）。該算法對(duì)周期任務(wù)最小能耗問題建立模型，通過限制處理器的利用率以提高算法的可調(diào)度性，對(duì)模型求解結(jié)果進(jìn)行判決處理，得到部分任務(wù)的分配方案。剩余任務(wù)根據(jù)平均任務(wù)密度排序后，重新定義能耗模型，優(yōu)先分配密度較大的任務(wù)，通過這種方式，算法產(chǎn)生的能耗接近理論最優(yōu)值，不僅能夠更快地得到所有任務(wù)的分配結(jié)果，而且能提高算法的可調(diào)度性。

1 系統(tǒng)模型

1.1 任務(wù)模型

1.2 平臺(tái)模型

假設(shè)多處理器片上系統(tǒng)（SoC）有m個(gè)異構(gòu)處理器，記為Ψ={Ψ1，Ψ2，…，Ψm}，所有的處理器均可利用DVFS技術(shù)動(dòng)態(tài)調(diào)節(jié)電壓/頻率。定義sji∈（0，1]為任務(wù)Ti在處理器Ψ j上的執(zhí)行速率，對(duì)應(yīng)的WCET可表示為Ci/（sjif）。假定m個(gè)異構(gòu)處理器核心為理想的處理器核心，其頻率范圍在（0， fmax）連續(xù)可變。

1.3 功耗模型

處理器采用互補(bǔ)金屬氧化物半導(dǎo)體（Complementary Metal Oxide Semiconductor， CMOS）工藝制造的SoC，每個(gè)核心具有獨(dú)立的DVFS功能，

其每個(gè)處理器核心的功耗由三個(gè)部分組成：1）動(dòng)態(tài)功耗，記為Pdynamic;2）靜態(tài)功耗，記為Pstatic;3）固有功耗，記為Pon。

假定在SoC中有m個(gè)異構(gòu)處理器核心，其處理器核心的總功耗的表達(dá)式為：處理器的動(dòng)態(tài)功耗可以近似表達(dá)為：

其中：? β j為與Ψ j設(shè)計(jì)和工藝相關(guān)的常量值。

文獻(xiàn)[9]的研究表明，當(dāng)功耗函數(shù)為凸函數(shù)時(shí)，恒定頻率產(chǎn)生的能耗優(yōu)于時(shí)變頻率的，所以本文功耗模型只考慮恒定頻率，不考慮時(shí)變頻率。由于Pon在SoC中對(duì)于所有異構(gòu)核心都是統(tǒng)一依賴的，只有當(dāng)系統(tǒng)所有核心和外部電路都沒有工作時(shí)，可以利用DPM技術(shù)進(jìn)行關(guān)閉，Pon的最小化問題不屬于本文研究范疇，故本文不討論固有功耗。

另外，當(dāng)Ψ j處于普通的激活模式時(shí)，P jstatic對(duì)于整個(gè)系統(tǒng)功耗貢獻(xiàn)比例相對(duì)于動(dòng)態(tài)功耗來說非常小，同時(shí)任務(wù)集的分配問題對(duì)P jstatic的影響也非常小，因此本文假定采用如下簡(jiǎn)化的功耗函數(shù)：

本文采用文獻(xiàn)[16-17]中處理器核心功耗模型，假定所有異構(gòu)處理器核心有兩種工作模式：1）激活模式。在該模式下功耗函數(shù)符合式（2）定義。2）空閑模式。該模式下所有功耗為0。

某個(gè)處理器在激活模式下執(zhí)行任務(wù)，當(dāng)沒有任務(wù)執(zhí)行時(shí)，立即從激活模式進(jìn)入空閑模式。

由于這種模式間轉(zhuǎn)換的能耗開銷與處理器上執(zhí)行完成任務(wù)的功耗相比非常小，因此假定這部分的開銷已經(jīng)包含在任務(wù)執(zhí)行的過程之中。

1.4 問題定義

給定一組實(shí)時(shí)周期任務(wù)集T={T1，T2，…，Tl}，將任務(wù)分配到m個(gè)異構(gòu)處理器核心，使得任務(wù)不超過截止期限的條件下所有處理器產(chǎn)生的總能耗最小。設(shè)任務(wù)集Ti對(duì)應(yīng)的最壞情況執(zhí)行指令周期集合為C={C1，C2，…，Cl}，由于處理器核心的異構(gòu)特性，同一任務(wù)在不同的處理器的執(zhí)行效率不同，定義任務(wù)的執(zhí)行速率矩陣：矩陣的元素值1表示任務(wù)已分配，0表示任務(wù)未被分配。假設(shè)xji=1，矩陣行向量表示任務(wù)Ti分配到處理器核心Ψ j。

由于系統(tǒng)產(chǎn)生的功耗和處理器工作頻率的三次方成正比關(guān)系，當(dāng)處理器的工作頻率下降，任務(wù)的執(zhí)行時(shí)間變長(zhǎng)。系統(tǒng)的能耗可表示為處理器功耗與執(zhí)行時(shí)間的乘積（E=Pt），因此，為了使系統(tǒng)產(chǎn)生盡可能小的能耗，系統(tǒng)的工作頻率和時(shí)間需要達(dá)到一種平衡。同時(shí)為了滿足任務(wù)實(shí)時(shí)性的條件，任務(wù)的完成時(shí)間不得超過截止期限D(zhuǎn)i。通過求解分配矩陣A和處理器工作頻率fM，最后得到系統(tǒng)的最小能耗E。

2 任務(wù)分配算法

2.1 問題分析

任務(wù)集T={T1，T2，…，Tl}在0時(shí)刻同時(shí)釋放，任務(wù)數(shù)大于處理器核心數(shù)（l>m），總存在處理器核心執(zhí)行多個(gè)任務(wù)，為了確保其執(zhí)行先后順序，定義任務(wù)Ti在m個(gè)處理器以最大頻率fjmax工作時(shí)的平均任務(wù)密度（Average Task Density， ATD）為：

式（6）對(duì)處理器的工作頻率fj進(jìn)行歸一化處理（fj= fjreal/fjmax），此時(shí)的工作頻率為1。對(duì)任務(wù)的平均執(zhí)行時(shí)間進(jìn)行降序排列ATDi1≥ATDi2≥…≥ATDil，排序后的任務(wù)集為T={Ti1，Ti2，…，Til}。平均任務(wù)密度的大小代表任務(wù)的執(zhí)行需求不同，平均任務(wù)密度越大，系統(tǒng)執(zhí)行任務(wù)產(chǎn)生的能耗越大。由滿足負(fù)載均衡的任務(wù)分配方法得到啟發(fā)，在分配時(shí)優(yōu)先分配平均任務(wù)密度較大的任務(wù)。

為了使系統(tǒng)產(chǎn)生最小能耗并且滿足任務(wù)不超過截止期限的條件，由文獻(xiàn)[18]可知，每個(gè)處理器核心中任務(wù)的利用率之和要無限接近1，如式（7）所示。從而，每個(gè)處理器核心中任務(wù)的利用率之和不大于1可作為算法可調(diào)度性標(biāo)準(zhǔn)。

對(duì)于式（13）描述的最優(yōu)能耗的任務(wù)分配問題屬于二進(jìn)制整數(shù)規(guī)劃問題，求解難度較大。在最優(yōu)理論中，整數(shù)線性規(guī)劃問題的可行域是其松弛問題的子集。所以，為了方便得出最優(yōu)解，在這里需要重新定義分配矩陣。將分配矩陣A松弛化后得到：

2.2 求解算法

通過內(nèi)點(diǎn)法求得松弛化的分配矩陣，分配矩陣中的元素值在[0，1]中連續(xù)，然而最終的分配結(jié)果有如下條件：

由于松弛問題的最優(yōu)解不一定是整數(shù)規(guī)劃問題的最優(yōu)解，為了盡可能得到接近理論最優(yōu)能耗的分配矩陣，RNRA對(duì)分配矩陣進(jìn)行簡(jiǎn)單處理，將每行元素最大者判為1，其余元素判為0，由式（7）可知，此方法會(huì)變相放大分配元素x值而導(dǎo)致處理器核心利用率大于1。為了避免此問題出現(xiàn)，本文算法首先對(duì)矩陣中的元素進(jìn)行門限判決，大于門限值Δ判為1，小于門限值則判為0。當(dāng)k個(gè)任務(wù)完成分配，分配矩陣可以分解為已分配矩陣A*1和未分配矩陣A*2兩個(gè)矩陣。

由此得出部分任務(wù)的分配方案，并通過式（19）計(jì)算每個(gè)處理器核心的利用率，在分配的過程中保證每個(gè)處理器核心的利用率Uj≤1是分配的前提，利用率超出1分配方案將不滿足實(shí)時(shí)性的條件。

接下來求解分配矩陣A*2。對(duì)于未分配任務(wù)，在確定分配方案之前，先根據(jù)任務(wù)的ATD進(jìn)行降序排列。這里采用文獻(xiàn)[15]中RIRA的思路，先固定部分任務(wù)分配方案，得到每個(gè)處理器核心的利用率后，最優(yōu)能耗模型更新為式（20），求解剩余的任務(wù)分配方案。

將A*2的首行元素值最大值判為1，剩余元素值判為0，剩余行元素判為0，將未分配矩陣首行元素增加到已分配矩陣中。已分配任務(wù)矩陣和未分配任務(wù)矩陣得到更新，優(yōu)化能耗模型同樣再次更新。運(yùn)用同樣的方式，進(jìn)行多次迭代求解所有任務(wù)的分配方案。

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

通過設(shè)置一系列仿真實(shí)驗(yàn)評(píng)估算法的調(diào)度能力，同時(shí)把本文算法與RIRA、RNRA的歸一化能耗（即算法能耗值與理論最優(yōu)值的比值）、利用率大于1次數(shù)（可調(diào)度性）和算法執(zhí)行時(shí)間進(jìn)行對(duì)比。所有的仿真實(shí)驗(yàn)在Matlab 2018a中實(shí)現(xiàn)，操作系統(tǒng)為Windows 10家庭中文版，版本為1803，處理器是lntel Core i5-8265U CPU @ 1.6GHz 1.8GHz。

仿真實(shí)驗(yàn)?zāi)M24個(gè)周期任務(wù)分配到6個(gè)處理器核心中。任務(wù)的周期是一定范圍內(nèi)的隨機(jī)值，24個(gè)任務(wù)周期的均值為100。為了驗(yàn)證不同的任務(wù)周期范圍對(duì)算法調(diào)度能力的影響，在實(shí)驗(yàn)中設(shè)置5種周期范圍，分別為[50，150]、[60，140]、[70，130]、[80，120]、[90，110]。根據(jù)參考文獻(xiàn)[15]中生成幀任務(wù)集的方式，設(shè)置4組不同的WCEC范圍，每種范圍生成100組隨機(jī)任務(wù)。門限值Δ設(shè)置為0.99。

通過控制變量的方式，設(shè)置2組實(shí)驗(yàn)評(píng)估任務(wù)元素變化對(duì)算法歸一化能耗、利用率大于1次數(shù)和算法執(zhí)行時(shí)間的影響。

實(shí)驗(yàn)1 同一任務(wù)集設(shè)置不同的周期范圍。

為了驗(yàn)證DIA在不同任務(wù)周期下的調(diào)度能力，任務(wù)集設(shè)置以下參數(shù)：

1）隨機(jī)生成5種范圍的周期，每種100組，每組中有24個(gè)隨機(jī)數(shù)對(duì)應(yīng)到24個(gè)任務(wù)的周期，周期的均值為100。由于算法需要得出24個(gè)任務(wù)的最小公倍數(shù)即超周期，為了防止超周期過大而導(dǎo)致計(jì)算不準(zhǔn)確，對(duì)超周期進(jìn)行篩選，把每個(gè)任務(wù)的周期數(shù)值精確到個(gè)位，超周期最大不差過109。

2）WCEC范圍選擇[10，15]，生成一個(gè)24×6矩陣，矩陣中的元素值為[0.1，1]范圍內(nèi)的隨機(jī)數(shù)，表示24個(gè)任務(wù)在不同處理器的執(zhí)行速率，根據(jù)公式Ci/（sji f）得到任務(wù)在各個(gè)處理器的最壞情況執(zhí)行時(shí)間WCET。

實(shí)驗(yàn)結(jié)果如圖1～3所示：圖1中把每種周期范圍100組任務(wù)的能耗值取平均，然后與理論最優(yōu)能耗值相比;圖2是平均每組任務(wù)超過截止期限的次數(shù);圖3表示每種算法在不同周期范圍執(zhí)行時(shí)間。

由圖1可知，三種算法在不同周期范圍內(nèi)的歸一化能耗波動(dòng)較小，都很接近理論最優(yōu)能耗，隨著周期寬度的下降，能耗值略微下降。DIA與RNRA相比，前者的歸一化能耗比后者平均優(yōu)化1.1%，當(dāng)周期范圍是[50，150]，DIA比RNRA優(yōu)化1.4%，效果達(dá)到最好。在5種周期范圍，DIA能耗最接近RIRA，RIRA略小于DIA，平均約小0.5%。然而，在圖3中，RIRA與其他算法執(zhí)行時(shí)間差距較大，DIA平均執(zhí)行時(shí)間為1.02s，RNRA執(zhí)行最小，平均為0.85s，RIRA的執(zhí)行時(shí)間較長(zhǎng)，平均為7.65s。從圖2可以看出，三種算法隨著周期范圍的變窄，利用率大于1的次數(shù)逐漸在減少，DIA在周期范圍[90，110]時(shí)沒有處理器核心利用率大于1的次數(shù)出現(xiàn)，完全避免了任務(wù)超過截止期限的情況。RNRA超過利用率次數(shù)1的次數(shù)最多。

由實(shí)驗(yàn)1可以得出，DIA在歸一化能耗方面接近于理論最優(yōu)值，只比RIRA稍高0.7%，但是在算法執(zhí)行效率方面得到了大幅優(yōu)化，同時(shí)在超出截止期限次數(shù)方面也得到了明顯的減少。DIA能夠擁有RIRA和RNRA的優(yōu)點(diǎn)，在減小能耗的同時(shí)降低算法的執(zhí)行時(shí)間，能夠在更短的時(shí)間內(nèi)獲得有效的分配方案。

實(shí)驗(yàn)2 固定周期設(shè)置不同的WCEC范圍。

為了驗(yàn)證DIA對(duì)不同負(fù)載任務(wù)的調(diào)度能力，任務(wù)集設(shè)置以下參數(shù)：

1）設(shè)置100組周期范圍為[80，120]的任務(wù)集，每組生成24個(gè)隨機(jī)數(shù)對(duì)應(yīng)24個(gè)任務(wù)的周期，每組任務(wù)集周期的均值為100。與實(shí)驗(yàn)1相同，過濾掉較大的超周期。

2）設(shè)置4種WCEC范圍，任務(wù)設(shè)置1的WCEC范圍為[1，5]，任務(wù)設(shè)置2的WCEC范圍為[5，10]，任務(wù)設(shè)置3的WCEC范圍為[10，15]，任務(wù)設(shè)置4的WCEC范圍為[15，20]， WCEC生成方式同實(shí)驗(yàn)設(shè)置1，每種WCEC范圍生成100組任務(wù)集。

表1為各算法不同任務(wù)設(shè)置的歸一化能耗。RNRA歸一化能耗表現(xiàn)最差，DIA在[1，5]、[5，10]、[10，15]三種WCEC范圍中的歸一化能耗略高于RIRA，當(dāng)WCEC范圍是[15，20]時(shí)，DIA能耗值優(yōu)于RIRA約0.6%，僅僅比理論最優(yōu)值高1.8%。三種算法在[1，5]、[5，10]兩種范圍的WCEC中都沒有出現(xiàn)利用率大于1的情況。當(dāng)WCEC為[10，15]時(shí)，DIA處理器核心的利用率沒有超過1的情況，算法的可調(diào)度性為100%;而RIRA和RNRA表現(xiàn)較差。在算法執(zhí)行時(shí)間方面，三種算法波動(dòng)較小，RNRA執(zhí)行時(shí)間最短約為0.87s，其次DIA為0.96s，RIRA表現(xiàn)最差為7.84s。

由實(shí)驗(yàn)2可知，DIA調(diào)度不同負(fù)載任務(wù)的能耗值接近RIRA，隨著任務(wù)負(fù)載的加大，DIA與RIRA的差距逐漸縮小，在WCEC范圍為[10，15]時(shí)產(chǎn)生優(yōu)于RIRA的能耗。

在算法執(zhí)行時(shí)間方面，DIA大幅度領(lǐng)先RIRA，能夠在更短的時(shí)間完成任務(wù)調(diào)度，同時(shí)產(chǎn)生更低的能耗。在可調(diào)度性方面，DIA優(yōu)于RNRA和RIRA，在中低負(fù)載情況下算法可調(diào)度性達(dá)到100%。

4 結(jié)語

本文針對(duì)異構(gòu)多核平臺(tái)中的非搶占式周期任務(wù)提出了減少迭代算法DIA。該算法首先對(duì)周期任務(wù)的最小能耗問題進(jìn)行建模，每個(gè)處理器利用率不超過1作為模型的限制條件，運(yùn)用優(yōu)化理論求解最小能耗問題，對(duì)求解結(jié)果通過判決門限進(jìn)行初步處理后得到部分任務(wù)的分配結(jié)果，在此結(jié)果基礎(chǔ)上通過迭代的方式動(dòng)態(tài)求解剩余任務(wù)的分配方案。實(shí)驗(yàn)結(jié)果表明，DIA得到的分配方案產(chǎn)生的能耗更加接近理論最優(yōu)值，節(jié)能效果略優(yōu)于已有算法，但是算法的執(zhí)行時(shí)間比現(xiàn)有算法大幅減少。

由于處理器利用率不大于1這一限制條件的存在，提高了算法可調(diào)度性，使得任務(wù)調(diào)度更加滿足實(shí)時(shí)性的條件。在未來，筆者將對(duì)算法進(jìn)行改進(jìn)，使得算法能耗更加接近理論最優(yōu)值的同時(shí)，不僅減少當(dāng)處理器負(fù)載較高時(shí)任務(wù)分配方案超過截止期限的次數(shù)，而且進(jìn)一步減少算法迭代次數(shù)，使得算法能夠在更短的時(shí)間內(nèi)完成任務(wù)的分配。

參考文獻(xiàn)（References）

[1] NIELSEN L S， NIESSEN C， SPARSO J， et al. Low-power operation using self-timed circuits and adaptive scaling of the supply voltage[J]. IEEE Transactions on Very Large Scale Integration Systems， 1994， 2（4）： 391-397.

[2] BURD T D， PERING T A， STRATAKOS A J， et al. A dynamic voltage scaled microprocessor system[J]. IEEE Journal of Solid-State Circuits， 2000， 35（11）： 1571-1580.

[3] NOWKA K J， CARPENTER G D， MACDONALD E W， et al. A 32-bit powerpc system-on-a-chip with support for dynamic voltage scaling and dynamic frequency scaling[J]. IEEE Journal of Solid-State Circuits， 2002， 37（11）： 1441-1447.

[4] SEO E， JEONG J， PARK S， et al. Energy efficient scheduling of real-time tasks on multicore processors[J]. IEEE Transactions on Parallel and Distributed Systems， 2008， 19（11）： 1540-1552.

[5] LI K. Performance analysis of power-aware task scheduling algorithms on multiprocessor computers with dynamic voltage and speed[J]. IEEE Transactions on Parallel and Distributed Systems， 2008， 19（11）： 1484-1497.

[6] MANUMACHU R R， LASTOVETSKY A. Bi-objective optimization of data-parallel applications on homogeneous multicore clusters for performance and energy[J]. IEEE Transactions on Computers， 2018， 67（2）： 160-177.

[7] LI Y， NIU J， ATIQUZZAMAN M， et al. Energy-aware scheduling on heterogeneous multi-core systems with guaranteed probability[J]. Journal of Parallel and Distributed Computing， 2017， 103： 64-76.

[8] PAGANI S， PATHANIA A， SHAFIQUE M， et al. Energy efficiency for clustered heterogeneous multicores[J]. IEEE Transactions on Parallel and Distributed Systems， 2017， 28（5）： 1315-1330.

[9] CHENG D， ZHOU X， LAMA P， et al. Energy efficiency aware task assignment with DVFS in heterogeneous Hadoop clusters[J]. IEEE Transactions on Parallel and Distributed Systems， 2018， 29（1）： 70-82.

[10] ZHOU J， YAN J， CAO K， et al. Thermal-aware correlated two-level scheduling of real-time tasks with reduced processor energy on heterogeneous MPSoCs[J]. Journal of Systems Architecture， 2018， 82： 1-11.

[11] SUN W， SUGAWARA T. Heuristics and evaluations of energy-aware task mapping on heterogeneous multiprocessors[C]// Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum. Piscataway： IEEE， 2011： 599-607.

[12] IZAKIAN H， ABRAHAM A， SNASEL V. Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments[C]// Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization. Piscataway： IEEE， 2009： 8-12.

[13] XU C， XIAO J， ZENG L， et al. An energy-aware dynamic algorithm based on variable interval DVFS technology[J]. Advanced Materials Research， 2014， 950： 185-195.

[14] THAMMAWICHAI M， KERRIGAN E C. Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors[J]. Real-Time Systems， 2018， 54（1）： 132-165.

[15] LI D， WU J. Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[J]. IEEE Transactions on Parallel and Distributed Systems， 2015， 26（3）： 810-823.

[16] ALBERS S， ANTONIADIS A， GREINER G. On multi-processor speed scaling with migration[J]. Journal of Computer and System Sciences， 2015， 81（7）： 1194-1209.

[17] ANGEL E， BAMPIS E， KACEM F， et al. Speed scaling on parallel processors with migration[C]// Proceedings of the 18th International Conference of Parallel Processing， LNCS 7484. Berlin： Springer， 2012： 128-140.

[18] KHAN A A， ALI A， ZAKARYA M， et al. A migration aware scheduling technique for real-time aperiodic tasks over multiprocessor systems[J]. IEEE Access， 2019， 7： 27856-27873.