基于異構多核平臺低能耗周期任務調度算法

夏軍 袁帥 楊逸

摘 要：針對異構多核平臺存在的高能耗問題，提出一種運用優化理論求解周期任務最優能耗分配方案的算法。該算法對周期任務的最優能耗問題進行建模，并對模型添加限制條件。根據優化理論將二進制整數規劃問題松弛化后得到凸優化問題，通過內點法求解優化問題并得到松弛化的分配矩陣，對分配矩陣進行判決處理后得到部分任務的分配方案。在此基礎上，通過迭代的方式求得剩余任務的分配方案。實驗結果表明，該分配方案產生的能耗與同類優化理論算法相比能耗降低約1.4%，

與能耗相當的優化理論算法相比執行時間減少86%，且僅比理論最優能耗值高2.6%。

關鍵詞：多處理器;節能調度;周期任務;利用率;優化理論

中圖分類號：TP316.2

文獻標志碼：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 引言

隨著嵌入式系統復雜度和性能要求的提升，多處理器片上系統（System on Chip， SoC）得到了廣泛的應用，同時，如何降低系統產生的高能耗成為社會關注的焦點。所以，在多處理器片上系統中能耗優化技術起到了重要的作用。在現有平臺中，處理器核心大多嵌入動態電壓頻率調節（Dynamic Voltage Frequency Scaling， DVFS）技術和動態電源管理（Dynamic Power Management， DPM）技術。DPM負責管理系統產生的靜態功耗，當處理器處于空閑狀態時，該技術將處理器工作模式切換到低功耗狀態。但是，DPM切換處理器狀態需要時間并產生一定的能耗。對于周期性任務來說，頻繁地切換處理器的工作狀態所產生的能耗不可以忽略。

DVFS調度技術則負責管理系統產生的動態功耗，利用處理器工作頻率和功耗之間的凸關系，降低處理器核心工作頻率已達到減小能耗的目的，同時延長執行時間，減少處理器的空閑狀態，從而可以減小處理器狀態切換帶來的能耗。

隨著計算系統架構的發展，DVFS調度技術已經從單核處理器DVFS調度技術[1-3]，

發展到多核/多處理器DVFS調度技術[4-6]，而多核/多處理器DVFS調度技術從同構多核/多處理器DVFS調度技術發展到異構多核/多處理器DVFS調度技術[7-8]。根據應用于實時系統和非實時系統的差異進行分類，DVFS調度技術可以分為基于實時系統的DVFS調度技術[9-10]和基于非實時系統的DVFS調度技術。

在異構多核平臺實時系統DVFS調度技術中，啟發式算法使用較為廣泛。文獻[11]中針對幀任務提出了min-min啟發式算法，該算法首先計算未分配任務的最小完成時間，然后選擇預期完成時間最小的任務分配給對應的處理器;文獻[12]中提出了max-min啟發式算法，該算法與min-min區別在于計算完任務最小完成時間后，將預期完成時間最大的任務分配給相應的處理器，優點在于保證了平臺的負載均衡。啟發式算法能夠快速地得到處理器的任務分配方案，但是算法產生的能耗較大。文獻[13]中針對周期任務提出了最大本地剩余執行時間優先（Largest Local Remaining Execution Time First， LLREF）算法，根據任務剩余時間對各個處理器核心分配任務，但頻繁的算法調用和任務遷移同樣產生了巨大能耗。

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

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

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

1 系統模型

1.1 任務模型

1.2 平臺模型

假設多處理器片上系統（SoC）有m個異構處理器，記為Ψ={Ψ1，Ψ2，…，Ψm}，所有的處理器均可利用DVFS技術動態調節電壓/頻率。定義sji∈（0，1]為任務Ti在處理器Ψ j上的執行速率，對應的WCET可表示為Ci/（sjif）。假定m個異構處理器核心為理想的處理器核心，其頻率范圍在（0， fmax）連續可變。

1.3 功耗模型

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

