李霞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法的思想

2.1 任務(wù)分配

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

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

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

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

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

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

3 算法的實(shí)現(xiàn)

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[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.

作者單位

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