基于異構多核機群系統的任務調度算法研究

李霞

摘 要：針對多核機器構成的異構機群系統，充分利用多核機器并行性及處理核心共享二級緩存的特點，提出基于DAG圖的相關任務調度算法，該算法通過三個階段完成任務的分配及調度過程，通過對相應任務的復制減少各處理節點之間的通信開銷，提升任務調度的效率和減少任務調度的長度。

【關鍵詞】任務調度 DAG 多核 機群

近年來，單芯片多核心處理器（Chip Multi-core Processors，CMP）體系結構在計算機硬件領域已經處于主導地位，在理論上通過增加多個處理核心以減少單個處理芯片由于主頻過高帶來的散熱問題，然而針對多核機器構成的機群系統上的任務調度算法尚未成熟，如果直接把傳統的任務調度的算法直接移植到此類系統中，則不能很好的發揮多核機器的多個處理核心可以并行執行的優勢，因此，多核機器的任務調度作為影響系統性能的重要因素成為近些年來系統結構方向的熱點研究問題之一。

通過實踐的檢驗，人們發現目前最有發展前景的任務調度技術是先用啟發式調度算法對任務進行分組，分組之后再采用遺傳算法對任務單獨進行調度。基于這種思想，本文提出了基于異構多核機群系統的相關任務調度算法。

任務調度是一類非常重要的組合優化問題，除了一些假設的簡單的調度模型外，大多數相關任務的調度是一個NP完全問題。目前很多研究學者提出了多種算法，包括各種啟發式算法、遺傳算法及其混合算法等，而啟發式算法則目前認為是尋求NP完全問題的接近最優解的一種可行的方法。文獻[3]中提出了一個基于迭代的啟發式算法，用于對多核處理機系統中的各個處理器進行任務的分配，該算法利用多核處理器的處理核心之間通過共享二級緩存或通過高速信道的內連接進行通信，因此子任務之間的通信開銷可以忽略不計，因而將通信比較頻繁或通信代價比較大的子任務分配到同一個多核處理機節點上執行，這樣就大大的利用了多核機器的優點，同時也減少了任務在執行的過程中由于相關任務被分配到了不同的處理機節點而帶來的通信開銷。但是該算法只分析了多核系統上的任務分配問題，而未考慮任務分配之后如何在多核處理機節點內的調度。

本文基于文獻[2]提出的思想，并結合多核處理機本身具備的并行性能，首先將任務分配到合適的多核處理機節點，然后根據多核機器多個核心可以并行執行的特點，在單個節點內再次進行任務調度，從而將任務分配到具體的處理核心進行處理。

1 任務調度模型

假設機群系統由N個多核處理機節點（P1，P2……PN）構成，且Pi處理節點有Ci個處理核。將實際應用的任務分解成M個子任務，且假設預先已經知道每個子任務運行所需要的時間，而子任務之間的約束關系我們可以通過一個有向無環圖（directed acyclic graph DAG）來表示。并且將DAG圖定義為一個四元組：G={T，E，C，S}，其中各個參數的含義如下所述：

T={Ti|i=1，2…，M}是頂點的集合，每個頂點用來表示一個子任務。

E={Eij|Ti，Tj∈T}是有向邊的集合，邊Eij表示有向邊Ti->Tj，即Ti和Tj之間存在約束關系，任務Ti一定要在任務Tj前執行。

C={C1，C2，…，CM}是一個M維的向量，其中Ci>0表示任務Ti運行時所花費的時間。

S是表示通信矩陣，對于任務圖中任意邊（Ti，Tj）∈E，S（Ti，Tj）表示子任務Ti和Tj之間的通信開銷。如果兩個任務被分配到同一個處理機節點上，則他們之間的通信時間可以忽略，用0表示。

如圖1是包含有十一個子任務的DAG圖，其中用T1、T2……、T11表示分解后的子任務，節點之間的有向邊則表示子任務和子任務之間的約束關系，有向邊上的數字則表示該有向邊的通信開銷，節點中下部的數字表示該子任務執行所需的時間。

基于DAG任務圖調度時追求的目標有很多，本文考慮的目標是將M個子任務調度到N個處理機節點上，以期獲得最短的調度長度即總的處理時間最少。

2 算法的思想

2.1 任務分配

為了達到最短的任務調度長度，結合多核機器的性能：同一個處理器上的多個處理核心共享二級緩存，因此盡量將任務之間通信時間較長的子任務分配到同一個節點上執行，并且根據每個多核處理機節點處理能力及所分配到的子任務總的執行時長來決定子各個多核處理機節點所分配的子任務的數量。經過任務分配之后的DAG圖如圖2所示，原始的DAG圖被分成了四個子任務群。

2.2 任務復制

