李靜梅，尤曉非，韓啟龍

（哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001）

0 引 言

基于異構(gòu)多核系統(tǒng)下的任務(wù)調(diào)度屬于 NP－難問(wèn)題［1，2］，所以只能得到問(wèn)題的近似最優(yōu)解或者是取得某些性能指標(biāo)上的優(yōu)化。任務(wù)的不恰當(dāng)調(diào)度不但會(huì)使系統(tǒng)真正潛在的計(jì)算能力得不到全面發(fā)揮，反而會(huì)阻礙并行化所帶來(lái)的性能提升［3，4］，故解決好任務(wù)調(diào)度問(wèn)題對(duì)提高處理器的性能和效率具有至關(guān)重要的作用。

關(guān)鍵路徑反映出緊迫性比較高的任務(wù)，所以關(guān)鍵路徑上的任務(wù)在滿足約束關(guān)系的條件下應(yīng)該優(yōu)先被執(zhí)行。任務(wù)集合中每一個(gè)子任務(wù)的調(diào)度都會(huì)使DAG （directed acyclic graph）中局部任務(wù)的計(jì)算開(kāi)銷和通信開(kāi)銷發(fā)生變化，影響關(guān)鍵路徑上信息的準(zhǔn)確性。故本文利用多關(guān)鍵路徑的方法矯正了由于每次任務(wù)調(diào)度后關(guān)鍵路徑的偏差。在DAG中初始任務(wù)是最先被執(zhí)行的任務(wù)且直接后繼節(jié)點(diǎn)的執(zhí)行都和其有約束關(guān)系，如果初始任務(wù)與直接后繼任務(wù)之間的通信開(kāi)銷太大而且它們被調(diào)度到不同的計(jì)算內(nèi)核上，那么其直接后繼任務(wù)必須得接收到其父節(jié)點(diǎn)執(zhí)行完畢的數(shù)據(jù)后才可以執(zhí)行，使得每個(gè)處理內(nèi)核上會(huì)出現(xiàn)空閑時(shí)間或后續(xù)調(diào)度任務(wù)陷入忙等狀態(tài)，故在任務(wù)開(kāi)始階段就降低任務(wù)整體的執(zhí)行效率。為克服這一問(wèn)題提出承受度判斷解決方法。綜上所述提出 TDMCP （task duplication multi critical path）調(diào)度算法。

1 任務(wù)調(diào)度問(wèn)題描述

任務(wù)調(diào)度實(shí)質(zhì)是通過(guò)一個(gè)特定算法得到任務(wù)集合的最優(yōu)解從而把任務(wù)按照最優(yōu)解順序依次調(diào)度到多處理器計(jì)算內(nèi)核上使任務(wù)整體執(zhí)行時(shí)間最短。如果不做特別說(shuō)明文中“節(jié)點(diǎn)”和 “任務(wù)”指的是同一概念。為了把抽象的概念具體化先用數(shù)學(xué)方法來(lái)進(jìn)行建模。一組有約束關(guān)系的任務(wù)集合可用圖論中一個(gè)四元組來(lái)表示，把有向無(wú)環(huán)圖 （DAG）描述為G＝ （V，E，W，C）［5］，其中 V＝ ｛ti｜ti是DAG中第i個(gè)任務(wù)｝，1≤i≤n，n為任務(wù)個(gè)數(shù)。E＝ ｛ei，j｜ei，j是任務(wù)ti到tj的通信約束關(guān)系｝，1≤i＜j≤n。W＝｛wi，j｜wi，j是任務(wù)ti在處理器內(nèi)核Pj上的執(zhí)行時(shí)間｝，其中Pj代表多核系統(tǒng)中第j個(gè)處理器內(nèi)核，P是處理器計(jì)算內(nèi)核集合P＝ ｛P1，P2，……，Pm｝，m 為處理器計(jì)算內(nèi)核的個(gè)數(shù)。C＝ ｛ci，j｜c(diǎn)i，j是 有約束關(guān) 系 的 任務(wù)ti到 任 務(wù)tj的通信開(kāi)銷｝。Pred（ti）為ti直接前驅(qū)節(jié)點(diǎn)集合，Succ（ti）為ti直接后繼節(jié)點(diǎn)集合。ESTj（ti）表示任務(wù)ti在處理器計(jì)算內(nèi)核Pj上最早開(kāi)始時(shí)間。圖1為DAG的一個(gè)實(shí)例圖。圖中節(jié)點(diǎn)表示任務(wù)，節(jié)點(diǎn)中的數(shù)值表示任務(wù)的計(jì)算開(kāi)銷。邊表示任務(wù)之間的約束關(guān)系，邊值表示有約束關(guān)系任務(wù)之間的通信開(kāi)銷。

