異構(gòu)計(jì)算環(huán)境下基于優(yōu)先隊(duì)列劃分的調(diào)度算法

王 蘭，張龍信，滿君豐，周立前，李肯立

1(湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412007)2(湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082)

1 引 言

隨著云計(jì)算和物聯(lián)網(wǎng)等技術(shù)的快速發(fā)展，以及新型社交網(wǎng)絡(luò)的不斷涌現(xiàn)，數(shù)據(jù)正在以前所未有的速度不斷地產(chǎn)生和累積，大數(shù)據(jù)和萬(wàn)物互聯(lián)的時(shí)代已經(jīng)到來(lái).相對(duì)于物聯(lián)網(wǎng)而言，萬(wàn)物互聯(lián)在物聯(lián)網(wǎng)的基礎(chǔ)上更側(cè)重于“人”與“物”的互聯(lián)[1]，增強(qiáng)網(wǎng)絡(luò)智能，推動(dòng)人工智能的發(fā)展.萬(wàn)物互聯(lián)的不斷發(fā)展，網(wǎng)絡(luò)邊緣設(shè)備數(shù)量亦迅猛地增長(zhǎng).

網(wǎng)絡(luò)邊緣設(shè)備和社交媒體等產(chǎn)生海量的、復(fù)雜多樣的數(shù)據(jù)，利用云計(jì)算中心超強(qiáng)的計(jì)算能力來(lái)計(jì)算和處理數(shù)據(jù).數(shù)據(jù)中心接受到提交的數(shù)據(jù)任務(wù)，采用合理高效的任務(wù)調(diào)度算法可以提高計(jì)算性能、降低數(shù)據(jù)處理時(shí)間.因此，任務(wù)調(diào)度問(wèn)題已經(jīng)成為云計(jì)算和邊緣計(jì)算中的研究熱點(diǎn)問(wèn)題[2]，異構(gòu)計(jì)算模式下的任務(wù)調(diào)度問(wèn)題依舊是研究重點(diǎn)問(wèn)題.

異構(gòu)計(jì)算環(huán)境下的任務(wù)調(diào)度問(wèn)題已經(jīng)被證明是NP-hard問(wèn)題[3]，所以任務(wù)調(diào)度問(wèn)題只能通過(guò)設(shè)計(jì)的優(yōu)化算法取得近似最優(yōu)解.在并行計(jì)算環(huán)境下，合理高效的任務(wù)調(diào)度算法會(huì)使處理器系統(tǒng)的計(jì)算性能得到很大的提升.任務(wù)調(diào)度問(wèn)題是指在滿足某些約束條件的情況下(節(jié)點(diǎn)間的數(shù)據(jù)依賴關(guān)系和處理器的計(jì)算消耗)，按照設(shè)計(jì)的算法科學(xué)地將每個(gè)節(jié)點(diǎn)任務(wù)映射到對(duì)應(yīng)處理器上并高效地執(zhí)行，以達(dá)到最小化任務(wù)執(zhí)行的完成時(shí)間、最大化算法的調(diào)度效率的目的.任務(wù)的有效調(diào)度是提高處理器計(jì)算性能和資源利用率的關(guān)鍵所在.

任務(wù)調(diào)度問(wèn)題一直以來(lái)都是高性能計(jì)算中的經(jīng)典問(wèn)題.根據(jù)應(yīng)用程序的特征(包括任務(wù)間的依賴關(guān)系、任務(wù)在處理器上的計(jì)算開(kāi)銷以及任務(wù)之間的通信開(kāi)銷)是否提前給定，可將任務(wù)調(diào)度問(wèn)題分為靜態(tài)任務(wù)調(diào)度和動(dòng)態(tài)任務(wù)調(diào)度[4].現(xiàn)有的主要研究工作是針對(duì)靜態(tài)任務(wù)調(diào)度模型，靜態(tài)任務(wù)調(diào)度中應(yīng)用程序的特征是確定的.針對(duì)異構(gòu)系統(tǒng)中的靜態(tài)調(diào)度問(wèn)題，主要可劃分為基于啟發(fā)式的調(diào)度算法和基于引導(dǎo)隨機(jī)搜索的調(diào)度算法，高調(diào)度效率的HEFT[4]、CPOP[4]、HCPFD[5]等啟發(fā)式算法被廣泛運(yùn)用到實(shí)際的應(yīng)用程序中.

隨著海量數(shù)據(jù)的產(chǎn)生和計(jì)算數(shù)量的增長(zhǎng)，異構(gòu)計(jì)算環(huán)境下DAG任務(wù)圖的結(jié)構(gòu)也變得復(fù)雜多樣化.傳統(tǒng)的調(diào)度算法在解決復(fù)雜問(wèn)題時(shí)可能得不到理想的結(jié)果，這需要通過(guò)更為合理高效的調(diào)度策略來(lái)優(yōu)化和平衡系統(tǒng)的各方面性能[6].目前，國(guó)內(nèi)外研究學(xué)者已經(jīng)提出了很多算法.文獻(xiàn)[7]提出了一種前驅(qū)節(jié)點(diǎn)優(yōu)先級(jí)最早完成時(shí)間算法，首先生成前驅(qū)節(jié)點(diǎn)優(yōu)先級(jí)隊(duì)列(PPQ)，任務(wù)根據(jù)向下排名和優(yōu)先級(jí)在PPQ中排隊(duì)等待調(diào)度.文獻(xiàn)[8]考慮到任務(wù)執(zhí)行時(shí)關(guān)鍵路徑上的信息會(huì)隨著任務(wù)調(diào)度動(dòng)態(tài)更新，對(duì)首任務(wù)采用復(fù)制技術(shù)，然而任務(wù)每一次實(shí)時(shí)更新會(huì)增加整個(gè)任務(wù)的調(diào)度復(fù)雜性.文獻(xiàn)[9]提出了一種基于隊(duì)列的資源調(diào)度模型，其將任務(wù)和處理器問(wèn)題轉(zhuǎn)化成最大費(fèi)用最小流圖，從而有效地優(yōu)化大規(guī)模資源調(diào)度.文獻(xiàn)[10]針對(duì)異構(gòu)計(jì)算系統(tǒng)中的應(yīng)用程序在使用DVS(動(dòng)態(tài)電壓頻率調(diào)節(jié))技術(shù)實(shí)現(xiàn)節(jié)能時(shí)，瞬態(tài)故障難以避免.對(duì)于具有優(yōu)先約束的并行任務(wù)集，設(shè)計(jì)了能量約束下的應(yīng)用程序可靠性最大化算法RMEC.RMEC算法能有效地實(shí)現(xiàn)系統(tǒng)高可靠性與能量節(jié)約之間平衡的目標(biāo).文獻(xiàn)[11]提出了數(shù)據(jù)中心的能量消耗最小和系統(tǒng)失效率最小的雙目標(biāo)優(yōu)化算法，該算法在不增加時(shí)間開(kāi)銷的約束下，能找到更好的pareto front(帕內(nèi)托前沿).文獻(xiàn)[12]提出了最小松弛時(shí)間和最小距離(MSMD)算法，該算法針對(duì)應(yīng)用程序截止日期所需的最小VM實(shí)例數(shù)，在分配的VM實(shí)例上調(diào)度任務(wù)，以達(dá)到最小化應(yīng)用程序的調(diào)度時(shí)間.以上研究很少針對(duì)復(fù)雜多樣的DAG并行任務(wù)集展開(kāi)研究，因此，本文以提高任務(wù)間的并行性和處理器的執(zhí)行效率為目標(biāo)，針對(duì)多入口、多出口的并行任務(wù)集，提出基于優(yōu)先隊(duì)列劃分調(diào)度算法(PQDSA).本文設(shè)計(jì)的算法將根據(jù)入口節(jié)點(diǎn)數(shù)量確定優(yōu)先隊(duì)列數(shù)量，劃分調(diào)度優(yōu)先隊(duì)列，將復(fù)雜多樣的任務(wù)集簡(jiǎn)單化.

