星載異構計算環境下的能耗優化任務調度

安建峰，游紅俊，趙偉勛，劉咪咪，張盛兵

（1.西北工業大學 計算機學院，陜西 西安 710129；2.上海航天電子技術研究所，上海 201109）

0 引言

在諸如航天探測系統等尖端領域里，系統對安全性、可靠性、實時性以及功耗都有較高的要求，其中，安全性和可靠性一般通過硬件設備進行保障，實時性及功耗往往通過合理的任務調度方案來保證。隨著近些年異構多核處理器的發展，在異構平臺上，如何處理上述問題成為一種研究方向。

異構多核處理器由不同類型的處理器核組成，相比較單核、同構多核處理器具有獨特的優勢，能夠更有針對性地處理特定的事件。常見的異構多核處理器有CPU 和GPU，或FPGA 的集成、ARM的BIG.LITTLE 架構等，根據處理器核的類型數量稱之為二型異構多核處理器。在異構處理器中，研究最為廣泛的就是ARM BIG.LITTLE 架構處理器下的任務調度算法［1-3］。

異構多核處理器的任務調度已經被證明是NP完全問題，目前還沒有算法可以在多項式時間內求得最優解，現有算法大多使用啟發式的算法求得近似解［4］。異構調度模式一般分為3 種類型：不遷移、同構核間遷移以及全局核間遷移。

1）不遷移［5-7］是指當任務分配到一個處理器核后只在該處理器核上執行；

2）同構核間遷移是指任務在執行期間可以遷移到同種類型的處理器核上執行；

3）全局核間遷移是指一個任務在執行期間可以遷移到任意類型處理器核上執行。

RARAVI 等［8］提出了用整數線性規劃（Integer Linear Programming，ILP）的方法來解決同構核間遷移模式下的任務調度問題，并且提出了一種按分類進行分配的近似算法（Sort and Assign，SA）。BARUAH［9］對全局核間遷移模式下周期性任務調度的可行性進行了分析和研究，通過一組線性規劃（Linear Programming，LP）約束判定對于給定處理器平臺和任務集是否存在可行的調度方案。CHWA 等［10］提出了一種最優的全局核間遷移模式下的周期性任務調度算法，然而其未考慮功耗問題。李延祺等［11］提出一系列基于計算概率的建模方法，用來解決星載實時嵌入式系統中，對于具有數據依賴的非周期性任務的處理器和電壓分配相關問題，在所有時間約束下具有更好的能效。楊亞琪等［12］提出一種異構多核下兼顧應用公平性和能耗的調度方法。

本文的主要工作是以二型異構多處理器為調度平臺，將調度算法分為負載分配及任務調度2 個步驟：

1）負載分配算法EB-Split 是在CHWA 等［10］提出的全遷移算法（Hetero-Split）基礎上加入能耗優化的思想；

2）任務調度算法BI-Wrap 則根據負載分配的結果合理安排任務時間片，保證調度的可行性。

實驗表明：本算法在不損失Hetero-Split 算法所能尋找到的可行方案數的條件下，能耗降低約23%～24%。

1 系統模型構建

約定每一個任務都獨立且可搶占，可以在處理器集群內部，也可以跨集群進行任務的遷移，假定這些遷移代價可以接受。每一個任務都會被重復地調用，每一個此類調用稱為一個作業或者任務實例。

調度遵從非并行執行（No Parallel Execution，NPE）限制：

1）每個處理器在任一時刻只能運行一個任務；

2）一個任務實例任一時刻只能運行在一個處理器上。

為了方便調度算法的設計，將調度方案分為2個子部分：負載分配和任務調度。

1）負載分配問題決定了在保證實時性的條件下，每個任務在每個類型的處理器核上該分配多少子任務，同時盡可能降低系統能耗；

2）調度生成問題在解決負載分配問題的基礎上，生成一個合理的調度方式使得所有任務都可以滿足截止期約束條件。

2 負載分配算法EB-Split

基于能耗優化的二型異構負載分配算法EBSplit 是在文獻［10］中的分配算法的基礎上加入能耗的因素，調整任務分配，使得在保證可調度性的條件下，盡量減小系統能耗。

2.1 可行性條件

為了保證任務的截止期約束，任務τi應該分配給type-1 類型和type-2 類型處理器集群的最小任務分配量分別記作和。任務τi在兩類集群上的剩余工作負載分別記作和，即

為使給每個處理器集群分配的任務可調度，以下條件必須滿足：

