異構多核全局限制性可搶占并行任務可調度分析

韓美靈 孫施寧 鄧慶緒

1（南京郵電大學現代郵政學院 南京 210023）

2（東北大學計算機科學與工程學院 沈陽 110819）

隨著嵌入式技術的發展，云計算、邊緣計算等復雜計算場景對芯片的性能要求越來越高.為了滿足該應用需求，異構多核在現代計算機系統得到迅速發展.然而，向大規模異構平臺遷移非常困難.軟件層面的原因主要是大規模的、必要的程序并行導致軟件調度的復雜度，即使在同構平臺下這依然是大量學者致力研究的一個熱點問題.

本文首次針對有向無環圖（directed acyclic graph,DAG）并行任務模型在異構平臺上進行全局固定優先級限制性可搶占的可調度性分析，所提到的異構平臺由多個不同類型的處理器組成（每個類別的處理器個數大于等于1）.由于異構融合的體系結構，多種不同類型的處理器集成在同一硬件，且并行軟件中某些程序片段只能在特定的處理器執行.因此，DAG 任務的某些結點可以綁定到特定的一類處理器上執行.而綁定處理器的操作，在一些主流的并行處理程序和操作系統都有對應的指令，例如：在OpenMP中可以通過proc_bind 實現線程的綁定[1]；在OpenCL中，通過clCreatCommand 可以針對特定設備創建一組命令[2]；在CUDA 中，可以通過cudaSetDevise 實現指令到目標設備的綁定[3].而對任務的如此處理可以避免任務在不同速率的處理器上遷移，減少實現難度和不必要的遷移開銷.下文中，我們稱綁定處理器的DAG 任務為分類DAG 任務.

在經典的調度策略中，一般忽略了任務搶占和遷移的開銷.然而，可搶占調度中頻繁發生的搶占所造成的開銷往往比不可搶占調度高很多，需要高度重視.尤其在異構多核體系結構中，GPU 中執行的任務片段是不可搶占的，因此一些實時系統的任務存在不可搶占域（即任務執行的某個片段不允許被搶占）.因此，限制性可搶占的研究對于實時系統的任務執行是至關重要的.

關于分類DAG 任務集的調度問題，難點主要存在2 方面：1）DAG 任務內部不同結點的互相影響；2）不同DAG 任務結點間的互相影響.尤其是限制性可搶占導致優先級翻轉，即低優先級任務會對高優先級任務結點的執行造成阻塞.因此，分類DAG 的某個結點的執行會受到自身其他結點的干涉、高優先級任務的干涉以及低優先級任務的阻塞.其中，自身結點的干涉已經在早期工作[4]中解決.本文重點解決高優先級任務的干涉、低優先級任務的阻塞的分析問題以及分類DAG 的最差響應時間（worst case response time,WCRT）分析，主要創新點包括3 個層面：

1）由于分類導致DAG 任務的關鍵路徑（得到WCRT 的路徑）不確定[4]，從而增加高優先級任務干涉分析的難度.結合經典的同構DAG 理論和分類DAG的特點，本文提出了分類DAG 高優先級分析方法.

2）解決了分類DAG 限制性可搶占導致的優先級翻轉問題.本文將同構DAG 的低優先級任務分析方法和分類DAG 相結合，提出了分類DAG 的低優先級任務阻塞的分析方法.

3）采用文獻[4]的路徑抽象方法并結合高、低優先級任務的分析，提出了分類DAG 任務集的WCRT分析方法.由于高、低優先級任務干涉計算的引入，本文對文獻[4]路徑抽象規則進行了創新.

1 相關工作

在嵌入式實時系統中，某些任務的執行只能在規定的地方被搶占.考慮到完全可搶占和完全不可搶占的優缺點，限制性可搶占的研究非常重要.近年來關于這方面的研究也較突出.如：文獻[5]的工作針對多核全局最早截止期優先限制性可搶占任務做出了分析；文獻[6-7]對非并行任務在全局調度策略下進行了響應時間分析；文獻[8]針對多核并行任務的限制性可搶占問題進行了分析，并根據搶占策略的不同提出了對應的分析方法并進行了比較；文獻[9]針對DAG 的限制性可搶占問題進行了研究，特別是針對低優先級任務的阻塞在效率和精確度的不同上提出了不同的分析策略.然而，限制性可搶占的研究工作還未考慮到資源的限制性.隨著異構體系結構的發展，資源限制性是必須要考慮和解決的問題.