這里做一些前提條件的假設(shè)：在拓?fù)浣Y(jié)構(gòu)中，如果初始節(jié)點(diǎn)多于一個(gè)，那么需要給這些初始節(jié)點(diǎn)建立一個(gè)新的父節(jié)點(diǎn)作為唯一的初始節(jié)點(diǎn)，此節(jié)點(diǎn)的計(jì)算開(kāi)銷為0，與直接后繼節(jié)點(diǎn)之間建立通信關(guān)系，通信開(kāi)銷標(biāo)為0。如果出節(jié)點(diǎn)有多個(gè)，那么需要給出節(jié)點(diǎn)生成一個(gè)新的子節(jié)點(diǎn)作為唯一的出節(jié)點(diǎn)。此節(jié)點(diǎn)的計(jì)算開(kāi)銷為0，與直接前驅(qū)節(jié)點(diǎn)之間建立通信關(guān)系，通信開(kāi)銷標(biāo)記為0；如果i＞j那么ti肯定不是tj的前驅(qū)節(jié)點(diǎn)；如果Pred（ti）＝Φ，那么任務(wù)ti是入結(jié)點(diǎn)，如果Succ（ti）＝Φ，那么任務(wù)ti是出節(jié)點(diǎn)；在DAG中每個(gè)任務(wù)必須等到其有約束關(guān)系的直接前驅(qū)任務(wù)執(zhí)行完并且把數(shù)據(jù)傳送過(guò)來(lái)后才可以執(zhí)行；如果兩個(gè)任務(wù)調(diào)度到同一個(gè)計(jì)算內(nèi)核上，那么它們之間的通信開(kāi)銷為零。同時(shí)任務(wù)之間是非搶占式執(zhí)行。

圖1 DAG任務(wù)

2 TDMCP算法

TDMCP算法的執(zhí)行分為任務(wù)選擇、處理器計(jì)算內(nèi)核選擇和狀態(tài)更新3個(gè)階段。這3個(gè)階段循環(huán)執(zhí)行一次調(diào)度一個(gè)子任務(wù)，直到任務(wù)調(diào)度完畢循環(huán)結(jié)束。在任務(wù)選擇階段，通過(guò)線性公式來(lái)判斷是否對(duì)首任務(wù)進(jìn)行復(fù)制操作，以減少首任務(wù)與直接后繼節(jié)點(diǎn)之間由于通信開(kāi)銷過(guò)大導(dǎo)致調(diào)度效率下降的問(wèn)題。處理器內(nèi)核選擇階段，計(jì)算出任務(wù)完成時(shí)間值最小的內(nèi)核作為調(diào)度處理器計(jì)算內(nèi)核。把任務(wù)調(diào)度到上面執(zhí)行。在狀態(tài)更新階段，利用更新準(zhǔn)則對(duì)任務(wù)計(jì)算開(kāi)銷和任務(wù)之間的通信開(kāi)銷進(jìn)行實(shí)時(shí)更新。算法執(zhí)行的具體過(guò)程如圖2所示。其中○表示信息源，→表示對(duì)箭尾信息源的操作。

圖2 任務(wù)調(diào)度過(guò)程

2.1 任務(wù)選擇階段

在任務(wù)選擇階段，基于初始任務(wù)對(duì)后續(xù)任務(wù)調(diào)度的重要性，初始任務(wù)單獨(dú)作為一類任務(wù)首先進(jìn)行選擇調(diào)度。后續(xù)調(diào)度任務(wù)則作為另一類任務(wù)進(jìn)行選擇調(diào)度。

2.1.1 初始任務(wù)選擇

首任務(wù)執(zhí)行對(duì)后續(xù)任務(wù)調(diào)度起到至關(guān)重要的作用，因?yàn)槿绻跏冀Y(jié)點(diǎn)與其直接后繼節(jié)點(diǎn)之間的通信開(kāi)銷太大而且它們被調(diào)度到不同的計(jì)算內(nèi)核上時(shí)，初始任務(wù)的后繼任務(wù)在執(zhí)行時(shí)必須得等其執(zhí)行完畢才可以執(zhí)行。這樣在任務(wù)調(diào)度開(kāi)始階段就會(huì)影響任務(wù)整體執(zhí)行效率，計(jì)算內(nèi)核可能出現(xiàn)空閑時(shí)間或后續(xù)調(diào)度任務(wù)忙等狀態(tài)。這對(duì)于異構(gòu)多核系統(tǒng)下高性能任務(wù)調(diào)度是絕對(duì)不能容忍的。所以針對(duì)這一問(wèn)題，提出初始結(jié)點(diǎn)判斷的公式。如式 （1）所示，承受度（task bear degree，TBD）是根據(jù) DAG整體松散性、入結(jié)點(diǎn)與直接后繼任務(wù)節(jié)點(diǎn)之間的計(jì)算開(kāi)銷和通信開(kāi)銷這3個(gè)線性因素計(jì)算得到