其每個處理器核心的功耗由三個部分組成：1）動態功耗，記為Pdynamic;2）靜態功耗，記為Pstatic;3）固有功耗，記為Pon。

假定在SoC中有m個異構處理器核心，其處理器核心的總功耗的表達式為：處理器的動態功耗可以近似表達為：

其中：? β j為與Ψ j設計和工藝相關的常量值。

文獻[9]的研究表明，當功耗函數為凸函數時，恒定頻率產生的能耗優于時變頻率的，所以本文功耗模型只考慮恒定頻率，不考慮時變頻率。由于Pon在SoC中對于所有異構核心都是統一依賴的，只有當系統所有核心和外部電路都沒有工作時，可以利用DPM技術進行關閉，Pon的最小化問題不屬于本文研究范疇，故本文不討論固有功耗。

另外，當Ψ j處于普通的激活模式時，P jstatic對于整個系統功耗貢獻比例相對于動態功耗來說非常小，同時任務集的分配問題對P jstatic的影響也非常小，因此本文假定采用如下簡化的功耗函數：

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

某個處理器在激活模式下執行任務，當沒有任務執行時，立即從激活模式進入空閑模式。

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

1.4 問題定義

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

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

2 任務分配算法

2.1 問題分析

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

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

為了使系統產生最小能耗并且滿足任務不超過截止期限的條件，由文獻[18]可知，每個處理器核心中任務的利用率之和要無限接近1，如式（7）所示。從而，每個處理器核心中任務的利用率之和不大于1可作為算法可調度性標準。

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

2.2 求解算法

通過內點法求得松弛化的分配矩陣，分配矩陣中的元素值在[0，1]中連續，然而最終的分配結果有如下條件：

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

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

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

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

3 仿真實驗及結果分析

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

仿真實驗模擬24個周期任務分配到6個處理器核心中。任務的周期是一定范圍內的隨機值，24個任務周期的均值為100。為了驗證不同的任務周期范圍對算法調度能力的影響，在實驗中設置5種周期范圍，分別為[50，150]、[60，140]、[70，130]、[80，120]、[90，110]。根據參考文獻[15]中生成幀任務集的方式，設置4組不同的WCEC范圍，每種范圍生成100組隨機任務。門限值Δ設置為0.99。

通過控制變量的方式，設置2組實驗評估任務元素變化對算法歸一化能耗、利用率大于1次數和算法執行時間的影響。

實驗1 同一任務集設置不同的周期范圍。

為了驗證DIA在不同任務周期下的調度能力，任務集設置以下參數：

1）隨機生成5種范圍的周期，每種100組，每組中有24個隨機數對應到24個任務的周期，周期的均值為100。由于算法需要得出24個任務的最小公倍數即超周期，為了防止超周期過大而導致計算不準確，對超周期進行篩選，把每個任務的周期數值精確到個位，超周期最大不差過109。

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

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

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

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

實驗2 固定周期設置不同的WCEC范圍。

為了驗證DIA對不同負載任務的調度能力，任務集設置以下參數：

1）設置100組周期范圍為[80，120]的任務集，每組生成24個隨機數對應24個任務的周期，每組任務集周期的均值為100。與實驗1相同，過濾掉較大的超周期。

2）設置4種WCEC范圍，任務設置1的WCEC范圍為[1，5]，任務設置2的WCEC范圍為[5，10]，任務設置3的WCEC范圍為[10，15]，任務設置4的WCEC范圍為[15，20]， WCEC生成方式同實驗設置1，每種WCEC范圍生成100組任務集。

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

由實驗2可知，DIA調度不同負載任務的能耗值接近RIRA，隨著任務負載的加大，DIA與RIRA的差距逐漸縮小，在WCEC范圍為[10，15]時產生優于RIRA的能耗。

在算法執行時間方面，DIA大幅度領先RIRA，能夠在更短的時間完成任務調度，同時產生更低的能耗。在可調度性方面，DIA優于RNRA和RIRA，在中低負載情況下算法可調度性達到100%。

4 結語

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

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

參考文獻（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.