資源限制性問題的研究曾經非常熱門，也取得了一些研究成果，基于當時的條件這些成果考慮的任務模型相對簡單.例如文獻[10-13]考慮的問題是2 種處理器集合分配給2 個任務，并且一個處理器集合是另一個集合的子集等，相關研究總結在綜述類文獻[14-15].可以發現，現有研究的問題和本文提出的分類DAG 任務的可調度性問題存在差異.針對分類DAG 任務的可調度性研究，可查閱的文獻較少，Han 等人在文獻[4]中提出單個分類DAG 的響應時間分析，該文分析了單DAG 分類任務可調度性，并提出了基于路徑抽象的方法進行可調度性分析.基于此研究以及并行任務分析和響應時間分析的經典理論[16-18]，Han 等人提出了基于聯合策略的可調度性分析[19]和全局固定優先級可調度性分析[20].文獻[21]提出的工作和本文的任務模型接近，該工作是基于分解策略提出的點到點（即計算路徑中每個點的WCRT）的調度分析方法，然而該方法并未考慮資源限制的問題.就單個分類DAG 任務而言，文獻[4]進行了算法對比，對比實驗結果顯示文獻[21]算法比文獻[4]算法明顯消極.

本文的主要工作是基于文獻[4]的理論基礎，提出基于全局固定優先級的限制性可搶占調度策略的分類DAG 任務的可調度性分析方法.分類導致DAG任務的關鍵路徑不確定，從而增加高、低優先級任務的分析難度.本文將DAG 分析的理論（基于路徑的分析）和分類DAG 任務相結合，成功解決了該難題.最后，基于文獻[4]的路徑抽象算法，更新路徑抽象規則，進行任務集的可調度性判定.

2 任務模型

2.1 任務集模型的建立

本文對由N個分類DAG 任務組成的任務集G={G1,G2,…,GN}進行可調度性分析，該任務集執行的系統由不同種類的核組成.S是核類別的集合，對于每種類型s∈S具有Ms（Ms≥1）個核用于調度.分類DAG 任務Gi=(Vi,Ei,C,γi,Ti,Di)，該元組中各個符號的定義為：

1）Vi表示Gi所有結點的集合，結點∈Vi,1 ≤j≤ni，ni為Gi的結點數；

2）Ei表示Gi所有邊的集合，結點(u,v)∈Ei,v,u∈Vi；

3）C表示Gi每個結點最差執行時間（worst case execution time,WCET）的函數，表示結點的WCET；

4）γi表示Gi每個結點類型的集合，表示結點的類型；

5）Ti表示Gi相鄰2 個實例的最小釋放時間間隔；

6）Di表示Gi的相對截止期，即Gi在時間點ri釋放一個任務實例，必須在ri+Di內完成該任務實例的執行.

例1.異構DAG 并行任務模型如圖1 所示，任務執行在具有2 種類別的處理器平臺，白色圈表示類別1，灰色圈表示類別2，結點旁的數值表示任務的WCET.

2.2 任務調度策略

本文中任務采用全局固定優先級限制性可搶占策略進行調度.任務按照優先級順序排列，即如果i＜j，則Gi的優先級比Gj高.限制性可搶占是指任務的結點一旦開始執行，其執行不會被高優先級任務搶占.

本文將提出一種過量估計方法分析每個任務的WCRT 上界，從而保證任務執行的安全性.其中，任務Gi的WCRT上界表示為Ri.

Fig.1 Illustration of typed DAG taskG1圖 1 分類DAG 任務G1的示意圖

3 調度算法分析

本節將針對任務集G={G1,G2,…,GN}進行可調度性分析，并假設Gk是被分析任務，k=1,2,…,N.

