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

（1.西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710129；2.上海航天電子技術(shù)研究所，上海 201109）

0 引言

在諸如航天探測系統(tǒng)等尖端領(lǐng)域里，系統(tǒng)對安全性、可靠性、實(shí)時性以及功耗都有較高的要求，其中，安全性和可靠性一般通過硬件設(shè)備進(jìn)行保障，實(shí)時性及功耗往往通過合理的任務(wù)調(diào)度方案來保證。隨著近些年異構(gòu)多核處理器的發(fā)展，在異構(gòu)平臺上，如何處理上述問題成為一種研究方向。

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

異構(gòu)多核處理器的任務(wù)調(diào)度已經(jīng)被證明是NP完全問題，目前還沒有算法可以在多項(xiàng)式時間內(nèi)求得最優(yōu)解，現(xiàn)有算法大多使用啟發(fā)式的算法求得近似解［4］。異構(gòu)調(diào)度模式一般分為3 種類型：不遷移、同構(gòu)核間遷移以及全局核間遷移。

1）不遷移［5-7］是指當(dāng)任務(wù)分配到一個處理器核后只在該處理器核上執(zhí)行；

2）同構(gòu)核間遷移是指任務(wù)在執(zhí)行期間可以遷移到同種類型的處理器核上執(zhí)行；

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

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

本文的主要工作是以二型異構(gòu)多處理器為調(diào)度平臺，將調(diào)度算法分為負(fù)載分配及任務(wù)調(diào)度2 個步驟：

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

2）任務(wù)調(diào)度算法BI-Wrap 則根據(jù)負(fù)載分配的結(jié)果合理安排任務(wù)時間片，保證調(diào)度的可行性。

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

1 系統(tǒng)模型構(gòu)建

約定每一個任務(wù)都獨(dú)立且可搶占，可以在處理器集群內(nèi)部，也可以跨集群進(jìn)行任務(wù)的遷移，假定這些遷移代價可以接受。每一個任務(wù)都會被重復(fù)地調(diào)用，每一個此類調(diào)用稱為一個作業(yè)或者任務(wù)實(shí)例。

調(diào)度遵從非并行執(zhí)行（No Parallel Execution，NPE）限制：

1）每個處理器在任一時刻只能運(yùn)行一個任務(wù)；

2）一個任務(wù)實(shí)例任一時刻只能運(yùn)行在一個處理器上。

為了方便調(diào)度算法的設(shè)計(jì)，將調(diào)度方案分為2個子部分：負(fù)載分配和任務(wù)調(diào)度。

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

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

2 負(fù)載分配算法EB-Split

基于能耗優(yōu)化的二型異構(gòu)負(fù)載分配算法EBSplit 是在文獻(xiàn)［10］中的分配算法的基礎(chǔ)上加入能耗的因素，調(diào)整任務(wù)分配，使得在保證可調(diào)度性的條件下，盡量減小系統(tǒng)能耗。

2.1 可行性條件

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

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

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

2.2 基于能耗的分配調(diào)整

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

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

能耗優(yōu)化算法的思想就是在保證SUR1和SUR2都非負(fù)的前提下，調(diào)整和的大小，盡可能地降低系統(tǒng)總能耗。

2.3 能耗優(yōu)化目標(biāo)

系統(tǒng)總能耗E由各任務(wù)在2 種類型處理器集群上的能耗之和得到，因此，在給定時間片長度L下，該時間片內(nèi)的系統(tǒng)總能耗的計(jì)算公式如下：

2.4 能耗優(yōu)化分析

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

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

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

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

2.5 分配方法

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

1）W1和W2均為空：表示已經(jīng)不存在待調(diào)整的任務(wù)，分配方案結(jié)束；

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

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

4）W1和W2均非空。

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

在此過程中，系統(tǒng)總能耗的減小量ΔE為

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

3 任務(wù)調(diào)度算法BI-Wrap

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

3.1 時間片劃分

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

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

3.2 時間片劃分方法