本文第一部分介紹了異構(gòu)計(jì)算環(huán)境下任務(wù)調(diào)度的相關(guān)背景和現(xiàn)有的研究工作.第二部分闡述了任務(wù)調(diào)度模型和具體應(yīng)用模型.第三部分詳細(xì)介紹了本文提出的算法.第四部分通過(guò)實(shí)驗(yàn)驗(yàn)證了本方法的可行性和有效性.最后對(duì)本文工作進(jìn)行了總結(jié)，并對(duì)下一步的研究工作進(jìn)行了展望.

2 相關(guān)知識(shí)

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

異構(gòu)環(huán)境下的任務(wù)調(diào)度問(wèn)題，是指將具有約束條件的任務(wù)按照特定的算法映射到有限的處理器上進(jìn)行執(zhí)行.這些任務(wù)一般會(huì)用DAG圖來(lái)刻畫(huà)，任務(wù)可以表示為節(jié)點(diǎn)，節(jié)點(diǎn)是任務(wù)調(diào)度中的最小單位.當(dāng)異構(gòu)計(jì)算系統(tǒng)中有任務(wù)等待執(zhí)行時(shí)，主機(jī)會(huì)按照特定算法尋找符合條件的處理器來(lái)進(jìn)行調(diào)度，即將任務(wù)分配給合適的處理器進(jìn)行有效調(diào)度以達(dá)到預(yù)期的優(yōu)化目標(biāo).將n個(gè)任務(wù)調(diào)度到m個(gè)處理器上的任務(wù)調(diào)度模型如圖1所示.

圖1 n個(gè)任務(wù)調(diào)度到m個(gè)處理器上調(diào)度模型Fig.1 Scheduling model of n tasks scheduled to m processors

2.2 應(yīng)用模型描述

任務(wù)調(diào)度是異構(gòu)計(jì)算環(huán)境下的關(guān)鍵問(wèn)題，這種存在約束關(guān)系的任務(wù)節(jié)點(diǎn)可以用DAG圖來(lái)進(jìn)行刻畫(huà)，即G={T，E，W，C}，其中T={ti|(i=1，2，…，n)}表示異構(gòu)系統(tǒng)中的任務(wù)節(jié)點(diǎn)集合，n為任務(wù)節(jié)點(diǎn)總數(shù)量.E={eij|eij表示節(jié)點(diǎn)ti與節(jié)點(diǎn)tj的邊}，即節(jié)點(diǎn)ti與節(jié)點(diǎn)tj之間存在優(yōu)先約束關(guān)系且tj是ti的直接后繼節(jié)點(diǎn).C={cij|cij表示ti與tj之間的通信開(kāi)銷，ti是tj直接前驅(qū)節(jié)點(diǎn)}，cij表示兩個(gè)任務(wù)節(jié)點(diǎn)不在同一個(gè)處理器上執(zhí)行時(shí)所需的通信開(kāi)銷.W={wij|表示節(jié)點(diǎn)ti在處理器pj上的計(jì)算開(kāi)銷}，其中pj表示異構(gòu)系統(tǒng)中第j個(gè)處理器，P是處理器的集合，P={p1，p2，…，pm}，m為處理器總數(shù)量.如果DAG任務(wù)圖中不止一個(gè)入口或出口節(jié)點(diǎn)，我們可以構(gòu)建虛擬節(jié)點(diǎn)作為唯一的入口節(jié)點(diǎn)或出口節(jié)點(diǎn)，該虛擬節(jié)點(diǎn)無(wú)通信開(kāi)銷和計(jì)算開(kāi)銷.節(jié)點(diǎn)調(diào)度時(shí)必須接收到所有前驅(qū)節(jié)點(diǎn)的數(shù)據(jù)才可以進(jìn)入準(zhǔn)備就緒狀態(tài)，等待調(diào)度.如圖2所示的DAG任務(wù)圖，T1-T10表示10個(gè)任務(wù)節(jié)點(diǎn)，有向邊上的數(shù)字表示節(jié)點(diǎn)間的依賴關(guān)系，即通信開(kāi)銷.表1描述了任務(wù)節(jié)點(diǎn)在不同處理器上執(zhí)行所需要的計(jì)算開(kāi)銷.

圖2 包含10個(gè)任務(wù)節(jié)點(diǎn)的DAG應(yīng)用模型Fig.2 DAG application model with 10 task nodes

圖2所示的DAG圖中，各任務(wù)節(jié)點(diǎn)在處理器上的計(jì)算開(kāi)銷如表1所示.為了描述方便，現(xiàn)對(duì)任務(wù)的開(kāi)始時(shí)間、完成時(shí)間、調(diào)度長(zhǎng)度和調(diào)度效率給出以下定義.

表1 任務(wù)節(jié)點(diǎn)的計(jì)算開(kāi)銷
Table 1 Computation cost of task nodes