3.1 整體分析

DAG 任務WCRT 上界分析方法多基于關鍵路徑.同構平臺下，最長路徑即為關鍵路徑[18].然而，這一結論已經不適用于分類DAG[4]，最長路徑分析方法得到的WCRT 上界并不安全，增大了分類DAG 的分析難度.分類DAG 任務進行可調度性分析需要解決2 個問題：1）如何確定關鍵路徑；2）已知關鍵路徑，如何進行響應時間分析.為了確保分析方法的安全可靠，解決問題1）最簡單的方法是枚舉所有路徑，后面會介紹如何解決枚舉問題.針對問題2），本文基于路徑進行解決.首先，假設Gk的關鍵路徑是 πk，πk=

路徑 πk的執行受到3 種不同類型的干擾：第1 種，任務內干涉Intra(πk)；第2 種，其他高優先級任務的干涉；第3 種，低優先級任務的阻塞.

由文獻[4]的結論可知，路徑 πk受到的任務內干涉定義為與 πk結點并行且實際干涉 πk上結點執行的同類結點工作量之和與對應的處理器個數的比值，即

其中ivs(πk,s)在文獻[4]中定義為路徑 πk實際受到的任務內干涉.

根據文獻[9]可知，路徑 πk受到的任務間干涉為路徑上所有類別的高優先級任務的工作量加上低優先級任務的阻塞量之和與處理器個數總和的比值，即

其中，Ws(πk)表示高優先級任務產生的工作量之和的上界，Bs(πk)表示低優先級任務產生的工作量之和的上界.根據式（1）（2），可以得到如下結論：

證明.根據文獻[9，18]，引理可證. 證畢.

關鍵問題是如何計算Inter(πk).Inter(πk)包括2 個部分，即高優先級任務的干涉和低優先級任務的阻塞，下面將對這2 個部分產生的工作量上界進行分析.

3.2 高優先級干涉量分析

對于高優先級任務的干涉量計算，首先要確定在某個時間窗口里高優先級任務能夠產生的每個類別的工作量上界.在時間長度為x的窗口內，高優先級任務Gi產生的工作量上界表示為Wi(x)，產生類別為s的 工作量上界表示為計算過程詳見引理2.

引理2.在長度為x的時間窗口內，高優先級任務Gi能夠產生的類別為s的 工作量上界為

證明.引理2 能夠得到證明基于2 個層面的假設：

1）當carry-in 實例（該實例在窗口之前釋放，在窗口內完成）和carry-out 實例（該實例在窗口內釋放，截止期在窗口外）的s類 別的工作量平均分布在所有s類核上時（如圖2 所示），可以得到s類別的工作量上界.

2）假設carry-out 實例全部帶入，可以得到高優先級任務的工作量上界，該假設基于假設1）.

首先，證明假設1）的正確性.該假設忽略任務的內部結構，單純考慮長度為x的時間窗口內能夠產生的工作量的最大情況.采用反證法，如果vols(Gi)的工作量分布在個 核且＜Ms，根據式（4），該設想顯然不能增加窗口內的工作量，因此假設1）成立.

假設2）的證明依然采用反證法，假設carry-out帶入的減少即窗口向左滑動ε=δ×vols(Gi)/Ms的長度，0 ＜δ ＜1.窗口向左滑動，會導致左邊carry-in 實例長度的增加，即carry-in 實例在窗口內增加 ε的長度.而carry-in 和carry-out 實例s類的工作量是均勻分布在所有核上，所以最終的工作量總和不會發生改變，即假設2）成立.接下來證明式（4）計算的正確性.

Fig.2 worst-case scenario to maximum workload in x ofGi圖 2 G i在x 窗口內產生最大工作量的最壞情況

圖2 中，x的時間窗口的組成包括：長度為vols(Gi)/Ms的carry-out 實例、body 實例（釋放和截止期都在窗口內的實例）個數的周期長度以及carry-in實例長度.而body 實例數量的上界為

x窗口還有carry-in 的組 成部分.而carry-in 的長度可由 α計算.根據圖2，carry-in 長度不大于vols(Gi)/Ms.