在多核處理機系統中，單個多核機器節點內的多個處理核是共享二級緩存的，因此使相關聯的任務盡可能的在同一個處理機節點上完成，這樣就有效的降低了相關任務被分配到不同處理機節點而需要花費的通信時間，為此要進行任務的復制。任務復制主要是對分配到不同的處理機節點上的任務進行復制，通過對具有前驅后繼關系的任務進行復制，將關聯的任務之一從一個處理機節點復制到另一個處理機節點上去，即在不同的處理機節點上都執行該任務，以通過增加任務的計算時間來減少任務之間的通信花費。在選擇復制的任務時，把所有子任務的前驅任務復制到當前處理機節點上，而對于新復制過來的子任務亦是如此，將其所有的前驅任務復制過來，直到入口節點為止。

按照如此復制的原則，四個子任務群對應的DAG圖經過復制后的結果如圖3所示。

2.3 任務調度

經過任務的分配及任務的復制操作之后，每個多核處理機節點上的子任務群都是互不關聯的，因此一個相關任務的調度問題就轉換成了多個可以并行執行的子任務群，而這些子任務群分布在不同的處理機節點上，且它們的執行不相互依賴，在執行的過程中，處理機節點之間不需要進行信息的通信。這樣，對每個處理機上的子DAG圖就可以采用獨立的調度算法進行任務調度，本文采用文獻[4]所述的遺傳算法進行調度。

3 算法的實現

本文的算法由三部分組成：第一部分根據各個任務之間的關聯特性將各個子任務分配給多核處理機節點；第二輪操作將處在不同處理機節點上的相關任務進行復制，使最原始的DAG圖變成相互獨立的多個子任務群。第三輪，將各個多核處理機節點上的子任務群再次進行調度，調度到各個處理核心上處理。

第一部分操作由迭代組成，每次選擇DAG圖中C（Ti，Tj）值最大的兩個子任務節點，即子任務之間通信開銷最大的那對節點，將選中的兩個子任務節點歸到同一個子DAG圖中，并且它們之間的通信開銷變為0，為了后面進行分配時使各個處理機節點負載均衡，同時要統計這兩個被選中任務的執行時間，重復這種歸集操作，直到所有的子任務節點都有歸屬為止。

第二部分操作進行相關任務的復制，對于具有前驅后繼關系而又分布在不同處理機節點上的任務進行前驅節點的復制工作，而對于新復制過來的節點如果其前驅節點不在當前處理機上時，則仍要進行前驅的復制，直到入口節點為止，并且在進行任務復制的同時疊加復制過來的任務的執行時間。經過該輪的操作，所有的子DAG圖都是互相獨立的，子DAG圖中的任務執行都不依賴于其他的處理機節點，即各個處理機節點可以并行執行。而對各個獨立的子DAG圖進行分配的時候，根據各個子任務圖中任務執行時間的多少來進行多核處理機節點的選擇：即子DAG圖中任務執行時間總和長的分配到處理能力強的處理機節點上。

第三部分操作對各個處理機節點上的子DAG圖分別使用遺傳算法將各個子任務分配給多核處理機節點的內核進行處理。本文采用文獻[4]所述的遺傳算法進行節點內任務的調度，步驟在此省略。

4 結束語

對于多核異構機群系統，本文充分利用多核機器多個處理核心共享二級緩存的特性，針對基于DAG圖的相關任務的調度問題，采用三個階段分別進行任務的分配、復制以及調度，在任務的分配階段利用多核機器共享二級緩存的特性減少相關任務之間的通信開銷；任務的復制階段使相關的任務變成可以并行執行的多個子任務群，然后根據各個處理機節點的處理能力的不同進行子任務群的分配；而在多核處理機節點內采用現有的遺傳算法對各個子任務群進行調度，從而分配到具體的處理核心進行處理。

參考文獻

[1]Laurea De Giusti，EmilioLuque，FrancoChichizola.AMTHA：An algorithm for automatically mapping tasks to processors in heterogeneous multiprocessor architectures[C]//World Congress.

[2]吳佳駿.多核多線程處理器上任務調度技術研究[D].北京：中國科學院，2006.

[3]LIU YI，ZHANGXIN，LIHE，etal.Allocatingtasksinmulti-core processorbasedparallelsystem[C].Proceedingsofthe2007IFIPInternationalConferenceonNetworkandParallelComputingWorkshops.WashingtonDC：IEEEComputerSociety，2007：748 -753.

[4]HOUESH，ANSARIN，RENH.Ageneticalgorithmformultiprocessorscheduling[J].IEEETransactionsonParallelandDistributed Systems，1994，5（2）：113-120.

作者單位

廣西財經學院防城港學院 廣西壯族自治區防城港市 538000