式中：α、β——兩個(gè)線性參數(shù)且α∈ ［0，1］，β∈ ［0，1］，α＋β＝1，如果DAG是稠密圖，整個(gè)任務(wù)運(yùn)行過(guò)程中的通信開(kāi)銷占據(jù)的比重大一點(diǎn)，那么α取0.4，β取0.6。如果DAG圖是稀疏圖，整個(gè)任務(wù)運(yùn)行過(guò)程中的計(jì)算開(kāi)銷占據(jù)的比重大一點(diǎn)，那么α取0.6，β取0.4。m為入結(jié)點(diǎn)直接后繼數(shù)目，n為處理器計(jì)算內(nèi)核的數(shù)目，wi（t1）為入節(jié)點(diǎn)在第i個(gè)計(jì)算內(nèi)核上的計(jì)算開(kāi)銷，C1，j為入節(jié)點(diǎn)與第j個(gè)直接后繼任務(wù)之間的通信開(kāi)銷。

如果入結(jié)點(diǎn)的平均計(jì)算開(kāi)銷大于TBD，那么對(duì)入結(jié)點(diǎn)采用任務(wù)復(fù)制技術(shù)，即把初始入結(jié)點(diǎn)任務(wù)調(diào)度到每一個(gè)計(jì)算內(nèi)核上運(yùn)行。然后進(jìn)行后續(xù)任務(wù)調(diào)度操作。反之入節(jié)點(diǎn)調(diào)度到最早完成時(shí)間值最小的處理器計(jì)算內(nèi)核上執(zhí)行。

2.1.2 后續(xù)任務(wù)選擇

對(duì)后續(xù)任務(wù)的選擇，選擇當(dāng)前任務(wù)集合中最緊迫性最高的任務(wù)既當(dāng)前關(guān)鍵路徑上需調(diào)度的任務(wù)［7］，如果緊迫性最高的任務(wù)有未被調(diào)度的父節(jié)點(diǎn)，那么就按照任務(wù)的向上排列值降序調(diào)度父節(jié)點(diǎn)。如果父任務(wù)的向上排列值相同那么就隨機(jī)選擇調(diào)度。這樣可以讓任務(wù)的總執(zhí)行時(shí)間通過(guò)局部?jī)?yōu)化達(dá)到整體最優(yōu)的效果。

任務(wù)選擇調(diào)度的過(guò)程中，每一步子任務(wù)的調(diào)度都會(huì)影響DAG中局部任務(wù)的計(jì)算開(kāi)銷和通信開(kāi)銷。所以關(guān)鍵路徑從調(diào)度開(kāi)始到結(jié)束不是唯一的，需要每次調(diào)度完子任務(wù)后對(duì)DAG進(jìn)行更新，然后計(jì)算新的關(guān)鍵路徑，所以整個(gè)調(diào)度過(guò)程中關(guān)鍵路徑是多個(gè)。為了計(jì)算每一步任務(wù)調(diào)度過(guò)程中的當(dāng)前關(guān)鍵路徑，引入 DAGP （DAG of processor）的概念。DAGP為每一個(gè)DAG在不同內(nèi)核上的映射。在任務(wù)調(diào)度執(zhí)行之前必須進(jìn)行DAGP的初始化。DAGP如定義所述。

定義1 假設(shè)DAG中有n個(gè)任務(wù)節(jié)點(diǎn)e條通信關(guān)系邊，在m （m＜n）個(gè)異構(gòu)多核處理器 ｛P1，P2，……Pm｝系統(tǒng)中。把DAG具體映射到每個(gè)處理內(nèi)核上形成了DAGP。

