異構多核調度算法研究綜述

晉高成，李丕丁

（上海理工大學醫療器械與食品學院，上海 200093）

0 引言

隨著網絡和通信技術的飛速發展，各式各樣的電子設備已廣泛應用于人們的日常生活、工作及生產等方面。近年來，機器學習、人工智能、無人駕駛等研究不斷深入，使得人們對CPU 計算速度的要求不斷提升［1］。然而，單核處理器一般通過提高處理器的主頻以提升處理器運算速度，該方法導致處理器功耗不斷提升，進而導致處理器工作溫度相應升高［2］。在需求和傳統處理器性能矛盾日益尖銳的情況下，多核處理器應運而生［3］。在主頻不變的前提下，雙核處理器的運行速度在理論上是單核處理器的1 倍，這意味著在相同時間內，雙核處理器可以做單核處理器兩倍的計算量，極大增加了處理器運行速率。并且，在單核處理器和雙核處理器達到相同性能時，雙核處理器的主頻甚至比單核處理的功耗低一半以上。多核處理器在性能和功耗上都比單核處理器表現更好，因此，越來越多的研究集中在多核處理器上［4］。

多核處理器又分為異構多核處理器和同構多核處理器。在同構處理器中，所有處理器核結構一致、功能相同、地位均等，相同程序在各處理器核上單獨運行所用的時間都相等［5］。正是由于以上特點，同構多核處理器在運行應用程序時并不能發揮最佳性能。每個處理器核的處理性能都相同，并不能為不同計算要求的應用程序提供更快的計算速度。異構多核處理器由多個不同類型的處理器核心構成，每個核心結構不同、功能也不同，針對某類運算具有較快處理速度，且每個核心都具有其擅長的功能［6］。如某個核心擅長浮點計算，另一個核心擅長任務切換。當處理某個含有多種計算要求的應用程序時，異構多核處理器往往比同構處理器表現得更好。盡管異構多核處理器比同構多核處理器在很多方面都表現得更好，但是異構多核處理器核心在結構和功能上都不相同，給硬件和軟件設計帶來了更多挑戰。目前，針對異構多核處理器的硬件和軟件相關研究較多，高效的調度算法是研究重點，它能及時將任務分配到特定的處理器核心上，體現出異構多核處理器的性能優勢。本文主要介紹基于異構多核的任務調度算法，與已有調度算法進行對比，并分析優缺點。

1 異構多核任務調度研究現狀

1.1 國外現狀

靜態啟發式表調度算法HEFT（Heterogeneous Earliest Finish Time）與CPOP（Critical Path on a Processor）算法是由Topcuoglu 等［7］提出的兩種異構環境下的多核任務調度算法。其中，HEFT 算法是針對異構多核數量有限情況下的任務調度算法，該算法分為兩個階段，分別為任務優先級排序和任務分配階段。在第1 階段，對于所有任務優先級，主要根據任務的向上排序進行計算；在第2 階段，調度器會根據在第1 階段計算的優先級，按照非遞增順序為各任務選擇合適的處理器核，在該階段還會采取區間插入技術，以減少任務間的通信時間。相比于HEFT 算法，CPOP算法在優先級計算上采取了不同的算法，它將任務的向上排序值和向下排序值作為任務優先級，計算出優先級后再將優先級最高的任務到出口節點的路徑作為整個任務的關鍵路徑。在任務分配階段，CPOP 會將關鍵路徑上的任務映射到同一處理器核上，剩下的節點按照最早完成時間進行映射。

在考慮減少任務調度長度的同時，也需關注異構處理器的能耗問題。Maurya 等［8］提出一種基于能耗感知的異構多核，該算法主要是以較少的高優先級任務通信時間降低總任務調度能耗。此外，有一種結合動態電壓調節技術和關鍵路徑的調度算法，不僅可減少調度長度，還能降低能耗，由Baskiyar 等［9］提出。也有較多在HEFT 算法基礎上的改進算法，如Lookahead 算法［10］。

隨著對智能調度算法研究的不斷深入，研究者開始將目光聚焦于遺傳算法［11-13］、蟻群算法［14-15］、模擬退火算法［16-17］等。

