李霞

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

【關(guān)鍵詞】任務(wù)調(diào)度 DAG 多核 機群

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

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

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

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

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

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

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

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

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

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

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

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

2 算法的思想

2.1 任務(wù)分配

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

2.2 任務(wù)復(fù)制

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

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

2.3 任務(wù)調(diào)度

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

3 算法的實現(xiàn)

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

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

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

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

4 結(jié)束語

對于多核異構(gòu)機群系統(tǒng)，本文充分利用多核機器多個處理核心共享二級緩存的特性，針對基于DAG圖的相關(guān)任務(wù)的調(diào)度問題，采用三個階段分別進行任務(wù)的分配、復(fù)制以及調(diào)度，在任務(wù)的分配階段利用多核機器共享二級緩存的特性減少相關(guān)任務(wù)之間的通信開銷；任務(wù)的復(fù)制階段使相關(guān)的任務(wù)變成可以并行執(zhí)行的多個子任務(wù)群，然后根據(jù)各個處理機節(jié)點的處理能力的不同進行子任務(wù)群的分配；而在多核處理機節(jié)點內(nèi)采用現(xiàn)有的遺傳算法對各個子任務(wù)群進行調(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]吳佳駿.多核多線程處理器上任務(wù)調(diào)度技術(shù)研究[D].北京：中國科學(xué)院，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)學(xué)院防城港學(xué)院 廣西壯族自治區(qū)防城港市 538000