TaskiP1P2P3wi-T12312T25133T32132T43343.3T52443.3T61322T72163T84534T91322T104835

定義1.任務(wù)的開(kāi)始時(shí)間、完成時(shí)間：若ST(ti，pj)、FT(ti，pj)分別表示任務(wù)ti在處理器pj上的開(kāi)始時(shí)間和完成時(shí)間，則它們之間的數(shù)學(xué)關(guān)系如式(1)所示：

FT(ti,pj)=ST(ti,pj)+cij

(1)

定義2.前驅(qū)節(jié)點(diǎn)、后繼節(jié)點(diǎn)：若pred(ti)表示任務(wù)ti的前驅(qū)節(jié)點(diǎn)，如果任務(wù)ti沒(méi)有前驅(qū)節(jié)點(diǎn)，則該任務(wù)是入口節(jié)點(diǎn).succ(ti)表示任務(wù)ti的后繼節(jié)點(diǎn)，若任務(wù)ti沒(méi)有后繼節(jié)點(diǎn)，則該任務(wù)為出口節(jié)點(diǎn).

任務(wù)節(jié)點(diǎn)ti平均計(jì)算開(kāi)銷定義為：

(2)

其中，wij為任務(wù)ti在處理器pi上的計(jì)算開(kāi)銷，m為處理器的數(shù)量.

節(jié)點(diǎn)任務(wù)的優(yōu)先級(jí)主要由通信開(kāi)銷、自身在處理器上的計(jì)算開(kāi)銷和前驅(qū)節(jié)點(diǎn)的優(yōu)先級(jí)等三個(gè)因素共同決定.

定義3.任務(wù)的TL(ti)值：從入口節(jié)點(diǎn)開(kāi)始采用遞歸的方法計(jì)算每個(gè)節(jié)點(diǎn)的t-level值TL(ti)，其計(jì)算表達(dá)式為：

(3)

入口節(jié)點(diǎn)的TL(ti)的計(jì)算表達(dá)式如式(4)所示：

(4)

定義4.調(diào)度長(zhǎng)度(makespan)：若Texit代表出口節(jié)點(diǎn),FT(Texit,pj)表示整個(gè)調(diào)度的完成時(shí)間,若出口節(jié)點(diǎn)不止一個(gè),可以添加零計(jì)算開(kāi)銷、零通信開(kāi)銷的偽節(jié)點(diǎn)作為最后的唯一出口節(jié)點(diǎn),調(diào)度長(zhǎng)度為：

makespan=max{FT(Texit,pj)}

(5)

調(diào)度的最終目的是將節(jié)點(diǎn)任務(wù)科學(xué)地分配到處理器上執(zhí)行，以達(dá)到最小化調(diào)度長(zhǎng)度的目標(biāo).

定義5.調(diào)度效率：算法的調(diào)度效率(Efficiency)是指任務(wù)調(diào)度加速比與處理器總數(shù)量的比值，其取值范圍為0到100%.調(diào)度效率由DAG任務(wù)的完成時(shí)間和處理器的數(shù)量共同決定，其計(jì)算表達(dá)式為：

(6)

其中,m為處理器總數(shù),Speedup為加速比.加速比是指任務(wù)集的順序計(jì)算時(shí)間與調(diào)度長(zhǎng)度的比值.

為了描述方便，我們將本文中可能使用到的符號(hào)和參數(shù)進(jìn)行歸納，如表2所示.

表2 符號(hào)和參數(shù)定義
Table 2 Symbol and parameter definition

參數(shù)和符號(hào)定 義T任務(wù)集合ti第i個(gè)任務(wù)節(jié)點(diǎn)Pj第j個(gè)處理器wij任務(wù)節(jié)點(diǎn)ti在處理器pj上的計(jì)算開(kāi)銷cij任務(wù)節(jié)點(diǎn)ti與節(jié)點(diǎn)tj的通信開(kāi)銷pred(ti) 任務(wù)節(jié)點(diǎn)ti的前驅(qū)節(jié)點(diǎn)集合succ(ti)任務(wù)節(jié)點(diǎn)ti的后繼節(jié)點(diǎn)集合Wi平均計(jì)算開(kāi)銷Tentry入口節(jié)點(diǎn)Texit出口節(jié)點(diǎn)Li劃分優(yōu)先隊(duì)列時(shí)借助的空隊(duì)列AECT(ti)任務(wù)節(jié)點(diǎn)ti的平均完成時(shí)間Mpred(ti)任務(wù)節(jié)點(diǎn)ti的直接前驅(qū)節(jié)點(diǎn)總和Mexit(Li)隊(duì)列Li的出口節(jié)點(diǎn)總和TL(ti)任務(wù)節(jié)點(diǎn)ti的t-level值

2.3 問(wèn)題描述

人工智能的崛起和網(wǎng)絡(luò)邊緣設(shè)備的增加以及數(shù)據(jù)的大量產(chǎn)生，都離不開(kāi)高性能計(jì)算中心的支持.數(shù)據(jù)的海量產(chǎn)生和高性能計(jì)算的高效要求，以及DAG任務(wù)圖的多變性，都對(duì)DAG應(yīng)用程序的調(diào)度提出更高的性能要求.降低DAG任務(wù)圖節(jié)點(diǎn)任務(wù)的完工時(shí)間以及最大化算法的調(diào)度效率，本文側(cè)重于這兩個(gè)目標(biāo).為了達(dá)到所要求的目標(biāo)，第一步在滿足約束條件下，對(duì)隊(duì)列進(jìn)行劃分，提高任務(wù)間的并行性，以達(dá)到降低調(diào)度長(zhǎng)度的目的.第二步在保證盡可能降低調(diào)度長(zhǎng)度的前提下，將任務(wù)科學(xué)地調(diào)度到處理器上，以達(dá)到最大化處理器的資源利用率[13].

3 優(yōu)先隊(duì)列劃分調(diào)度算法(PQDSA)