1.2 國內現狀

國內對于異構多核任務調度算法的研究要晚于國外，但也取得一系列成果。譚文安等［18］提出一種帶極值擾動的相關性粒子群優化算法EDCPSO（Extremum Disturbed Correlative Particle Swarm Optimization）；石 威 等［19］結 合MCP 算法和EFT 算法，提出一種動態的表調度算法。該算法不僅考慮到關鍵路徑節點，也考慮了非關鍵節點，對Makesapn 影響最大的可運行任務賦予最高優先級，極大減少異構多核上的任務調度長度，提升異構多核處理器性能；徐遠超等［20］實現了一種可在Linux 中運行的能進行感知的異構多核調度算法。該算法在保證各處理器利用效率達到動態平衡的基礎上，減少其它處理器核心空閑時間，且算法時間復雜度低，在負載均衡時能夠進行感知。

2 3 種異構多核任務調度算法

2.1 ICPOP 算法

傳統的CPOP 算法雖然在一定程度上減少了任務調度時間，但依然存在許多不足。CPOP 算法首先根據任務優先級形成任務列表（基于異構多核的混合式任務調度算法研究），然后將任務分配到處理器核上。但是優先權僅僅分配了關鍵任務，任務之間的依賴和約束關系并沒有被充分考慮進去。在這種情況下，如果關鍵任務的父任務并沒有及時被分配運行，則關鍵任務的運行時間將被延后，這樣會對任務的總完成時間產生不利影響。并且，CPOP 算法會將所有關鍵任務分配到同一個處理器核，雖然該方法可以減少這些關鍵任務之間的通信開銷，并且可以讓這些任務具有最早完成時間，但是該方法會造成不同處理器之間負載的不均衡，導致許多處理器核在某個核心過于忙碌時處于空閑狀態，使得處理器核心利用不充分。針對以上不足，本文提出一種基于CPOP 的改進算法ICPOP（Im?provedCritical Path on a Processor）。

ICPOP 算法在整體上與CPOP 算法一樣，總共分為兩個階段：任務優先級計算階段和處理器核分配階段。

Fig.1 Priority calculation process圖1 優先級計算流程

任務優先級計算階段：ICPOP 算法的優先級計算流程如圖1 所示。在該階段之前，要先將DAG（Directed Acy?clic Graph）標準化。一個標準的DAG 僅僅包含一個入口任務和一個出口任務，入口任務是父任務集合為空的節點，出口任務是子任務集合為空的節點。為了構建一個標準的DAG，就需要保證該DAG 中只含有一個入口任務和一個出口任務。因此，要使原DAG 中所有父任務集合為空的點添加一個父任務集合為空的節點，并讓它成為之前父任務集合為空的節點的父節點。同理，對于所有子任務集合為空的節點，添加一個子任務集合為空的節點，并讓其成為上述節點的子節點，這樣便可以構建一個標準的DAG。

對于異構多核處理器，出口任務完成時間就是整個任務調度完成時間。計算任務優先級時，需將最高優先級賦予擁有最長路徑的關鍵任務，這樣可盡量保證完成時間最短。對于非關鍵任務，出口任務的父任務及其父任務的完成時間影響出口任務開始執行時間，故若某任務到出口任務的開銷（計算開銷及通信開銷）越大，則該任務越需要提前執行，因此賦予該任務較高的優先級，以此縮短整個SAG 完成時間。然而，同一任務在不同處理器核心上計算開銷不同，計算差異較大的任務分配較高優先權，以提升其獲得開銷最小處理器核的概率。綜上所述，在計算任務優先級時，需計算出每個任務到出口任務的總開銷ε(Ni)以及當前任務在不同處理器核上的計算開銷差異σ(Ni)，計算方法如式（1）所示。

從當前任務Ni到出口任務的總開銷ε(Ni)計算公式如式（2）所示。其中,child(Ni)表示任務Ni的后繼任務集合。

由于異構多核處理器各處理器核之間的計算速率各不相同，在計算優先級時要計算任務在不同處理器核上的開銷差異，計算開銷差異用σ(Ni)表示，σ(Ni)的計算公式如式（3）所示。