綜上，負載分配算法Hetero-Split 理論上保證了只要存在則必然能夠找到可行的負載分配方案［10］。

2.2 基于能耗的分配調整

對于給定的處理器平臺和任務集，理論上可能存在多種滿足要求的任務調度方案。設SUR 代表Surplus。

定義type-1 和type-2 類型處理器集群執行能力剩余量分別為SUR1和SUR2，則由約束條件C3和C4可得

能耗優化算法的思想就是在保證SUR1和SUR2都非負的前提下，調整和的大小，盡可能地降低系統總能耗。

2.3 能耗優化目標

系統總能耗E由各任務在2 種類型處理器集群上的能耗之和得到，因此，在給定時間片長度L下，該時間片內的系統總能耗的計算公式如下：

2.4 能耗優化分析

式中：W1為那些已經分配到type-1 類型的處理器群上（＞0），但是從減小系統能耗的角度則更適合分配到type-2 類型處理器群上的任務；W2同理。

首先考慮從W1中選取任務τi，將其以更大的比例重新分配到type-2 類型的處理器群上。用表示在分配調整的過程中任務τi在2 種類型處理器上的分配比例變化，即重新分配后有

設ΔU2為SUR2在該過程中的減小量，ΔE為系統總能耗E在該過程中的減小量，則由式（2）可得

在不考慮能耗的任務分配方案下，SUR2為定值，所以為最大限度地減小系統的總能耗，從W1中選取任務的規則就是每次選取對應ΔE/ΔU2值即值最大的任務，以一定的比例ki(ki≤)重新調整到type-2 類型處理器核上；從W2中選取任務的方法同理。

2.5 分配方法

對于W1和W2中元素存在與否，分為以下4 種情況：

1）W1和W2均為空：表示已經不存在待調整的任務，分配方案結束；

2）W1非空，W2為空：選取W1中的第一個任務τi，以比例ki重新調整到type-2 類型處理器核上；

3）W1非空，W2為空：與2）同理；

4）W1和W2均非空。

選取W1中的第一個任務τi，以比例ki重新調整到type-2 類型處理器核上；選取W2中的第一個任務τj，以比例kj重新調整到type-1 類型處理器核上。為使SUR1和SUR2都非負，需要保證滿足以下幾個條件：

在此過程中，系統總能耗的減小量ΔE為

為在滿足約束條件CC 的情況下使得ΔE最大，利用二元線性規劃，易求得ki和kj，根據ki和kj值做相應的分配比例調整。

3 任務調度算法BI-Wrap

為保證在EB-Split 算法下所有的任務都滿足截止期需求且不違背NPE 原則，還需設計一種合適的任務調度方法，決定在某一時刻哪個任務具體在哪個處理器核上執行。

3.1 時間片劃分

LEVIN 和FUNK 證明了對于一個多核處理器上的任務調度問題，如果參與調度的任務具有2 個或者2 個以上的不同的截止期，那么就無法找到合適的任務調度方案。而如果任務集中的所有任務都具有相同的截止期，那么就可以找到可行的任務調度方案［13］。

因此，在二型異構多核平臺上，要保證任務集中的所有任務都具有相同的截止期，可采用時間片劃分［14-16］的思想，將整個時間軸劃分為多個時間片，每個時間片分配相應的任務工作量，即同一個時間片內部所要調度的任務均共享同一個截止期。

3.2 時間片劃分方法

每個任務τi在執行過程中會產生多個周期性的作業，每個作業的釋放周期為相對截止時間Ti，故任務τi所釋放的第k個作業的絕對截止時間為k×Ti。

將所有任務τi∈τ的所有絕對截止時間呈現于同一時間軸上，按照絕對時間的先后順序定義為時間節點tj（j=0，1，…，j），其中，t0=0 表示時間軸的起始節點，也是任務調度執行的開始時間。用σj表示時間片劃分完成后的第j個時間片，用Lj表示第j個時間片的長度，則時間片劃分的結果為

3.3 時間片上的任務工作量安排

在長度為Lj的時間片σj內，根據等比例劃分的方法，任務τi在type-1 類型處理器上的工作量安排為

在type-2 類型處理器上的工作量安排與type-1同理。

3.4 BI-Wrap 調度算法

τa、τb表示。

定 義 4 個隊列：P1、R1、P2、R2，將集合{E，M，SP1，SP2}中的任務按照下列規則添加到這4個隊列中：

在type-1 類型處理器群以及type-2 類型處理器群上分別對分配好的任務進行調度，調度規則如下：