DAG所對(duì)應(yīng)處理器內(nèi)核Pi形成的DAG稱為DAGPi。DAGPi是用DAG構(gòu)造的，任務(wù)在處理器Pi上的計(jì)算開(kāi)銷值設(shè)置在DAGPi上。為了更具體的說(shuō)明DAGP，圖3所示為DAGP的一個(gè)實(shí)例化過(guò)程例子。圖3（a）為一個(gè)DAG任務(wù)圖，其中ti表示第i個(gè)任務(wù)。圖3（b）表示任務(wù)在處理器的兩個(gè)內(nèi)核上計(jì)算開(kāi)銷矩陣。其中矩陣第i行第j列值表示第i個(gè)任務(wù)在第j個(gè)計(jì)算內(nèi)核上執(zhí)行的計(jì)算開(kāi)銷。圖3（c）為DAG映射到第一個(gè)計(jì)算內(nèi)核上的DAGP稱為DAGP1，圖3（d）為DAG映射到第二個(gè)計(jì)算內(nèi)核上的DAGP稱為DAGP2。

圖3 DAGP的一個(gè)實(shí)例化過(guò)程

在每一步任務(wù)調(diào)度中，每個(gè)DAGP中從入節(jié)點(diǎn)到出節(jié)點(diǎn)在所有內(nèi)核上最大計(jì)算開(kāi)銷和通信開(kāi)銷之和的邊為當(dāng)前關(guān)鍵路徑。關(guān)鍵路徑選取實(shí)質(zhì)就是在每個(gè)內(nèi)核上找出關(guān)鍵路徑，然后選取其中最長(zhǎng)的一條作為當(dāng)前任務(wù)調(diào)度的關(guān)鍵路徑。假定當(dāng)前關(guān)鍵路徑上需要調(diào)度的任務(wù)稱之為關(guān)鍵任務(wù)。在進(jìn)行關(guān)鍵路徑選取的時(shí)候，如果DAGP中有兩條或者兩條以上最大關(guān)鍵路徑值相同，則采取隨機(jī)方法任意選取一條作為當(dāng)前關(guān)鍵路徑。

當(dāng)關(guān)鍵任務(wù)有未被調(diào)度的父節(jié)點(diǎn)時(shí)，需要先調(diào)度其父節(jié)點(diǎn)。在父任務(wù)調(diào)度次序的選取時(shí)，需給DAGP上的每個(gè)任務(wù)都得設(shè)置向上排列 （upward rank，URank）值來(lái)反映它們?cè)贒AGP中的優(yōu)先級(jí)。在任務(wù)調(diào)度的時(shí)候首先得考慮當(dāng)前關(guān)鍵任務(wù)，如果當(dāng)前需要調(diào)度的關(guān)鍵任務(wù)有未被調(diào)度的父任務(wù)，那么就得先調(diào)度其父任務(wù)然后調(diào)度關(guān)鍵任務(wù)。如果關(guān)鍵任務(wù)未被調(diào)度的父任務(wù)只有一個(gè)，那么直接調(diào)度其父任務(wù)。如果未被調(diào)度的父節(jié)點(diǎn)有多個(gè)，那么首先對(duì)父節(jié)點(diǎn)的任務(wù)進(jìn)行URank值的計(jì)算，URank值反映了關(guān)鍵路徑上節(jié)點(diǎn)的父任務(wù)優(yōu)先級(jí)。然后按照值的大小降序排列調(diào)度。對(duì)URank值相同的父任務(wù)，采用隨機(jī)方式調(diào)度父任務(wù)。

父任務(wù)的優(yōu)先級(jí)主要受到自身計(jì)算開(kāi)銷、與相關(guān)任務(wù)的通信開(kāi)銷和后繼任務(wù)優(yōu)先級(jí)三方面的影響。故向上排列值 （Up rank，URank）采用遞歸的方法定義如式 （2）所示

式中：Succj（ti）——DAGPj中任務(wù)ti的直接后繼集合，wj（ti）——DAGPj中 任 務(wù)ti的 計(jì) 算 開(kāi) 銷，cj（ti，tk）——DAGPj中任務(wù)ti到tk的通信開(kāi)銷。

2.2 處理器計(jì)算內(nèi)核選擇階段

處理器計(jì)算內(nèi)核的選擇是任務(wù)調(diào)度到處理器內(nèi)核上的最后一步。此階段執(zhí)行的操作是選擇任務(wù)完成時(shí)間值最小的處理器內(nèi)核作為目標(biāo)處理器內(nèi)核，然后把任務(wù)調(diào)度到目標(biāo)處理器內(nèi)核上。