在式（3）中，P 表示處理器核的數目，k 表示處理器序號。計算完任務優先級后再根據計算出的優先級按照非遞增順序對任務進行排序，以構建任務調度列表。

處理器核分配階段：經歷上述階段后，得到已經排序好的調度列表，再利用區間插入技術對任務進行分配。不斷選取任務調度列表中優先級最高的任務，然后將其放置在開始時間最接近的處理器核上執行，重復上述操作，直到調度列表為空。處理器核分配流程如圖2 所示。在上述方法中，使用區間插入技術，該技術指將任務插入到同一處理器核心上兩個任務之間的空閑時間space，但是不能破壞任務之間的前驅后繼關系，必須滿足式（4）的任務才可采用區間插入技術。

在式（4）中，st（space）表示空閑區間開始時間，space_length 表示空閑區間大小，用st（Ni，pk）表示任務Ni在處理器核pk上的開始執行時間，WO(Ni,pk)表示任務Ni在處理器核pk上的所有開銷。

為了比較ICPOP 算法和CPOP 算法性能，設置不同的任務節點數以及不同的異構多核處理器，分別采用ICPOP算法和CPOP 算法進行對比實驗，比較在不同DAG 下的完成時間長短，結果如圖3 所示。

從圖3 可以看出，ICPOP 算法在大多數情況下比CPOP 算法減少了任務調度完成時間，ICPOP 算法獲得的任務調度長度更短。同時，在任務節點為50，核心數為2時，CPOP 算法比ICPOP 算法更加高效。

Fig.2 Processor core allocation process圖2 處理器核分配流程

Fig.3 Completion time of ICPOP algorithm and CPOP algorithm圖3 ICPOP 算法與CPOP 算法完成時間

2.2 智能蟻群調度算法

隨著并行執行模型的發展和完善，文獻［6］提出Code?let 模型，該模型是一種事件驅動的、細粒度的、混合控制流的并行執行模型。

該算法針對異構多核的Codelet 計算環境，結合HEFT算法和蟻群算法，提出一種智能蟻群調度策略（Samrt Ant Colony Task Scheduling）。該算法執行流程如圖4 所示。

如圖4 所示，該算法首先輸入CDG、數據傳輸時間開銷C 以及人物執行開銷ETC，然后根據HEFT 算法計算每個節點的靜態優先級Rank，螞蟻從Codelet 節點開始出發，依照動態狀態轉移規則選擇下一個調度的Codelet 節點，再將該節點分配給最早時間空閑的處理器核，開始執行該節點，跟新動態因子，重復上述步驟，直到調度達到最大迭代次數。該算法的參數和初始化值如表1 所示。

Fig.4 Scheduling strategy of ant colony optimization圖4 智能蟻群調度策略算法流程

Table 1 Parameters and initialization values表1 參數與初始化值

該算法中每個節點的靜態優先級可以采用ICPOP 算法中的優先級計算方法，計算每個節點的靜態優先級。該算法中螞蟻通過狀態轉移規則決定下一個COdelet 任務，該動態規則由式（5）計算得出。

其中，τ（i，w）為（i，w）邊上的信息素強度，該值越大，該節點被選擇的概率越大。該算法通過調整動態因子q0控制收斂速度，q0越小，蟻群選擇的多樣性越好。q0由式（6）計算得出。

在構造解的過程中，每個螞蟻都會對自己選擇的邊更新局部信息素。該做法的目的在于防止完成一次迭代后，其它螞蟻會得到同樣的解。因此，需不斷更新對應的信息素τ（t，n），更新公式如式（7）所示。

該算法運行結果如圖5 所示。其中，Robot 擁有88 個節點，Sparse 有96 個節點，Fpppp 有334 個節點。Static 為靜態調度策略，Dynamic 為原生動態導讀策略，SACTS 為智能蟻群調度策略。可以看出，在解決大規模任務調度問題時，智能蟻群調度策略比原生動態調度和靜態調度策略擁有更高效率，并縮短了任務執行時間。

Fig.5 The result of ant colony optimization圖5 智能蟻群算法運行結果

2.3 一種啟發式綜合任務調度算法