綜上，引理2 得證. 證畢.

根據引理2，在長度為x的時間窗口內，所有高優先級任務Gi產生的s類別的工作量上界為

3.3 低優先級阻塞分析

限制性可搶占導致優先級翻轉的問題，即低優先級任務會阻塞高優先級任務的執行.當路徑 πk上的某個結點可以執行時，即所有前繼結點完成執行，而處理器被低優先級任務占用，從而造成對該結點的阻塞.被低優先級任務占用的處理器個數為1～Ms（少于Ms個是因為處理器被高優先級任務或者前繼結點占用），最壞情況要結合的情況進行討論.

如果i=1即該結點是源結點，最多有Ms個低優先級任務的結點阻塞其執行.如果1 ＜i≤ni，分成2 種情況進行討論：

Fig.4 Scenario for ≠s圖 4 ≠s時的情況

綜上，被分析路徑上的某個結點阻塞量的計算總結見引理3.

證明.根據式（6）（7），引理3 得證.

證畢.

4 分析過程

基于文獻[4]提出的路徑抽象算法，進行響應時間分析.

由于其他任務干涉的增加，導致文獻[4]算法中元組替換的規則不再適用，需要增加新的替換規則滿足增加的其他任務干涉的分析，具體見引理4.

證明.替換規則2）和3）已經在文獻[4]中證明.本文只需證明規則1）的必要性.采用反證法，如果規則1）不成立，則以下2 種情況之一成立：

最終，本文提出的分析方法綜合為算法1，來判定任務集的可調度性.

算法1.任務集可調度性分析算法.

算法1 針對任務集中的每個任務進行路徑抽象，計算其WCRT 上界.算法1 的行③～?是針對每個任務Gk，從源結點開始搜索至結束結點，針對每個結點基于其前繼結點的元組進行該結點的元組計算，計算出新的元組進行元組合并和替換操作，直至結束結點.結束結點所有元組中最大的R即為Gk的WCRT上界（行?～?）.如果Rk＞Dk說明該任務不可調度，直接結束計算返回整個任務集不可被調度；否則，繼續分析下一個任務.如果最后1 個任務被分析完，且滿足截止期的要求則整個任務集可被調度（行?～?）.

基于文獻[4]，算法1 對DAG 任務每個結點的響應時間分析時增加了其他任務的干涉計算.在算法1過程中增加了新的合并和替換規則以保證最終計算的安全性.

定理1.任務集G是否可以被調度，可以由算法1 來判定.

證明.綜合理論和算法1 的偽代碼分析，定理1得證. 證畢.

5 實 驗

本文采用仿真實驗，分別從算法的準確性和效率層面進行算法的驗證.對任務集的可調度性產生影響的參數包括：任務集利用率、處理器個數、任務集內任務個數、結點個數、類別數以及每個任務的并行度.首先，對這些參數設置一組默認參數，然后基于該默認參數進行對應參數實驗變化的驗證實驗.異構平臺相關的實驗數據基于OpenAMP[22]項目支持的硬件平臺作為基礎數據，對類別數和每種類別核數量的范圍進行適當地增大，觀察這2 組參數對算法性能的影響.而任務集的默認參數則結合實際情況和其他DAG 任務集的相關參數進行設置.默認參數設置為：

1）異構平臺上核類別的數量在[2,15]隨機生成，每個類別核的數量Ms在[2,10]隨機生成；每個類別s的利用率在[1,Ms/3]的范圍內隨機生成；

2）任務集中，任務的數量在[2,20]的范圍內隨機生成；

3）用UUnifast 方法[23]為每個任務的s類別分配利用率；

4）對于每一個任務，周期在[100,1 000]之內隨機生成，默認每個任務的相對截止期等于周期；

5）每次隨機選取1 000 個任務集分析平均性能.

對單個任務的參數進行設置，主要依據文獻[4]，具體參數設置為：