眾所周知，異構(gòu)計(jì)算環(huán)境下的任務(wù)調(diào)度問(wèn)題是NP-hard問(wèn)題[3].為了提高處理器的執(zhí)行效率和任務(wù)間的并行性，本文提出基于優(yōu)先隊(duì)列劃分的任務(wù)調(diào)度算法(PQDSA).PQDSA算法的主要思想是根據(jù)入口節(jié)點(diǎn)的數(shù)量，通過(guò)計(jì)算開(kāi)銷和通信開(kāi)銷來(lái)劃分合適的優(yōu)先隊(duì)列.該算法執(zhí)行步驟分為優(yōu)先隊(duì)列劃分、節(jié)點(diǎn)優(yōu)先級(jí)以及處理器選擇三個(gè)階段.首先，存在數(shù)據(jù)依賴關(guān)系的節(jié)點(diǎn)在不同的處理器上執(zhí)行時(shí)，會(huì)存在通信開(kāi)銷.為了降低任務(wù)集的完工時(shí)間，將通信開(kāi)銷較大的任務(wù)分配到同一臺(tái)處理器上執(zhí)行，以提高調(diào)度效率.然后，根據(jù)入口節(jié)點(diǎn)數(shù)量劃分的優(yōu)先隊(duì)列，計(jì)算隊(duì)列中節(jié)點(diǎn)的TL(ti)值，確定節(jié)點(diǎn)優(yōu)先級(jí).最后，在處理器選擇階段，使用基于插入策略的思想，計(jì)算出任務(wù)完成時(shí)間最小的處理器，將其作為該節(jié)點(diǎn)的調(diào)度處理器，從而進(jìn)一步縮短調(diào)度時(shí)間.

3.1 優(yōu)先隊(duì)列劃分階段

在優(yōu)先隊(duì)列劃分階段，針對(duì)復(fù)雜多樣的DAG任務(wù)圖，在任務(wù)執(zhí)行調(diào)度之前，首先根據(jù)入口節(jié)點(diǎn)的數(shù)量來(lái)決定劃分多少優(yōu)先隊(duì)列.在本文中，從DAG圖中的入口節(jié)點(diǎn)到出口節(jié)點(diǎn)，通信開(kāi)銷和計(jì)算開(kāi)銷之和最大的路徑稱為關(guān)鍵路徑.多于一個(gè)直接前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)稱為關(guān)鍵節(jié)點(diǎn).任務(wù)劃分的主要思想是將關(guān)鍵節(jié)點(diǎn)劃分到適合的隊(duì)列中，生成最佳的任務(wù)調(diào)度隊(duì)列，以提高任務(wù)的并行性.計(jì)算每個(gè)節(jié)點(diǎn)的平均完成時(shí)間(AECT)，根據(jù)AECT值對(duì)節(jié)點(diǎn)進(jìn)行劃分，然后在調(diào)度到合適的處理器上執(zhí)行.劃分優(yōu)先隊(duì)列時(shí)需要借助空隊(duì)列Li(i=1，2，3…)，i的取值取決于實(shí)際入口節(jié)點(diǎn)的數(shù)量.參數(shù)Mexit(Li)表示隊(duì)列Li出口節(jié)點(diǎn)的總數(shù)，Mpred(ti)表示節(jié)點(diǎn)ti的直接前驅(qū)節(jié)點(diǎn)的總數(shù).對(duì)于多入口多出口節(jié)點(diǎn)的復(fù)雜任務(wù)應(yīng)用程序，即存在多個(gè)入口節(jié)點(diǎn)和多個(gè)出口節(jié)點(diǎn)，可以采用零計(jì)算開(kāi)銷和零數(shù)據(jù)傳輸時(shí)間的節(jié)點(diǎn)作為偽入口節(jié)點(diǎn)和偽出口節(jié)點(diǎn)，偽節(jié)點(diǎn)不影響整個(gè)調(diào)度過(guò)程.

任務(wù)的平均完成時(shí)間(AECT)從入口節(jié)點(diǎn)開(kāi)始采用遞歸的方式進(jìn)行計(jì)算，其表達(dá)式如式(7)所示：

(7)

對(duì)于入口節(jié)點(diǎn)Tentry,其平均完成時(shí)間AECT表示為:

(8)

在優(yōu)先隊(duì)列劃分的過(guò)程中，通過(guò)判斷整個(gè)DAG任務(wù)圖入口節(jié)點(diǎn)的數(shù)量，借助空隊(duì)列Li，選擇每個(gè)入口節(jié)點(diǎn)，放入空隊(duì)列中單獨(dú)成為一個(gè)隊(duì)列.從入口節(jié)點(diǎn)開(kāi)始遞歸計(jì)算每個(gè)節(jié)點(diǎn)的AECT值，隊(duì)列中選擇節(jié)點(diǎn)時(shí)按以下方式處理：

1)如果節(jié)點(diǎn)ti只有一個(gè)直接前驅(qū)節(jié)點(diǎn)，則直接將該節(jié)點(diǎn)放入其前驅(qū)節(jié)點(diǎn)的隊(duì)列中；

2)如果節(jié)點(diǎn)ti有多個(gè)直接前驅(qū)節(jié)點(diǎn)，即Mpred(ti)>1時(shí)，則該節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，比較其前驅(qū)節(jié)點(diǎn)的AECT值，將節(jié)點(diǎn)放入AECT值最大的節(jié)點(diǎn)隊(duì)列中.

關(guān)鍵節(jié)點(diǎn)根據(jù)其前驅(qū)節(jié)點(diǎn)的AECT值來(lái)選擇隊(duì)列，將復(fù)雜度較高的任務(wù)圖劃分成低復(fù)雜度的隊(duì)列，提高任務(wù)間的并行性.本文提出PQDSA算法的隊(duì)列劃分階段偽代碼如算法1所示.

算法1.隊(duì)列劃分算法

Queue dividing algorithm

Input：并行任務(wù)集G={T，E，W，C}

空隊(duì)列Li(i=1，2，…，n)，n為入口節(jié)點(diǎn)的數(shù)量

Output：優(yōu)先隊(duì)列劃分結(jié)果

1.從入口節(jié)點(diǎn)開(kāi)始，向下遍歷計(jì)算所有任務(wù)節(jié)點(diǎn)AECT值.

2.forti=t1totn

3.ifMpred(ti)==0

4. 借助空隊(duì)列Li，將該節(jié)點(diǎn)放入空隊(duì)列中

5.elseifMpred(ti)==1

6. 直接將給節(jié)點(diǎn)放入其前驅(qū)節(jié)點(diǎn)所在隊(duì)列

7.else

8. 比較其直接前驅(qū)節(jié)點(diǎn)的AECT值

9. 將節(jié)點(diǎn)放入AECT值最大的節(jié)點(diǎn)所在隊(duì)列