由于任務(wù)在異構(gòu)多核環(huán)境下調(diào)度，所以同一任務(wù)在不同處理內(nèi)核上執(zhí)行的計(jì)算開(kāi)銷不同。任務(wù)調(diào)度到最早完成時(shí)間值最小的處理內(nèi)核上不一定能夠保證任務(wù)最早完成［6］。因?yàn)槿蝿?wù)調(diào)度到最早開(kāi)始時(shí)間最小的內(nèi)核上時(shí)，任務(wù)在此內(nèi)核上的計(jì)算開(kāi)銷不一定是最小的。那么完成時(shí)間就不能保證是最小的。為達(dá)到局部最優(yōu)需要選取完成時(shí)間最小的處理內(nèi)核最為目標(biāo)調(diào)度內(nèi)核。任務(wù)在處理器內(nèi)核上的最早完成時(shí)間計(jì)算公式如式 （3）所示。式 （3）中的EST在式（4）中求得

式中：EFTj（ti）——任務(wù)ti在計(jì)算內(nèi)核j上的最早完成時(shí)間，Pred（tk）——任務(wù)ti的前驅(qū)集合，ESTj（ti）——任務(wù)ti在計(jì)算內(nèi)核j上的最早開(kāi)始時(shí)間，c（ti，tk）——任務(wù)ti和tk之間的通信開(kāi)銷。m是一個(gè)常量系數(shù)，如果計(jì)算時(shí)任務(wù)ti和tk在同一個(gè)計(jì)算內(nèi)核上則m為0，如果不在同一個(gè)計(jì)算內(nèi)核上則m為1。

2.3 狀態(tài)更新階段

狀態(tài)更新階段，首先在每一步子任務(wù)調(diào)度完畢時(shí)按照更新準(zhǔn)則對(duì)DAGP中的任務(wù)計(jì)算開(kāi)銷和任務(wù)之間的通信開(kāi)銷進(jìn)行調(diào)整，以便及時(shí)更新關(guān)鍵路徑，然后找出緊迫性高的關(guān)鍵任務(wù)進(jìn)行調(diào)度。最后循環(huán)執(zhí)行，直到任務(wù)調(diào)度完畢為止。下面給出DAGP更新準(zhǔn)則：任務(wù)ti調(diào)度到處理器內(nèi)核Pj上意味著任務(wù)ti的計(jì)算開(kāi)銷不在是未知的，因此任務(wù)ti調(diào)度到處理器內(nèi)核Pj上的計(jì)算開(kāi)銷賦值到每個(gè)DAGP上去，既修改DAGP中的ti；如果調(diào)度結(jié)點(diǎn)與其有約束關(guān)系的父節(jié)點(diǎn)調(diào)度到同一個(gè)處理器計(jì)算內(nèi)核上，那么DAGP中它們之間的邊值置零。

TDMCP算法完整流程描述如下：

步驟1 任務(wù)調(diào)度開(kāi)始。

步驟2 輸入DAG任務(wù)圖。

步驟3 初始化所有的DAGP。

步驟4 如果任務(wù)執(zhí)行完畢，跳到步驟14。

步驟5 如果首任務(wù)的平均計(jì)算開(kāi)銷＜TBD那么復(fù)制首任務(wù)到每一個(gè)處理內(nèi)核上執(zhí)行，跳到步驟13。

步驟6 找到關(guān)鍵DAGP。

步驟7 找到關(guān)鍵DAGP中的關(guān)鍵節(jié)點(diǎn)。

步驟8 如果關(guān)鍵任務(wù)父節(jié)點(diǎn)未被調(diào)度直接調(diào)度。

步驟9 如果關(guān)鍵任務(wù)的父節(jié)點(diǎn)有未被調(diào)度的則利用URank值降序調(diào)度未被調(diào)度的父節(jié)點(diǎn)。

步驟10 計(jì)算當(dāng)前調(diào)度任務(wù)在每個(gè)處理器上的EFT。

步驟11 選擇EFT值最小的處理器最為目標(biāo)調(diào)度處理器。

步驟12 把當(dāng)前需要調(diào)度的任務(wù)調(diào)度到目標(biāo)處理器上。

步驟13 更新DAGP，跳到步驟4。

步驟14 任務(wù)調(diào)度結(jié)束。

TDMCP算法流程如圖4所示。

2.4 TDMCP算法時(shí)間復(fù)雜度分析

TDMCP算法的時(shí)間復(fù)雜度由任務(wù)選擇、處理器計(jì)算內(nèi)核選擇和狀態(tài)更新3個(gè)階段構(gòu)成。下面通過(guò)對(duì)這3個(gè)階段的分析來(lái)得出整個(gè)調(diào)度算法的時(shí)間復(fù)雜度。