每個任務(wù)τi在執(zhí)行過程中會產(chǎn)生多個周期性的作業(yè)，每個作業(yè)的釋放周期為相對截止時間Ti，故任務(wù)τi所釋放的第k個作業(yè)的絕對截止時間為k×Ti。

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

3.3 時間片上的任務(wù)工作量安排

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

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

3.4 BI-Wrap 調(diào)度算法

τa、τb表示。

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

在type-1 類型處理器群以及type-2 類型處理器群上分別對分配好的任務(wù)進(jìn)行調(diào)度，調(diào)度規(guī)則如下：

1）在type-1 類型的處理器上，從core 1 開始，按照處理器核編號遞增且時間遞增的方式對隊(duì)列P1中的任務(wù)依次進(jìn)行調(diào)度。

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

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

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

3.5 調(diào)度舉例

任務(wù)集的劃分結(jié)果為

由調(diào)度規(guī)則可得

應(yīng)用BI-Wrap 算法中的調(diào)度規(guī)則在所劃分的第1 個時間片（σ1=[ 0，60)，L1=60）上對上述4 個隊(duì)列中的任務(wù)實(shí)例進(jìn)行調(diào)度，調(diào)度結(jié)果如圖1 所示。

圖1 BI-Wrap 調(diào)度算法實(shí)例Fig.1 Examples of the BI-Wrap schedule algorithm

如圖1 所示，采用BI-Wrap 算法進(jìn)行任務(wù)調(diào)度可保證在第1 個時間片內(nèi)分配的任務(wù)工作量都能在時間片截止之前完成，且所有任務(wù)在調(diào)度過程中都滿足非并行執(zhí)行性。

3.6 BI-Wrap 算法的時間復(fù)雜度

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

4 仿真試驗(yàn)及結(jié)果分析

4.1 仿真實(shí)驗(yàn)

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

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

首先測試得到3 種算法各自滿足系統(tǒng)約束的可行任務(wù)調(diào)度方案數(shù)見表1。

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

由實(shí)驗(yàn)結(jié)果可知，EB-Split 算法不損失Hetero-Split 算法求得的可行方案數(shù)，且兩者均優(yōu)于SA 算法。然后對比EB-Split 算法（使用BI-Wrap 算法進(jìn)行調(diào)度）與Hetero-Split 算法（正常調(diào)度）的平均系統(tǒng)能耗（分別用E1_avg 和E2_avg 表示），每次測試得到的系統(tǒng)能耗按式（11）計(jì)算而得。并計(jì)算EB-Split算法相對于Hetero-Split 算法的能耗降低百分比R=（E1_avg-E2_avg）/E1_avg。實(shí)驗(yàn)結(jié)果如表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

由實(shí)驗(yàn)結(jié)果可知，EB-Split 算法相較于Hetero-Split 算法在系統(tǒng)總能耗方面約降低23%～24%。

4.2 仿真結(jié)果分析

由實(shí)驗(yàn)結(jié)果可知，EB-Split 算法與Hetero-Split算法在尋求可行性方案上性能相當(dāng)且優(yōu)于SA 算法。Hetero-Split 算法已被證明為可行方案數(shù)最優(yōu)的［10］，故本文所設(shè)計(jì)的EB-Split 算法也滿足可行任一方案的最優(yōu)性。此外，在能耗方面，EB-Split 算法相較于Hetero-Split 算法在系統(tǒng)總能耗方面有大幅度降低，降低比率約為23%～24%。

5 結(jié)束語

異構(gòu)多核處理器上實(shí)時任務(wù)調(diào)度算法的設(shè)計(jì)向來是難點(diǎn)問題，尤其在航天探測等對系統(tǒng)各方面性能指標(biāo)要求都比較高的尖端領(lǐng)域。本文設(shè)計(jì)的基于全遷移的、加入能耗約束的實(shí)時任務(wù)調(diào)度算法，在保證系統(tǒng)實(shí)時性的條件下對能耗進(jìn)行了優(yōu)化，在總體性能方面優(yōu)于目前的較出色的SA 算法和Hetero-Split 算法。

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