1）在type-1 類型的處理器上，從core 1 開始，按照處理器核編號遞增且時間遞增的方式對隊列P1中的任務依次進行調度。

2）在type-1 類型的處理器上，從corem1開始，按照處理器核編號遞減且時間遞減的方式對隊列R1中的任務依次排列在時間片上，調度時按時間遞增方向進行。

3）在type-2 類型的處理器上，從core 1 開始，按照處理器核編號遞增且時間遞增的方式對隊列P2中的任務依次進行調度。

4）在type-2 類型的處理器上，從corem2開始，按照處理器核編號遞減且時間遞減的方式對隊列R2中的任務依次排列在時間片上，調度時按時間遞增方向進行。

3.5 調度舉例

任務集的劃分結果為

由調度規則可得

應用BI-Wrap 算法中的調度規則在所劃分的第1 個時間片（σ1=[ 0，60)，L1=60）上對上述4 個隊列中的任務實例進行調度，調度結果如圖1 所示。

圖1 BI-Wrap 調度算法實例Fig.1 Examples of the BI-Wrap schedule algorithm

如圖1 所示，采用BI-Wrap 算法進行任務調度可保證在第1 個時間片內分配的任務工作量都能在時間片截止之前完成，且所有任務在調度過程中都滿足非并行執行性。

3.6 BI-Wrap 算法的時間復雜度

BI-Wrap 算法首先將整個任務集劃分為4 個子集，這一過程的時間復雜度為O(n)，然后，BIWrap 算法對這4 個子集中的任務均按照既定的規則進行順序調度，這一過程的時間復雜度也為O(n)。因此，整個BI-Wrap 算法的時間復雜度為O(n)。

4 仿真試驗及結果分析

4.1 仿真實驗

在Windows 平臺下用C++語言模擬算法的調度過程，對SA 算法、Hetero-Split 算法及EB-Split 算法（使用BI-Wrap 算法進行調度）分別進行了模擬調度。

對算法的輸入數據，設置處理器集群（m1，m2）的個數平均至少大于2，任務集τ中的每個任務（τi）在不同處 理器集群 上的參數元組值均由隨機函數生成。實驗每次測試的任務集數目為10 000。根據分析，實驗將首先執行算法的負載分配以追求低能耗的目標，然后，按照BI-Wrap 算法保證分配好的負載能夠進行調度。

首先測試得到3 種算法各自滿足系統約束的可行任務調度方案數見表1。

表1 各算法所求的可行方案數Tab.1 Numbers of feasible schemes for each algorithm

由實驗結果可知，EB-Split 算法不損失Hetero-Split 算法求得的可行方案數，且兩者均優于SA 算法。然后對比EB-Split 算法（使用BI-Wrap 算法進行調度）與Hetero-Split 算法（正常調度）的平均系統能耗（分別用E1_avg 和E2_avg 表示），每次測試得到的系統能耗按式（11）計算而得。并計算EB-Split算法相對于Hetero-Split 算法的能耗降低百分比R=（E1_avg-E2_avg）/E1_avg。實驗結果如表2、圖2 所示。

表2 Hetero-Split 與EB-Split 算法的能耗比Tab.2 Energy consumption ratios of the Hetero-Split and EB-Split algorithms

圖2 Hetero-Split 與EB-Split 的能耗對比Fig.2 Energy consumption of the Hetero-Split and EBSplit algorithms

由實驗結果可知，EB-Split 算法相較于Hetero-Split 算法在系統總能耗方面約降低23%～24%。

4.2 仿真結果分析

由實驗結果可知，EB-Split 算法與Hetero-Split算法在尋求可行性方案上性能相當且優于SA 算法。Hetero-Split 算法已被證明為可行方案數最優的［10］，故本文所設計的EB-Split 算法也滿足可行任一方案的最優性。此外，在能耗方面，EB-Split 算法相較于Hetero-Split 算法在系統總能耗方面有大幅度降低，降低比率約為23%～24%。

5 結束語

異構多核處理器上實時任務調度算法的設計向來是難點問題，尤其在航天探測等對系統各方面性能指標要求都比較高的尖端領域。本文設計的基于全遷移的、加入能耗約束的實時任務調度算法，在保證系統實時性的條件下對能耗進行了優化，在總體性能方面優于目前的較出色的SA 算法和Hetero-Split 算法。

由于本文未考慮并行、遷移開銷、任務相關性等方面的問題，因此，還有許多工作需進一步研究，且該任務調度算法目前雖然在能耗方面有較好的性能，但是并沒有達到在滿足實時約束條件下的最佳能耗。