在任務(wù)選擇階段，首先是對(duì)DAGP的初始化時(shí)間復(fù)雜度為O（n×p），n為DAG任務(wù)節(jié)點(diǎn)數(shù)目，p為處理器計(jì)算內(nèi)核數(shù)目。其次是關(guān)鍵路徑的選取，其時(shí)間復(fù)雜度為O（n2×p），接下來(lái)對(duì)首任務(wù)平均計(jì)算開(kāi)銷的計(jì)算，其時(shí)間復(fù)雜度為O（P）。然后是TBD的計(jì)算，其時(shí)間復(fù)雜度為O（n），最后是URank值的計(jì)算，其時(shí)間復(fù)雜度為O（n2）。任任務(wù)選擇階段的時(shí)間復(fù)雜度為O（n2×p）

在處理器計(jì)算內(nèi)核選擇階段，計(jì)算調(diào)度任務(wù)在不同處理器計(jì)算內(nèi)核上的EFT和EST值，其時(shí)間復(fù)雜度為O（n2×p）。

在狀態(tài)更新階段，主要是對(duì)任務(wù)計(jì)算開(kāi)銷和通信開(kāi)銷的更新。對(duì)任務(wù)計(jì)算開(kāi)銷的更新的時(shí)間復(fù)雜度為O（n×p），對(duì)任務(wù)之間通信開(kāi)銷的時(shí)間復(fù)雜度為O（e×p），e為DAG任務(wù)圖總邊的數(shù)目。故此階段的時(shí)間復(fù)雜度為O（n×p）。

綜上所述，TDMCP算法的時(shí)間復(fù)雜度為O（n2×p）＋O（n2×p）＋O（n×p），故其時(shí)間復(fù)雜度為O（n2×p）。

3 實(shí) 驗(yàn)

為了更加有效驗(yàn)證本算法的性能，采用調(diào)度長(zhǎng)度（normal schedule length，NSL）和 算 法 效 率 （efficiency）兩個(gè)參數(shù)作為性能測(cè)試指標(biāo)，利用現(xiàn)有的DAG生成器隨機(jī)產(chǎn)生DAG任務(wù)圖。選取兩個(gè)經(jīng)典的任務(wù)調(diào)度算法HEFT算法和CPFD算法作為實(shí)驗(yàn)對(duì)比算法。兩個(gè)算法的時(shí)間復(fù)雜度分別為O（n2×q）和O（n4）。首先采用具體DAG進(jìn)行實(shí)例分析來(lái)對(duì)比調(diào)度長(zhǎng)度，然后在任務(wù)節(jié)點(diǎn)個(gè)數(shù)不同和CCR （communication and computational ratio）不同的情況下分別做兩組實(shí)驗(yàn)來(lái)進(jìn)行性能對(duì)比。通過(guò)性能參數(shù)的設(shè)置和任務(wù)圖的生成使得實(shí)驗(yàn)更加的合理公平。下面對(duì)實(shí)驗(yàn)的兩個(gè)性能測(cè)試指標(biāo)NSL和算法效率做一下定義和分析。NSL如式 （5）所示，Speedup如式 （6）所示

式 （5）中分子SL為任務(wù)總的調(diào)度時(shí)間。分母中Ci，j表示任務(wù)ti與tj之間的通信開(kāi)銷。分子求的是任務(wù)在初始狀態(tài)時(shí)每個(gè)DAGP上的關(guān)鍵路徑最小值。NSL考慮了通信開(kāi)銷對(duì)調(diào)度長(zhǎng)度的影響。值越小說(shuō)明調(diào)度算法的性能越好

圖4 TDMCP算法流程

式 （6）中Efficiency為任務(wù)調(diào)度加速比與用于調(diào)度任務(wù)處理器個(gè)數(shù)的比值。式中分子speedup為加速比，Speedup的計(jì)算如式 （7）所示，式 （7）中分子中的 Wi，j為任務(wù)ti在處理器內(nèi)核Pj上的計(jì)算開(kāi)銷，分子表示任務(wù)在初始DAGP中執(zhí)行時(shí)間的最小值。分母SL為任務(wù)調(diào)度的總時(shí)間。分母｜P｜為調(diào)度時(shí)所用的處理器內(nèi)核個(gè)數(shù)。如果Efficiency越大，任務(wù)調(diào)度算法的性能越好。

