李霞

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

【關鍵詞】任務調(diào)度 DAG 多核 機群

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

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

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

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

1 任務調(diào)度模型

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

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

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

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

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

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

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

2 算法的思想

2.1 任務分配

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

2.2 任務復制

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

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

2.3 任務調(diào)度

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

3 算法的實現(xiàn)

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

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

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

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

4 結束語

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

參考文獻

[1]Laurea De Giusti，EmilioLuque，F(xiàn)rancoChichizola.AMTHA：An algorithm for automatically mapping tasks to processors in heterogeneous multiprocessor architectures[C]//World Congress.

[2]吳佳駿.多核多線程處理器上任務調(diào)度技術研究[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.

作者單位

廣西財經(jīng)學院防城港學院 廣西壯族自治區(qū)防城港市 538000