10.endif

11.endfor

任務(wù)劃分隊(duì)列結(jié)果如圖3所示.

在算法1中，步驟1指從入口節(jié)點(diǎn)開(kāi)始遍歷每個(gè)節(jié)點(diǎn)，并計(jì)算每個(gè)節(jié)點(diǎn)的AECT值.步驟3-10實(shí)現(xiàn)節(jié)點(diǎn)根據(jù)隊(duì)列劃分條件選擇優(yōu)先隊(duì)列，直至所有節(jié)點(diǎn)都在隊(duì)列中.

圖3 任務(wù)優(yōu)先隊(duì)列劃分結(jié)果Fig.3 Task priority queue division results

為了詳細(xì)地說(shuō)明隊(duì)列的劃分過(guò)程，圖3所示為優(yōu)先隊(duì)列劃分的實(shí)例化例子.由給定的DAG任務(wù)圖2可知，圖中有兩個(gè)入口節(jié)點(diǎn)T1和T2，需要借助兩個(gè)空隊(duì)列L1和L2，將入口節(jié)點(diǎn)放入對(duì)應(yīng)的空隊(duì)列中，即L1={T1}、L2={T2}.圖中節(jié)點(diǎn)T7有三個(gè)直接前驅(qū)節(jié)點(diǎn)，則該節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，計(jì)算其直接前驅(qū)節(jié)點(diǎn)的AECT值，將節(jié)點(diǎn)T7加入AECT值最大的隊(duì)列中，因此將T7加入隊(duì)列L2中.初步得到隊(duì)列L1和隊(duì)列L2，最后檢查生成的優(yōu)先隊(duì)列，隊(duì)列L1存在兩個(gè)出口節(jié)點(diǎn)T8和T9，則添加一個(gè)零計(jì)算開(kāi)銷和零通信開(kāi)銷的偽節(jié)點(diǎn)作為隊(duì)列L1的唯一出口節(jié)點(diǎn).最終劃分得到的兩個(gè)優(yōu)先隊(duì)列分別為L(zhǎng)1={T1,T3,T6,T8,T9}、L2={T2,T4,T5,T7,T10}.

3.2 優(yōu)先級(jí)選擇階段

由入口節(jié)點(diǎn)數(shù)量確定優(yōu)先隊(duì)列的數(shù)目，根據(jù)通信開(kāi)銷和平均計(jì)算開(kāi)銷將節(jié)點(diǎn)添加到隊(duì)列中，從而提高任務(wù)間的并行性.由于關(guān)鍵節(jié)點(diǎn)的存在，隊(duì)列間的數(shù)據(jù)依賴并沒(méi)有完全消失.在確定任務(wù)集的調(diào)度順序時(shí)，需要對(duì)隊(duì)列中的所有任務(wù)節(jié)點(diǎn)計(jì)算TL(ti)值來(lái)確定任務(wù)的優(yōu)先級(jí).處理器對(duì)任務(wù)進(jìn)行調(diào)度時(shí)，首先要考慮當(dāng)前調(diào)度中是否存在關(guān)鍵節(jié)點(diǎn)任務(wù)，如果關(guān)鍵節(jié)點(diǎn)任務(wù)的前驅(qū)節(jié)點(diǎn)尚未調(diào)度，那么需要先調(diào)度其前驅(qū)節(jié)點(diǎn)再執(zhí)行下一步.倘若該節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，則表示該節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)個(gè)數(shù)Mpred(ti)多于一個(gè).倘若節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)都來(lái)自同一隊(duì)列，那么直接調(diào)度該關(guān)鍵節(jié)點(diǎn).倘若其直接前驅(qū)節(jié)點(diǎn)有來(lái)自其他隊(duì)列的節(jié)點(diǎn)任務(wù)，此時(shí)需要考慮該前驅(qū)節(jié)點(diǎn)是否已調(diào)度、數(shù)據(jù)是否已到達(dá).在確定該前驅(qū)節(jié)點(diǎn)已經(jīng)調(diào)度且數(shù)據(jù)已經(jīng)到達(dá)之后，則該關(guān)鍵節(jié)點(diǎn)可以執(zhí)行調(diào)度.對(duì)TL(ti)值相同的節(jié)點(diǎn)，可采取隨機(jī)方式進(jìn)行調(diào)度.

對(duì)于給定的DAG任務(wù)圖2，根據(jù)入口節(jié)點(diǎn)劃分兩個(gè)優(yōu)先隊(duì)列的實(shí)例圖如圖3所示.在任務(wù)的優(yōu)先級(jí)選擇階段，首先計(jì)算優(yōu)先隊(duì)列L1和L2中節(jié)點(diǎn)的TL(ti)值，然后將優(yōu)先隊(duì)列中節(jié)點(diǎn)根據(jù)TL(ti)值的大小按照升序排列，得到實(shí)例化優(yōu)先隊(duì)列L1和L2，對(duì)應(yīng)的節(jié)點(diǎn)集合分別為{T1,T3,T6,T8,T9}、{T2,T4,T5,T7,T10}.

3.3 處理器選擇階段

通過(guò)對(duì)任務(wù)劃分優(yōu)先隊(duì)列，很大程度上降低了任務(wù)的相關(guān)性，提高了隊(duì)列的并行性，減少了節(jié)點(diǎn)的平均完成時(shí)間.再對(duì)隊(duì)列中的任務(wù)進(jìn)行優(yōu)先級(jí)選擇，生成任務(wù)的拓?fù)漤樞颍_保關(guān)鍵節(jié)點(diǎn)滿足優(yōu)先約束.這一節(jié)的重點(diǎn)是將任務(wù)調(diào)度到合適的處理器上執(zhí)行，進(jìn)一步提前節(jié)點(diǎn)的完成時(shí)間.在DAG任務(wù)圖應(yīng)用程序中，任務(wù)調(diào)度到某個(gè)處理器上執(zhí)行，必須等待其所有前驅(qū)節(jié)點(diǎn)執(zhí)行結(jié)束且相關(guān)數(shù)據(jù)到達(dá)其所在的處理器，該節(jié)點(diǎn)任務(wù)才可以開(kāi)始執(zhí)行調(diào)度.兩個(gè)任務(wù)節(jié)點(diǎn)在同一個(gè)處理器上執(zhí)行時(shí)，其通信開(kāi)銷為零.獲取DAG任務(wù)圖的關(guān)鍵節(jié)點(diǎn)，該關(guān)鍵節(jié)點(diǎn)在同層的節(jié)點(diǎn)中任務(wù)優(yōu)先級(jí)最高.