實(shí)驗(yàn)一：首先給出一個(gè)實(shí)例化的DAG任務(wù)圖，圖5任務(wù)調(diào)度具體實(shí)例化。圖5（a）為一個(gè)DAG圖，共有10個(gè)子任務(wù)，邊值代表有約束關(guān)系任務(wù)之間的通信開(kāi)銷值。圖5（b）為任務(wù)集合在3個(gè)處理內(nèi)核上的計(jì)算開(kāi)銷矩陣［8］。圖6為TDMCP算法、HEFT算法和CPFD算法的調(diào)度過(guò)程，3種算法的調(diào)度時(shí)間分別為79、80和86?？梢钥闯霰疚奶岢龅腡DMCP算法在調(diào)度時(shí)間和處理內(nèi)核的利用率方面優(yōu)于后兩種算法。同時(shí)處理內(nèi)核空閑時(shí)間相對(duì)于后兩種算法要少很多。

圖5 任務(wù)調(diào)度具體實(shí)例化

圖6 3個(gè)算法的調(diào)度過(guò)程

實(shí)驗(yàn)二：考慮到實(shí)驗(yàn)的公平客觀性，在DAG圖的選取上采用多參數(shù)隨機(jī)產(chǎn)生的方式［9，10］，選取4個(gè)參隨機(jī)參數(shù)分別是DAG規(guī)模、通信計(jì)算開(kāi)銷比、并行因子和計(jì)算開(kāi)銷的異構(gòu)性因子，而且DAG數(shù)據(jù)量也比較大，使其生產(chǎn)的DAG雜度滿足正太分布，這樣就使得產(chǎn)生的DAG圖具有普遍性。實(shí)驗(yàn)采取兩組來(lái)做，第一組實(shí)驗(yàn)是CCR不同時(shí)的性能指標(biāo)比較，如圖7和圖8所示。第二組實(shí)驗(yàn)是Number of Nodes不同時(shí)性能指標(biāo)的比較，如圖9和圖10所示。

圖7 CCR不同時(shí)NSL

圖7為3個(gè)算法在CCR分別為0.1、0.5、1、2、3時(shí)NSL性能的比較［11］。圖8為CCR分別為0.1、0.5、1、2、3時(shí)Efficiency性能的比較。從圖7和圖8可以看出隨著CCR值增大任務(wù)之間的通信開(kāi)銷增加，在任務(wù)調(diào)度到不同處理內(nèi)核上執(zhí)上時(shí)需要花費(fèi)一定的時(shí)間來(lái)等待父任務(wù)的數(shù)據(jù)使得處理內(nèi)核出現(xiàn)了空閑時(shí)間增加了調(diào)度的時(shí)間，3種算法的NSL和Efficiency性能都下降了。但是TDMCP算法NSL變化幅度要小于HEFT算法和CFPD算法。同時(shí)TDMCP算法效率優(yōu)于后兩種算法。因?yàn)門DMCP算法采用多關(guān)鍵路徑。使得任務(wù)調(diào)度的每一步都及時(shí)更新DAG的關(guān)鍵路徑，這樣核間通信開(kāi)銷比較大的任務(wù)盡可能多的處于關(guān)鍵路徑上，盡早的被調(diào)度。任務(wù)從整體上實(shí)現(xiàn)了調(diào)度的最優(yōu)化。

圖8 CCR不同時(shí)Efficiency

圖9 Number of Nodes不同時(shí) NSL

圖10 Number of Nodes不同時(shí)Efficiency

圖9為3個(gè)算法在 Number of Nodes分別為20、40、60、80、100時(shí)NSL性能的比較。圖10為3個(gè)算法在Number of Nodes分別為20、40、60、80、100時(shí)Efficiency性能的比較。從圖9和圖10可以看出隨著任務(wù)節(jié)點(diǎn)個(gè)數(shù)的增加，任務(wù)之間的約束關(guān)系變的復(fù)雜化，DAG圖變的稠密了。3種算法的NSL和Efficiency性能隨之降低了。但是TDMCP算法的效率要高于HEFT算法和CPFD算法。因?yàn)殡S著任務(wù)節(jié)點(diǎn)個(gè)數(shù)的增加DAG復(fù)雜度也增加，任務(wù)開(kāi)始調(diào)度的速度對(duì)于后續(xù)任務(wù)調(diào)度影響比較大。TDMCP算法采用了基于首任務(wù)復(fù)制的技術(shù)，使得開(kāi)始的任務(wù)執(zhí)行速度提高，為后續(xù)的任務(wù)的執(zhí)行提前了時(shí)間，從而使得任務(wù)局部到達(dá)最優(yōu)化。