1）每個DAG 任務的任務結構采用文獻[24]提出的方法生成.任務的結點數在[15,30]的范圍內隨機生成；任意2 個結點之間是否生成邊，需要隨機選定；假設選定為增加該邊，需進一步判定，即增加該邊后并行度Pr的值滿足要求，則增加邊，否則不增加；Pr值在[0,1]之間隨機選擇，注意Pr值越大說明并行度越低，Pr值為1 則所有結點為串行.

2）采用UUnifast 方法將已分配的利用率分配給每個結點，注意利用率是按類別分配的，結點的WCET 值等于分配的利用率與周期的乘積.

算法的正確性采用接受率進行驗證，接受率定義為可以被調度的任務集占所有被測試的任務集的比率.圖5（a）～（f）展示的是各個參數下的接受率.其中，圖5（a）～（d）是整個任務集參數對接受率的影響，圖5（e）～（f）是單個任務中重要參數對接受率的影響.圖5（a）中，因為利用率增大，而每個類別的處理器個數不變，使得接受率逐漸下降；圖5（b）中，由于利用率固定，每個類別的處理器個數增加，從而導致接受率逐漸提升；圖5（c）表明，其他參數不變的情況下，任務集中任務個數越多任務越難以調度；圖5（d）表明，類別越多，相同利用率下分給每個類別的利用率就會減少，而類別的增加也會導致處理器個數增加，從而使得接受率提升；圖5（e）表明，單個任務內部結點個數對接受率的影響不顯著；圖5（f）表明，單個任務內部并行度越高（Pr值越低）接受率越高，這是因為并行度大則并行執行的可能性增大，從而提高接受率.綜上分析，實驗數據符合各參數的性質和對實際任務可調度性的影響.

Fig.5 Acceptance ratio of tasks under different parameters圖 5 各種參數下的任務接受率

圖6（a）～（f）是對應接受率實驗的各個參數下的效率實驗.其中，效率趨勢中的每個點是所有1 000 個參加測試的任務集的平均分析時間.注意，該時間隨著分析設備硬件性能的不同會有所不同，其變化趨勢可以表明與相關參數的關聯性.同樣地，圖6（a）～（d）為與任務集相關的參數，而圖6（e）（f）是和單個任務相關的參數.圖6（a）（b）（d）中時間效率的變化趨勢分別和圖5（a）（b）（d）類似，這是因為接受率低，說明不可調度的任務集增多，在第1 次出現不可調度任務時停止對任務集的分析從而出現平均分析時間下降的現象.圖6（c）的實驗結果為時間效率先升高后降低.圖6（c）升高趨勢的原因是當任務集接受率差不多時，任務集中任務個數增多，導致平均分析時間變長；圖6（c）降低趨勢的原因是由于接受率降低太多.圖6（e）中曲線變化表明，時間效率對任務內的結點個數是敏感的，當任務內的結點數增多時，時間效率呈增長趨勢，且增長速度非常大.圖6（f）中時間效率變化趨勢類似于圖6（c），即先增后降，當任務集都可調度時任務分析時間隨并行度下降而升高，當并行度降低到一定程度時接受率下降過多，導致任務集大量開始不可調度，從而導致平均分析時間下降.

Fig.6 Efficiency under different parameters圖 6 各種參數下的效率

實驗結果表明，本文提出的算法具有很好的接受率且任務的平均分析時間在嵌入式實時系統離線分析時間的可接受范圍內，各個參數實驗數據均符合實驗預期.

6 結 論

本文針對異構平臺上任務執行進行資源限制即規定任務只能執行在某一類處理器上這一特殊模型，進行了基于全局固定優先級限制性可搶占調度策略的可調度性分析.首先，提出了整體的分析思路；然后，針對高優先級任務的干涉和低優先級任務的阻塞進行了分析；最后，結合最新的異構模型提出了一個整體的分析方法.實驗結果表明，本文提出的算法性能良好，能夠在有效時間內完成任務的分析，且任務的可調度性和各個參數的關系符合實驗預期.

作者貢獻聲明：韓美靈提出了算法思路并撰寫論文；孫施寧負責實現算法并設計了相關實驗方案；鄧慶緒提出研究思路并指導修改論文.