IHTSGMP（Integrated Heuristic Task Scheduling Algo?rithm for Heterogeneous Multicore Processer）算法以表調度算法為基礎，首先構建任務調度優先級，根據優先級構造調度列表。在調度過程中采取任務復制技術，再將各任務節點分配到處理器核上執行，提升處理器利用效率，可分為優先級計算階段和任務分配階段。

優先級計算階段：在該階段開始時，需根據現有任務節點，構建一個DAG，表示任務執行和依賴關系。計算優先級的方法大致類似，都是根據關鍵路徑法，首先需找到關鍵路徑節點最高優先級。對于其它節點，IHTSHMP 算法的優先級由式（8）計算得出。

其中，weighti表示節點i的優先級權值，ncp表示當前任務節點的直接后繼關鍵路徑節點。cp_value(ni)的定義如式（9）所示。

任務分配階段：IHTSHMP 算法采用任務復制以及區間插入方法。首先選擇最早完成任務的處理器內核，然后根據第一階段計算出的優先級，選擇優先級最好的節點，再分別計算該節點在被選擇的核心上采用和不采用任務復制技術的最早完成時間，選擇最早完成時間最短的方案。任務復制流程如圖6 所示。

Fig.6 The process of task copy圖6 任務復制流程

其中，est(ni,pu)和est2(ni,pu)分別為不采用任務復制和采用任務復制的最早完成時間。在任務復制策略基礎上，采用在ICPOP 算法中敘述的區間插入技術，進一步提升處理器利用效率。

該算法運行效果如圖7 和圖8 所示。該實驗對比了前驅復制算法CPFD（Critical Path Fast Duplication）［21］和選擇性任務復制的表調度算法STDH（Selected Task Duplica?tion for Heterogenous System）［22］。可以看出，相比于CPFD算法和STDH 算法，IHTSHMP 算法在不同任務數下都保持著較高調度效率。

Fig.7 Comparison of average speedups of different tasks圖7 不同任務數下的平均加速比對比

Fig.8 Comparison of average accelerations with different CCRs圖8 不同CCR 下的平均加速比對比

3 調度算法總結

ICPOP 算法在優先級計算和處理器核分配上對CPOP算法作出改進。在任務優先級計算時，不僅考慮了當前任務到出口任務的開銷，還計算了此任務在不同處理器核上的計算開銷差值，相對于CPOP 算法，保證差值大的任務節點可以被優先調度，縮短任務調度時間；在處理器核分配階段，采用區間插入技術，減少處理器在任務和任務之間的縫隙，提升處理器利用效率，從而縮短任務調度長度。

智能蟻群算法結合靜態啟發式調度算法HEFT 和改進蟻群算法，在優先級計算階段采用與HEFT 算法相同的優先級計算方法，隨后采用蟻群算法，改進動態狀態轉移規則，更加有效地選取下個待運行節點。

IHTSHMP 算法是一種啟發式綜合任務調度算法。該算法綜合任務復制算法和表調度算法。計算優先級時考慮任務拓撲圖結構，進一步優化優先級計算，提升調度效率；任務分配階段采用任務復制技術，比較復制和不復制對整體的影響，然后選擇是否采取復制，該方法減少了依賴任務通信延遲，充分發揮了異構處理器的優勢。

4 結語

異構多核任務調度算法的關鍵在于如何合理調度，使得所有任務完成所用時間最短。該問題是一個NP（Nondeterministic Polynomial Complete）問題，目前還沒有一種能確保每次都可獲得最優解的算法，只能是不斷地逼近最優解。異構多核任務調度算法主要分為確定性算法和非確定性算法，本文提到的任務復制算法和表調度算法為確定性調度算法，蟻群調度算法為非確定性調度算法。確定性算法在任務數量少時更具優勢，非確定性算法在處理大規模任務時有更早的完成時間。目前，對于確定性任務調度算法中的列表調度算法使用最為廣泛，但是在處理大規模任務量時還是會采取蟻群算法、退火算法等非確定性算法。從上述算法中可以看出，未來發展趨勢是將非確定性算法和確定性算法相結合，實現優勢互補。