4 結(jié)束語(yǔ)

本文采用多關(guān)鍵路徑的方法，在調(diào)度的每一步都更新當(dāng)前關(guān)鍵路徑，使得整個(gè)任務(wù)調(diào)度過(guò)程中關(guān)鍵路徑上的信息實(shí)時(shí)準(zhǔn)確，及時(shí)調(diào)度緊迫性高的任務(wù)。首任務(wù)作為最先調(diào)度任務(wù)對(duì)后續(xù)任務(wù)的調(diào)度效率有很大的影響，故本文對(duì)首任務(wù)采用任務(wù)復(fù)制技術(shù)，首先判斷入節(jié)點(diǎn)是否超出承受度值，如果超出就把入節(jié)點(diǎn)復(fù)制到每個(gè)處理器計(jì)算內(nèi)核上執(zhí)行，從局部對(duì)任務(wù)調(diào)度進(jìn)行優(yōu)化。但是在調(diào)度的過(guò)程中發(fā)現(xiàn)部分處理器計(jì)算內(nèi)核上存在空閑時(shí)間槽，在后續(xù)的研究過(guò)程中要利用時(shí)間槽插入技術(shù)來(lái)解決這一問(wèn)題，使得任務(wù)算法更加完善，處理器利用率更加高效。

［1］Fortnow L.The status of the P versus NP problem ［J］.Communications of the Acm，2009，52 （9）：78－86.

［2］Moshe Y Vardi.On P，NP and computational complexity ［J］.Communications of the Acm，2010，53 （11）：5－6.

［3］HUANG Haiya，HE Dake.Grid task schedule algorithm based on load balance ［J］.Computer Engineering，2010，36 （2）：58－60（in Chinese）.［黃海于，何大可.一種基于負(fù)載均衡性的網(wǎng)格任務(wù)調(diào)度算法 ［J］.計(jì)算機(jī)工程，2010，36 （2）：58－60.］

［4］HUANG Guorui，ZHANG Ping，WEI Guangbo.Key techniques of multi－core processor and its development trends ［J］.Computer Engineering and Design，2009，31 （10）：2414－2418（in Chinese）.［黃國(guó)睿，張平，魏廣博.多核處理器的關(guān)鍵技術(shù)及其發(fā)展趨勢(shì) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （10）：2414－2418.］

［5］LI Jingmei，JIN Shengnan.Research on static task scheduling based on heterogeneous multi－core processor ［J］.Computer Engineering and Design，2013，34 （1）：178－184 （in Chinese）.［李靜梅，金勝男.基于異構(gòu)多核處理器的靜態(tài)任務(wù)調(diào)度研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （1）：178－184.］

［6］HE Yanxiang，XU Chao.A task scheduling method to increase the reliability of the multicore system ［J］.ACTA Electronica Sinica，2013，41 （5）：1019－1024 （in Chinese）.［何炎祥，徐超.一種多核系統(tǒng)可靠性加強(qiáng)的任務(wù)調(diào)度方法 ［J］.電子學(xué)報(bào)，2013，41 （5）：1019－1024.］

［7］Tang Xiaoyong，Li Kenli，Liao Guiping，et al.List scheduling with duplication for heterogeneous computing systems ［J］.J Parallel Distrib Comput，2010，70 （4）：323－329.

［8］TAN Yiming，ZENG Guosun，HAO Shuixia.Performance analysis for scheduling on heterogeneous ＆reconfigurable computing system ［J］.Journal of Chinese Computer System，2012，33 （2）：404－408 （in Chinese）. ［譚一鳴，曾國(guó)蓀，郝水俠.異構(gòu)重構(gòu)計(jì)算機(jī)系統(tǒng)應(yīng)用任務(wù)調(diào)度的性能分析 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33 （2）：404－408.］

［9］Amit Agarwal，Padam Kumar.Economical duplication based task scheduling for heterogeneous and homogeneous computing system ［C］／／IEEE International Advance Computing Conference，2009：87－93.

［10］Hassan Salamy，Ramanujam J.An effective solution to task scheduling and memory partitioning for multiprocessor systemon－chip ［J］.IEEE Tractions on Computer－Aided Design of Integrated and System，2012，31 （5）：717－725.

［11］Hosseinzadeh，Shahriar Shahhoseini.Earliest starting and finishing time duplication－based algorithm ［J］.Performance Evaluation of Computer ＆ Telecommunication Systems，2009，41 （13）：49－56.