任務(wù)實(shí)際開(kāi)始時(shí)間(AST)和任務(wù)實(shí)際結(jié)束時(shí)間(AFT)的計(jì)算表達(dá)式為：

AST(tentry)=0

(9)

AST(ti)=AFT(ti)-wij

(10)

(11)

當(dāng)ti與其前驅(qū)節(jié)點(diǎn)tj在同一處理器上執(zhí)行，k=0；當(dāng)ti與其前驅(qū)節(jié)點(diǎn)tj在不同處理器上執(zhí)行時(shí)，k=1.

如果隊(duì)列中任務(wù)都只有一個(gè)直接前驅(qū)節(jié)點(diǎn)，則可以將隊(duì)列中所有任務(wù)分配到同一處理器，此時(shí)沒(méi)有通信開(kāi)銷，也不需要等待其他節(jié)點(diǎn)的數(shù)據(jù).如果任務(wù)直接前驅(qū)節(jié)點(diǎn)任務(wù)多于一個(gè)時(shí)，則該節(jié)點(diǎn)是關(guān)鍵節(jié)點(diǎn)，數(shù)據(jù)最后到達(dá)的前驅(qū)節(jié)點(diǎn)為關(guān)鍵父親節(jié)點(diǎn).

針對(duì)存在關(guān)鍵節(jié)點(diǎn)的任務(wù)隊(duì)列，考慮到關(guān)鍵父親節(jié)點(diǎn)數(shù)據(jù)到達(dá)的時(shí)間，不能直接把所有任務(wù)分配到同一臺(tái)處理器上執(zhí)行.本算法采用基于插入的思想，在處理器上足夠大的時(shí)間槽空隙中插入任務(wù).對(duì)于隊(duì)列中非入口節(jié)點(diǎn)，但沒(méi)有直接后繼任務(wù)，可以將其單獨(dú)放置于單獨(dú)的處理器，給其他節(jié)點(diǎn)任務(wù)釋放空間，進(jìn)一步減少最終完成時(shí)間.PQDSA的全部偽代碼如算法2所示.

算法2.PQDSA算法

PQDSA algorithm

Input：并行任務(wù)集G={T,E,W,C}，

空隊(duì)列Li(i=1，2，…，n)，n為入口節(jié)點(diǎn)的數(shù)量

Output：DAG任務(wù)集的調(diào)度結(jié)果

1.從入口節(jié)點(diǎn)開(kāi)始，向下遍歷計(jì)算所有任務(wù)節(jié)點(diǎn)的AECT值.

2.forti=t1totn

3. 滿足劃分隊(duì)列條件

4. 產(chǎn)生劃分結(jié)果，隊(duì)列L1，L2…

5.endfor

6.從每個(gè)隊(duì)列的入口節(jié)點(diǎn)開(kāi)始,向下遍歷計(jì)算每個(gè)節(jié)點(diǎn)的TL(ti)值.

7.whileLi非空do

8. 按TL(ti)值升序排列

9.ifTL(ti)=TL(tj)

10. 隨機(jī)排序

11. 生成優(yōu)先級(jí)隊(duì)列

12.endif

13.end

14.whileLi非空do

15. 隊(duì)頭節(jié)點(diǎn)ti從隊(duì)列Li中出隊(duì)

16.for處理器集合P中每個(gè)處理器

17. 計(jì)算AST(ti)和AFT(ti)

18. 為節(jié)點(diǎn)選擇AFT(ti)值最小的處理器

19.endfor

20.end

3.4 PQDSA算法時(shí)間復(fù)雜度分析

在將n個(gè)任務(wù)調(diào)度到m個(gè)處理器上任務(wù)調(diào)度環(huán)境中，PQDSA主要包含優(yōu)先隊(duì)列劃分、優(yōu)先級(jí)選擇和處理器選擇三個(gè)部分，對(duì)這三個(gè)部分進(jìn)行分析可得到算法總時(shí)間復(fù)雜度.

在優(yōu)先隊(duì)列劃分階段，DAG圖中邊之間的約束關(guān)系選擇鏈表方式進(jìn)行存儲(chǔ)，該階段的時(shí)間復(fù)雜度為O(n+p)，其中n為DAG圖節(jié)點(diǎn)數(shù)量，p為處理器的數(shù)目.在優(yōu)先級(jí)選擇階段，計(jì)算節(jié)點(diǎn)TL(ti)值，其時(shí)間復(fù)雜度為O(n2).最后在處理器選擇階段，計(jì)算節(jié)點(diǎn)調(diào)度到每個(gè)處理器上的AST(ti)值和AFT(ti)值，在將任務(wù)調(diào)度到AFT(ti)值最小的處理器上，其時(shí)間復(fù)雜度為O(n2×p).由此可知，PQDSA算法的時(shí)間復(fù)雜度為O(n2×p).

3.5 PQDSA算法調(diào)度實(shí)例分析

首先使用圖2的實(shí)例化DAG任務(wù)圖進(jìn)行分析以及對(duì)比調(diào)度長(zhǎng)度，然后在劃分優(yōu)先隊(duì)列數(shù)量進(jìn)行性能對(duì)比，以及節(jié)點(diǎn)數(shù)量不同和劃分優(yōu)先隊(duì)列數(shù)不同的情況下，來(lái)進(jìn)行實(shí)驗(yàn)比較分析.DAG實(shí)例化三個(gè)算法的調(diào)度長(zhǎng)度對(duì)比圖如圖4所示.

圖4 三個(gè)算法的調(diào)度過(guò)程Fig.4 Scheduling process of three algorithms

針對(duì)圖2給出的實(shí)例化DAG任務(wù)圖，圖4為HEFT算法、PTSAC算法和PQDSA算法的調(diào)度效果.HEFT算法對(duì)節(jié)點(diǎn)任務(wù)進(jìn)行優(yōu)先級(jí)排序，再采用基于插入策略將節(jié)點(diǎn)調(diào)度到處理器上.PTSAC算法通過(guò)通信開(kāi)銷和計(jì)算開(kāi)銷來(lái)確定相關(guān)性，判斷是否進(jìn)行復(fù)制.本文提出的算法PQDSA首先通過(guò)入口節(jié)點(diǎn)的數(shù)量來(lái)確定劃分優(yōu)先隊(duì)列數(shù)，由圖2可知，有T1和T2兩個(gè)入口節(jié)點(diǎn)，因此可以劃分兩個(gè)優(yōu)先隊(duì)列L1和L2，將復(fù)雜多樣的DAG任務(wù)圖劃分成兩個(gè)相關(guān)性低的優(yōu)先隊(duì)列.然后按照節(jié)點(diǎn)劃分隊(duì)列的要求，將節(jié)點(diǎn)都放入到合適的隊(duì)列中，如圖3所示，生成最后的優(yōu)先隊(duì)列L1和L2.最后再將隊(duì)列中的任務(wù)調(diào)度到處理器上.由圖4可知，三個(gè)算法的調(diào)度長(zhǎng)度分別為16、16和14，本文提出的算法的調(diào)度長(zhǎng)度要比HEFT算法和PTSAC算法縮短了2個(gè)單位，相當(dāng)于makespan降低了12.5%.

4 實(shí)驗(yàn)部分

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文提出的PQDSA算法的可行性和有效性，以及避免因?qū)嶒?yàn)環(huán)境不同和對(duì)比的算法產(chǎn)生性能上的差異.本文采用相同的實(shí)驗(yàn)環(huán)境來(lái)進(jìn)行對(duì)比.實(shí)驗(yàn)中使用Intel Core(TM)i5-9300H@ 2.40GHz四核處理器，16 GB內(nèi)存，python版本為3.7，系統(tǒng)運(yùn)行環(huán)境為Windows 10.

4.2 實(shí)驗(yàn)結(jié)果分析

本文主要采用調(diào)度長(zhǎng)度(makespan)和調(diào)度效率(Efficiency)兩個(gè)參數(shù)作為衡量算法的性能指標(biāo)，并選取HEFT算法和PTSAC算法來(lái)進(jìn)行實(shí)驗(yàn)對(duì)比分析.PQDSA算法的輸入為DAG任務(wù)圖，算法的輸出為DAG任務(wù)圖的調(diào)度結(jié)果.

4.2.1 任務(wù)調(diào)度長(zhǎng)度

PQDSA算法主要側(cè)重于任務(wù)調(diào)度長(zhǎng)度，基于調(diào)度長(zhǎng)度從兩個(gè)方面進(jìn)行實(shí)驗(yàn).第一組實(shí)驗(yàn)是劃分優(yōu)先隊(duì)列數(shù)不同時(shí)的調(diào)度長(zhǎng)度比較，第二組實(shí)驗(yàn)是DAG節(jié)點(diǎn)數(shù)量不同時(shí)的調(diào)度長(zhǎng)度比較，分別如圖5、圖6所示.圖5分別為劃分2、4、6、8、10個(gè)優(yōu)先隊(duì)列時(shí)3個(gè)算法的調(diào)度長(zhǎng)度對(duì)比，圖6為DAG節(jié)點(diǎn)數(shù)量分別為10、20、30、40、50時(shí)3個(gè)算法的對(duì)比情況.

圖5 劃分隊(duì)列數(shù)不同時(shí)三種算法調(diào)度長(zhǎng)度對(duì)比Fig.5 Makespan comparison of three algorithms withdifferent queue numbers

圖5的橫坐標(biāo)為劃分優(yōu)先隊(duì)列數(shù)，是指由入口節(jié)點(diǎn)的數(shù)量來(lái)確定的優(yōu)先隊(duì)列數(shù)量，縱坐標(biāo)為算法所需要的調(diào)度長(zhǎng)度值.從實(shí)驗(yàn)數(shù)據(jù)對(duì)比可以得出，在任務(wù)調(diào)度時(shí)間長(zhǎng)度方面，PQDSA算法的調(diào)度時(shí)間比HEFT算法和PTSAC算法要低，隨著優(yōu)先隊(duì)列數(shù)的增加差距愈發(fā)明顯.PQDSA算法根據(jù)入口節(jié)點(diǎn)對(duì)任務(wù)進(jìn)行劃分優(yōu)先隊(duì)列，將關(guān)鍵節(jié)點(diǎn)任務(wù)放入合適的隊(duì)列中.在任務(wù)調(diào)度之前提高任務(wù)的并行性，降低節(jié)點(diǎn)間的時(shí)間消耗，隨著優(yōu)先隊(duì)列數(shù)的增加，PQDSA算法的優(yōu)勢(shì)愈發(fā)顯著.由實(shí)驗(yàn)數(shù)據(jù)可以得出，在劃分優(yōu)先隊(duì)列數(shù)時(shí)調(diào)度長(zhǎng)度方面，PQDSA算法比HEFT算法最高降低了22.5%，最低縮短了1.3%；PQDSA算法比PTSAC算法最高降低了18.6%，最低縮短了8.4%.

圖6 不同DAG節(jié)點(diǎn)數(shù)量三種算法調(diào)度長(zhǎng)度對(duì)比Fig.6 Makespan comparison of three algorithms withdifferent number of DAG nodes

圖6中橫坐標(biāo)為DAG任務(wù)圖的節(jié)點(diǎn)數(shù)量，縱坐標(biāo)為調(diào)度長(zhǎng)度.由圖6的實(shí)驗(yàn)結(jié)果對(duì)比圖可知，隨著DAG中節(jié)點(diǎn)數(shù)量的增加，HEFT、PTSAC和PQDSA算法的調(diào)度長(zhǎng)度變化并不明顯.當(dāng)節(jié)點(diǎn)數(shù)為10時(shí)，HEFT、PTSAC和PQDSA算法的調(diào)度長(zhǎng)度差距并不明顯；當(dāng)節(jié)點(diǎn)數(shù)為20時(shí)，PQDSA算法的調(diào)度長(zhǎng)度要明顯低于HEFT和PTSAC算法.隨著DAG中節(jié)點(diǎn)數(shù)量的增加，與HEFT和PTSAC相比，PQDSA算法在降低調(diào)度長(zhǎng)度方面的優(yōu)勢(shì)愈發(fā)明顯.當(dāng)節(jié)點(diǎn)數(shù)為50時(shí)，PQDSA算法的調(diào)度長(zhǎng)度要明顯低于HEFT和PTSAC算法.當(dāng)節(jié)點(diǎn)數(shù)量為10時(shí)，PQDSA算法只比HEFT算法和PTSAC算法降低了2個(gè)單位.節(jié)點(diǎn)數(shù)量為30時(shí)，PQDSA算法分別比HEFT算法和PTSAC算法縮短了3個(gè)單位和12個(gè)單位.當(dāng)節(jié)點(diǎn)數(shù)量達(dá)到50時(shí)，PQDSA算法分別比HEFT算法和PTSAC算法減少了6個(gè)單位和7個(gè)單位.由實(shí)驗(yàn)數(shù)據(jù)不難得出，當(dāng)DAG任務(wù)節(jié)點(diǎn)數(shù)量不同時(shí)，在任務(wù)調(diào)度長(zhǎng)度方面，PQDSA算法要優(yōu)于前兩種算法.

4.2.2 調(diào)度效率

為了進(jìn)一步驗(yàn)證PQDSA算法的性能，分別采用3種算法對(duì)DAG圖進(jìn)行調(diào)度，選擇調(diào)度效率作為算法性能測(cè)試指標(biāo).針對(duì)優(yōu)先隊(duì)列數(shù)和DAG節(jié)點(diǎn)數(shù)量進(jìn)行兩組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果分別如圖7、圖8所示.

圖7 劃分隊(duì)列數(shù)量不同時(shí)三種算法調(diào)度效率對(duì)比Fig.7 Comparison of scheduling efficiency of three algorithmswith different queue numbers

圖8 不同DAG節(jié)點(diǎn)數(shù)量時(shí)三種算法調(diào)度效率對(duì)比Fig.8 Comparison of scheduling efficiency of three algorithmswith different number of DAG nodes

圖7和圖8的縱坐標(biāo)均為算法的調(diào)度效率，圖7的橫坐標(biāo)為劃分優(yōu)先隊(duì)列數(shù)量，圖8的橫坐標(biāo)為DAG節(jié)點(diǎn)數(shù)量.圖7為優(yōu)先隊(duì)列數(shù)分別為2、4、6、8、10時(shí)的調(diào)度效率對(duì)比.圖8展示了DAG中節(jié)點(diǎn)數(shù)量分別為10、20、30、40、50時(shí)的調(diào)度效率實(shí)驗(yàn)結(jié)果對(duì)比.由圖7的實(shí)驗(yàn)數(shù)據(jù)對(duì)比分析可以得出，在算法調(diào)度效率方面，PQDSA算法都要優(yōu)于HEFT和PTSAC算法.當(dāng)劃分的優(yōu)先隊(duì)列數(shù)分別為2、4、6時(shí)，PQDSA算法相對(duì)于HEFT算法提高并不明顯，相對(duì)于PTSAC算法改善更為顯著，尤其當(dāng)優(yōu)先隊(duì)列為6時(shí).當(dāng)優(yōu)先隊(duì)列數(shù)達(dá)到8或者10時(shí)，PQDSA算法明顯優(yōu)于HEFT算法.因此，我們可以得出結(jié)論，PQDSA算法特別適合優(yōu)先隊(duì)列數(shù)較多的DAG圖.由圖7的實(shí)驗(yàn)數(shù)據(jù)對(duì)比可知，在劃分優(yōu)先隊(duì)列數(shù)不同時(shí)，PQDSA算法在調(diào)度效率方面比HEFT算法最高提升了5.76%，最低增加了1.33%.比PTSAC算法最高提升了15.47%，最低增加了5.87%.由圖8的實(shí)驗(yàn)數(shù)據(jù)可以得出，當(dāng)DAG節(jié)點(diǎn)數(shù)量不同時(shí)，PQDSA算法在調(diào)度效率方面比HEFT算法最高提高了11.23%，最低改善了4.13%.比PTSAC算法最高提高了13.82%，最低增加了5.31%.由圖7和圖8的實(shí)驗(yàn)結(jié)果分析對(duì)比不難得出，PQDSA算法調(diào)度效率要優(yōu)于對(duì)比的兩種算法.其主要原因在于PQDSA算法采取劃分優(yōu)先隊(duì)列的方法，將關(guān)鍵節(jié)點(diǎn)放置于合適的隊(duì)列，再將任務(wù)分配到完成時(shí)間最小的處理器上，使得每一步都在降低任務(wù)的最晚完成時(shí)間.從整體上提高任務(wù)的并行性，減小任務(wù)的調(diào)度時(shí)間，提升任務(wù)的調(diào)度效率.

通過(guò)四組實(shí)驗(yàn)分析對(duì)比得出，PQDSA算法在調(diào)度長(zhǎng)度以及算法的調(diào)度效率兩個(gè)方面均優(yōu)于HEFT算法和PTSAC算法.在任務(wù)調(diào)度長(zhǎng)度方面最大分別降低了22.5%和18.6%，在調(diào)度效率方面最大分別提高了11.23%和15.47%.PQDSA算法在調(diào)度長(zhǎng)度以及調(diào)度效率等方面，均呈現(xiàn)比較理想的效果.

5 總 結(jié)

云計(jì)算和人工智能的高速發(fā)展，邊緣設(shè)備數(shù)量的劇增，這對(duì)高性能計(jì)算提出了更高的要求.異構(gòu)環(huán)境下的任務(wù)調(diào)度問(wèn)題是高性能計(jì)算中的研究重點(diǎn).本文通過(guò)對(duì)DAG任務(wù)調(diào)度模型的研究，針對(duì)復(fù)雜多樣的DAG任務(wù)圖，本文提出一種基于優(yōu)先隊(duì)列劃分的調(diào)度算法(PQDSA).PQDSA算法針對(duì)多入口多出口節(jié)點(diǎn)的任務(wù)圖，根據(jù)入口節(jié)點(diǎn)采用劃分優(yōu)先隊(duì)列的方法，將高復(fù)雜度、低并行性的節(jié)點(diǎn)任務(wù)劃分成單獨(dú)的隊(duì)列.對(duì)于關(guān)鍵任務(wù)節(jié)點(diǎn)與其直接前驅(qū)節(jié)點(diǎn)存在依賴關(guān)系，劃分隊(duì)列時(shí)利用節(jié)點(diǎn)的平均完成時(shí)間將關(guān)鍵節(jié)點(diǎn)放入合適的隊(duì)列，降低任務(wù)的時(shí)間消耗.實(shí)驗(yàn)結(jié)果的分析對(duì)比表明，PQDSA算法在調(diào)度長(zhǎng)度和調(diào)度效率方面明顯優(yōu)于HEFT算法和PTSAC算法.