一種使用改進(jìn)預(yù)測成本矩陣任務(wù)優(yōu)先排序的異構(gòu)計(jì)算系統(tǒng)列表調(diào)度算法

姚 宇 宋宇鯤 楊國偉 黃 英 張多利

(合肥工業(yè)大學(xué)微電子學(xué)院 合肥 230601)

1 引言

異構(gòu)計(jì)算系統(tǒng)可以將應(yīng)用程序分配在多個(gè)處理器上執(zhí)行，并且通過處理器間的互聯(lián)網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)通信，應(yīng)用程序在系統(tǒng)上的并行計(jì)算大幅提高了執(zhí)行效率。異構(gòu)計(jì)算系統(tǒng)通常由不同的處理器以及連接各個(gè)處理器的網(wǎng)絡(luò)組成。不同任務(wù)在相同處理器上的執(zhí)行時(shí)間一般是不同的，而且，由于處理器的異構(gòu)性，相同任務(wù)在不同處理器上的執(zhí)行時(shí)間一般也是不同的。

應(yīng)用程序表示為有向無環(huán)圖(Directed Acyclic Graph, DAG)[1]，描述了應(yīng)用程序的屬性，例如每個(gè)任務(wù)在不同處理器上的執(zhí)行時(shí)間，任務(wù)之間的數(shù)據(jù)依賴關(guān)系以及通信時(shí)間。

異構(gòu)列表調(diào)度的目標(biāo)是將應(yīng)用程序分配到異構(gòu)計(jì)算系統(tǒng)的處理器上。在這個(gè)過程中，需要考慮不同任務(wù)在不同處理器上執(zhí)行時(shí)間的不同以及通信時(shí)間不同的問題。該問題是一個(gè)非確定多項(xiàng)式時(shí)間(Nondeterministic Polynomial-time, NP)完全問題[2-4]。在多項(xiàng)式時(shí)間內(nèi)獲得最調(diào)度方案幾乎是不可能的，于是如何在多項(xiàng)式時(shí)間內(nèi)產(chǎn)生較好的調(diào)度方案，成為相關(guān)工作的熱點(diǎn)研究內(nèi)容。

對于此問題，很多相關(guān)工作采用了啟發(fā)式算法。這些啟發(fā)式算法主要分為3類，包括基于聚類的啟發(fā)式算法[5-7]、基于復(fù)制的啟發(fā)式算法[8-10]和基于列表的啟發(fā)式算法[11-22]。

相關(guān)工作中的基于啟發(fā)式的列表調(diào)度算法將問題求解的搜索空間縮小，在降低了時(shí)間復(fù)雜度的基礎(chǔ)上獲得較好的解。為了下文的說明，現(xiàn)令DAG中任務(wù)數(shù)量為 tn，異構(gòu)計(jì)算系統(tǒng)中處理器數(shù)量為p n。

異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time, HEFT)[11]算法具有O(pn·tn2)的時(shí)間復(fù)雜度。它在任務(wù)優(yōu)先級排序階段使用 r ankμ作為依據(jù)，該值表示了一個(gè)任務(wù)到出口任務(wù)的最長路徑。在處理器選擇階段，它為任務(wù)選擇獲得最早完成時(shí)(Earliest Finish Time, EFT)的處理器。但是其只根據(jù)單個(gè)任務(wù)的計(jì)算屬性來選擇處理器，忽略了對后繼任務(wù)帶來的不利后果。

前瞻(lookahead)[12]算法針對HEFT的缺點(diǎn)進(jìn)行了改進(jìn)。在任務(wù)優(yōu)先級排序階段，前瞻使用rankμ作為排序依據(jù)。在處理器選擇階段，它會(huì)對當(dāng)前任務(wù)的后繼任務(wù)的處理器選擇進(jìn)行預(yù)測，并傾向于選擇能使當(dāng)前任務(wù)的所有后繼任務(wù)在所有處理器的最大EFT最小化的處理器。但是，前瞻算法的時(shí)間復(fù)雜度增加到O(pn3·tn4)。

預(yù)測最早完成時(shí)間(Predict Earliest Finish Time, PEFT)[13]算法通過計(jì)算樂觀成本表(Optimistic Cost Table, O CT)作為算法中抉擇的關(guān)鍵依據(jù)，在保持O(pn·tn2)的復(fù)雜度的基礎(chǔ)上，適用了前瞻特性，并且相比HEFT有較大的性能提升。用于任務(wù)優(yōu)先級排序階段的 r ankOCT沒有考慮當(dāng)前任務(wù)在處理上的計(jì)算消耗成本，導(dǎo)致優(yōu)先級列表的預(yù)測準(zhǔn)確性不佳。

預(yù)測優(yōu)先任務(wù)調(diào)度(Predict Priority Task Scheduling, PPTS)[14]算法使用預(yù)測成本矩陣(Predict Cost Matrix, P CM ) 替代O CT，同時(shí)考慮了當(dāng)前任務(wù)和直接后繼任務(wù)的計(jì)算消耗，能夠更好地預(yù)測任務(wù)的執(zhí)行，保持了O(pn·tn2)的時(shí)間復(fù)雜度，性能比PEFT有進(jìn)一步的提升。但是，由于P CM中考慮的是當(dāng)前任務(wù)在直接后繼任務(wù)處理器上的計(jì)算消耗，做出的預(yù)測偏向于產(chǎn)生相鄰任務(wù)在同一處理器上執(zhí)行的局部最優(yōu)解。而且，PPTS在處理器選擇階段使用P CM也會(huì)導(dǎo)致同樣的問題。PPTS的作者又提出了增強(qiáng)的預(yù)測優(yōu)先任務(wù)調(diào)度(Improved Predict Priority Task Scheduling, IPPTS)[22]，通過在優(yōu)先級排序階段考慮了任務(wù)的出度，在大任務(wù)數(shù)量應(yīng)用中獲得了提升，但其仍未完全解決其使用PCM所帶來的問題。

總體來說，此類型的相關(guān)工作中，設(shè)計(jì)用于任務(wù)優(yōu)先級排序或處理器選擇的預(yù)測列表或矩陣仍有不合理之處，不能充分發(fā)揮異構(gòu)計(jì)算系統(tǒng)的性能。

本文針對異構(gòu)列表調(diào)度問題，提出一種新的具有2次時(shí)間復(fù)雜度的調(diào)度算法，稱為改進(jìn)的預(yù)測優(yōu)先任務(wù)和樂觀處理器選擇調(diào)度(Improved Predict Priority and Optimistic processor Selection Scheduling, IPPOSS)。IPPOSS優(yōu)于PPTS和PEFT并且保持2次復(fù)雜度。該算法是在PPTS和PEFT基礎(chǔ)上的改進(jìn)，同樣具有任務(wù)優(yōu)先級排序和處理器選擇兩個(gè)階段，并且具有前瞻的特性。與PPTS和PEFT相比，IPPOSS計(jì)算改進(jìn)預(yù)測成本矩陣(Improved Predict Cost Matrix, IPCM)，該矩陣中的每個(gè)元素表示為特定任務(wù)選擇特定處理器時(shí)的執(zhí)行成本的預(yù)計(jì)值。然后計(jì)算任務(wù)優(yōu)先級rankIPCM，也就是任務(wù)在不同處理器上的I PCM值的均值，然后使用r ankIPCM對任務(wù)進(jìn)行排序。在處理器選擇階段，基于實(shí)驗(yàn)結(jié)果，IPPOSS使用基于EFTOCT[13]的處理器選擇策略。但是由于任務(wù)優(yōu)先級排序階段使用了更好的方法，IPPOSS產(chǎn)生了與PEFT完全不同的處理器選擇結(jié)果。隨機(jī)生成的應(yīng)用圖和真實(shí)世界的應(yīng)用圖的實(shí)驗(yàn)結(jié)果分析表明，IPPOSS的性能優(yōu)于現(xiàn)有相關(guān)算法。

2 調(diào)度問題模型

調(diào)度模型用于應(yīng)用程序到計(jì)算系統(tǒng)上的調(diào)度，并且達(dá)到一定的性能指標(biāo)。一般來說任務(wù)調(diào)度的主要目的是獲得最小調(diào)度長度，也稱為m akespan。

調(diào)度模型中的應(yīng)用描述為一種 D AG=(T,E)，如圖1和表1所示。T是節(jié)點(diǎn)的集合，任意ti ∈T表示DAG中的一個(gè)任務(wù)。E是有向邊e的集合，任意ei,j ∈E表示DAG中的一次通信，也就是任務(wù)ti到

表1 計(jì)算消耗

圖1 具有10 任務(wù)和3 處理器的任務(wù)以及計(jì)算消耗

任意通信ei,j在計(jì)算系統(tǒng)網(wǎng)絡(luò)中傳輸所消耗的時(shí)間表示為ci,j。 由于ci,j必 須要在執(zhí)行ti和tj的處理器被確定的情況下才能計(jì)算出，而靜態(tài)列表調(diào)度以通信消耗作為輸入?yún)?shù)，必須提前預(yù)知該值，所以一般的做法是，使用平均通信時(shí)間ci,j來 表示ei,j的時(shí)間消耗。當(dāng)ti和tj被分配在不同處理器上時(shí)，ci,j的計(jì)算方法為

其中，l表示所有處理器的平均延遲，也就是平均傳輸啟動(dòng)時(shí)間。b表示所有處理器之間的平均帶寬。Di,j表示在本次通信中ti需要傳輸?shù)絫j的數(shù)據(jù)量。ci,j表示了平均傳輸啟動(dòng)時(shí)間和特定量的數(shù)據(jù)在傳輸開始后到傳輸結(jié)束所消耗時(shí)間的和。如果ti和tj被分配在同一個(gè)處理器上，它們之間不需要通過網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)傳輸，則ci,j為0。tj的通信。通信ei,j也 表示了任務(wù)ti和tj間的數(shù)據(jù)依賴關(guān)系。任務(wù)ti被稱為tj的直接前驅(qū)任務(wù)，任務(wù)tj被稱為ti的直接后繼任務(wù)。通信消耗標(biāo)注于圖1的對應(yīng)邊上，計(jì)算消耗標(biāo)注于表1，因系統(tǒng)為異構(gòu)架構(gòu)，任務(wù)在不同的處理器上具有不同計(jì)算消耗。

調(diào)度模型中的計(jì)算系統(tǒng)包含處理器的集合P。本文的調(diào)度模型中，應(yīng)用程序在計(jì)算系統(tǒng)上的執(zhí)行過程進(jìn)行了一些假設(shè)：1個(gè)任務(wù)指令必須在計(jì)算系統(tǒng)中的1個(gè)處理器上執(zhí)行；多個(gè)處理器可以同時(shí)執(zhí)行不同任務(wù)；任務(wù)在處理器上的執(zhí)行不會(huì)發(fā)生爭用；任意兩個(gè)處理器之間都通過網(wǎng)絡(luò)連接并且能進(jìn)行數(shù)據(jù)傳輸；任意兩次通信之間不會(huì)發(fā)生干擾。

任務(wù)ti在 處理器pm上 的計(jì)算時(shí)間表示為W(ti,pm)。它的行數(shù)是DAG中任務(wù)數(shù)量 tn，列數(shù)是計(jì)算系統(tǒng)中處理器數(shù)量 pn。因?yàn)楸疚挠懻摰氖钱悩?gòu)計(jì)算系統(tǒng)，所以對于相同的ti以及不同的pm，W(ti,pm)也具有不同的值。平均計(jì)算時(shí)間表示了不指定處理器的情況下，執(zhí)行任務(wù)ti預(yù)計(jì)所花費(fèi)時(shí)間，表示為

3 IPPOSS算法

IPPOSS包含兩個(gè)階段，分別為任務(wù)優(yōu)先級排序階段和處理器選擇階段。改進(jìn)預(yù)測成本矩陣被用于任務(wù)優(yōu)先級排序階段，本節(jié)首先介紹它的定義和計(jì)算方法。

3.1 改進(jìn)預(yù)測成本矩陣

IPPOSS的任務(wù)優(yōu)先級排序階段基于改進(jìn)預(yù)測成本矩陣，是對PPTS[14]中的P CM的改進(jìn)。每個(gè)元素IPCM(ti,pm)代 表任務(wù)ti選 擇在pm上執(zhí)行時(shí)，任務(wù)ti到 出口任務(wù)的最短路徑的預(yù)計(jì)最大值。IPCM中的所有元素通過遞歸的過程計(jì)算，計(jì)算過程開始于出口任務(wù)，并向上遍歷所有的任務(wù)，結(jié)束于入口任務(wù)。I PCM(ti,pm)的計(jì)算公式為

其中，W(ti,pm)表 示ti在pm上執(zhí)行的異構(gòu)運(yùn)算時(shí)間。 succ(ti) 表示ti的所有直接后繼任務(wù)的集合。P表示所有處理器的集合。ci,j表 示ti到tj的平均通信時(shí)間。當(dāng)ti和tj在同一個(gè)處理器上運(yùn)行時(shí)，也就是pm=pn時(shí)，ci,j=0。W(tj,pn)表示直接后繼任務(wù)tj在pn上 執(zhí)行的異構(gòu)運(yùn)算時(shí)間。當(dāng)ti為texit，也就是出口任務(wù)時(shí)，有 succ(ti)=? ，IPCM(ti,pm)=W(texit,pm) 。IPCM(ti,pm)不僅考慮了直接后繼任務(wù)tj在可以獲取最小計(jì)算、通信時(shí)間之和的處理器上執(zhí)行的時(shí)間消耗，而且考慮了當(dāng)前任務(wù)ti在選擇的處理器pm上 的時(shí)間消耗，所以，I PCM(ti,pm)表示了ti選 擇在pm上 執(zhí)行時(shí)，任務(wù)ti到出口任務(wù)的最短路徑的預(yù)計(jì)最大值。而PPTS中的P CM沒用使用準(zhǔn)確的當(dāng)前任務(wù)計(jì)算消耗，而是使用了一種近似表示，也就是當(dāng)前任務(wù)在其直接后繼任務(wù)選擇的處理器上的計(jì)算消耗。這導(dǎo)致不能準(zhǔn)確地進(jìn)行調(diào)度預(yù)測，從而限制了調(diào)度性能。

3.2 任務(wù)優(yōu)先級排序階段

IPPOSS的任務(wù)優(yōu)先級排序階段根據(jù)rankIPCM(ti)的元素來進(jìn)行，具有較大的r ankIPCM(ti)的 任務(wù)ti被置于任務(wù)優(yōu)先級列表的前面。r ankIPCM(ti)通過任務(wù)ti在 每個(gè)處理器上的I PCM的平均值求得，定義為

rankIPCM是I PCM 的平均值，所以它能夠反映任務(wù)在調(diào)度列表中的重要程度。對于圖1的DAG1,HEFT, PEFT, PPTS和IPPOSS算法得到了完全不同的任務(wù)優(yōu)先級排序列表。表2給出DAG1的IPCM的所有元素，由表3可以確定4種算法的任務(wù)優(yōu)先級列表?？梢钥闯?，r ankμ與r ankOCT對于T1之后優(yōu)先進(jìn)行的任務(wù)做出了相同的選擇T2，而 rankPCM與rankIPCM則選擇T1,T3和T6作為開始的3個(gè)任務(wù)。rankIPCM與所有3種算法最顯著的不同是，將T7排在了T4和T5的前面，而且從圖1可以看出，這種優(yōu)先級排序是一種“越級”排序，因?yàn)門4和T5是入口任務(wù)T1的直接后繼，而T7則不是。對于DAG1，使用r ankIPCM相比其他3種算法的r ank，更具有在全局范圍內(nèi)調(diào)整任務(wù)優(yōu)先級列表順序的能力，而不是按照DAG1中每個(gè)任務(wù)的分級僅在局部進(jìn)行優(yōu)先級順序的調(diào)整，這使得IPPOSS可以獲得更好的調(diào)度性能。

表2 圖 1 中 DAG1 的 IPCM

表3 圖 1 中 DAG1 的各算法任務(wù)優(yōu)先級列表

3.3 處理器選擇階段

IPPOSS的處理器選擇階段沒有使用E FTIPCM。通過隨機(jī)生成的應(yīng)用圖實(shí)驗(yàn)發(fā)現(xiàn)，雖然在兩個(gè)階段中都使用I PCM，會(huì)獲得優(yōu)于PEFT和PPTS的解，但是如果在處理器選擇階段使用E FTOCT，則會(huì)獲得更好的解。表4給出了基于 E FTIPCM的處理器選擇策略的IPPOSS與PEFT, PPTS和基于E FTOCT的處理器選擇策略的IPPOSS的調(diào)度長度率(Scheduling Length Ratio, SLR)對比，可以看出，雖然基于EFTIPCM處理器選擇策略的IPPOSS比PEFT降低了1.75%的平均S LR，并且有57.5%的樣本獲得了更低調(diào)度長度，但是相比于PPTS，該方法并沒有明顯的提升。而基于E FTOCT處理器選擇策略的IPPOSS的平均SLR進(jìn)一步降低，此外，樣本的成對調(diào)度長度對比結(jié)果也有進(jìn)一步的優(yōu)化。

表4 不同方法的SLR對比(%)

基于實(shí)驗(yàn)結(jié)果，IPPOSS在處理器選擇階段使用PEFT中的方法，也就是選擇具有最小E FTOCT[13]的處理器，E FTOCT的計(jì)算公式為

一些相關(guān)工作[11,13,14]在處理器選擇階段使用了基于插入的(insertion-based)策略。它們在調(diào)度中可以通過充分利用處理器上的空閑時(shí)間槽，減少總體調(diào)度時(shí)間?？紤]算法對比的公平性，本文同樣使用該策略。

3.4 IPPOSS算法詳細(xì)描述

IPPOSS算法的細(xì)節(jié)如算法1所示。

算法1 IPPOSS算法

IPPOSS首先計(jì)算I PCM, O CT( 第1行)和rankIPCM(第2行)。然后，通過查找未分配處理器且所有直接前驅(qū)任務(wù)都已經(jīng)分配處理器的任務(wù)來更新就緒列表(第3行)。接著，為就緒列表中具有最高rankIPCM(ti)的任務(wù)ti分 配處理器，以獲得最小的EFTOCT(ti,pm)(第4～10行)，并更新L istready(第11行)。最后，如果更新后的就緒列表為空，則算法結(jié)束(第4、第12行)。

圖2給出了4種算法對DAG1的調(diào)度結(jié)果。其中，PEFT的m akespan 為158 ，PPTS的makespan為156，而本文IPPOSS的m akespan為151。

圖2 4種算法對圖1中DAG1產(chǎn)生的調(diào)度結(jié)果

從時(shí)間復(fù)雜度上來說，相比于PEFT和PPTS,IPPOSS的復(fù)雜度并沒有提高。計(jì)算 I PCM 和OCT的時(shí)間復(fù)雜度都是O(pn·(en+tn))，處理器選擇階段的時(shí)間復(fù)雜度為O(pn·tn2)?？倳r(shí)間復(fù)雜度為O(2·pn·(en+tn)+pn·tn2)。對于密集型DAG，有 e n=tn2，總時(shí)間復(fù)雜度約為O(pn·tn2)。因此，IPPOSS具有與這些算法相同的時(shí)間復(fù)雜度。

4 實(shí)驗(yàn)結(jié)果和討論

本節(jié)對比了IPPOSS與其他3種算法(HEFT[11],PEFT[13]和PPTS[14])的調(diào)度性能。設(shè)置了兩種應(yīng)用圖：隨機(jī)生成的應(yīng)用圖和真實(shí)世界應(yīng)用的應(yīng)用圖。通過設(shè)置對比的指標(biāo)，將4種算法的性能進(jìn)行了比較。4種對比指標(biāo)分別為SLR[11]、加速比(Speedup)[15]、松弛度(Slack)[23]和更好的解發(fā)生的比例(Percentage of Occurrences of Better Solutions, POBS)[11]。

4.1 隨機(jī)生成的應(yīng)用圖

本節(jié)首先評估HEFT[11], PEFT[13], PPTS[14]和本文的IPPOSS算法對隨機(jī)DAG的調(diào)度性能。本文使用了一款開源的DAG生成軟件daggen[24]，利用其基本參數(shù)生成實(shí)驗(yàn)所需的隨機(jī)DAG。

實(shí)驗(yàn)中使用了以下參數(shù)的組合來生成隨機(jī)DAG：n=[10,20,30,40,50,60,70,80,90,100]，表示DAG中的任務(wù)數(shù)量；c cr=[0.1,0.2,0.5,1,2,5,10]，表示平均通信時(shí)間與平均計(jì)算時(shí)間的比值；β=[0.1,0.2,0.5,1,2]，表示處理器速度的異構(gòu)性因子；j ump=[1,2,4]，表示任務(wù)間通信跨越的最大層級數(shù)量；r egular=[0.2,0.8]，表示DAG的不同級別之間任務(wù)分配的規(guī)律性； fat=[0.1,0.4,0.8]，表示DAG中可能出現(xiàn)的并行執(zhí)行的任務(wù)的最大數(shù)量；density=[0.2,0.8]，表示DAG中兩個(gè)相鄰層級中的任務(wù)間的依賴的數(shù)量系數(shù)；p n=[4,8,16,32]，表示異構(gòu)計(jì)算系統(tǒng)中處理器的數(shù)量。

以上8個(gè)參數(shù)總共有50400種組合，對于每一種組合，隨機(jī)生成10個(gè)DAG，總數(shù)量為504000。

圖3顯示了任務(wù)數(shù)量值為[10,20,30,40,50,60,70,80,90,100]的平均SLR、平均加速比和平均松弛度。每個(gè)數(shù)據(jù)節(jié)點(diǎn)都是50400個(gè)隨機(jī)生成DAG的實(shí)驗(yàn)結(jié)果平均值。圖3(a)表明，對于不同任務(wù)數(shù)量值，IPPOSS算法的平均SLR是4種算法中最低的。與HEFT算法相比，當(dāng)任務(wù)數(shù)量為10時(shí)，IPPOSS算法的平均SLR降低最高達(dá)7.82%。圖3(b)表明，對于不同任務(wù)數(shù)量值，IPPOSS算法的平均加速比是4種算法中最高的。與PEFT算法相比，當(dāng)任務(wù)數(shù)量為50時(shí)，平均加速比的提高最高達(dá)3.97%。相比其他算法，IPPOSS在任務(wù)優(yōu)先級排序階段使用IPCM 進(jìn)行預(yù)測，I PCM不僅考慮了直接后繼任務(wù)在可以獲取最小計(jì)算、通信時(shí)間之和的處理器上執(zhí)行的時(shí)間消耗，而且考慮了當(dāng)前任務(wù)在選擇的處理器上的時(shí)間消耗，因此IPPOSS進(jìn)行了更準(zhǔn)確的預(yù)測，為處理器選擇提供了更合理的優(yōu)先級列表，從而獲得了更高的平均加速比。而 I PCM的計(jì)算相比其他算法的預(yù)測表或預(yù)測矩陣并未提高時(shí)間復(fù)雜度，且算法中其他流程也未提高時(shí)間復(fù)雜度，從而在保持時(shí)間復(fù)雜度不變的基礎(chǔ)上提高了平均加速比。圖3(c)表明，對于不同任務(wù)數(shù)量值，IPPOSS算法的平均松弛度低于HEFT和PEFT算法。 相比于PPTS算法，在任務(wù)數(shù)量≤50時(shí)，IPPOSS的平均松弛度與PPTS接近。在任務(wù)數(shù)量≥60時(shí)，IPPOSS的平均松弛度略高于PPTS。因?yàn)镮PPOSS算法具有較為激進(jìn)性能策略，在獲得更短的調(diào)度長度和更高的加速比的同時(shí)，降低了一定的穩(wěn)定性。但在任務(wù)數(shù)量≥60時(shí)，IPPOSS仍比PPTS具有更高的穩(wěn)定性。

圖3 4種算法對不同任務(wù)數(shù)量的DAG的調(diào)度結(jié)果

圖4顯示了ccr值為[ 0.1,0.2,0.5,1,2,5,10]的平均SLR、平均加速比和平均松弛度。每個(gè)數(shù)據(jù)節(jié)點(diǎn)都是72000個(gè)隨機(jī)生成DAG的實(shí)驗(yàn)結(jié)果平均值。圖4(a)表明，對于不同ccr值，IPPOSS算法的平均S LR 是4種算法中最低的。與HEFT算法相比當(dāng)ccr為1時(shí)，平均SLR的降低最高達(dá)5.96%。圖4(b)表明，對于不同ccr值，IPPOSS算法的平均加速比高于HEFT和PEFT。與PEFT算法相比，當(dāng)ccr為1時(shí)，平均加速比提高最高達(dá)5.10%。相比于PPTS算法，在ccr≤0.5時(shí)，IPPOSS的平均加速比高于PPTS。在ccr≥1時(shí)，IPPOSS的平均加速比與PPTS相近。這是因?yàn)?，PPTS使用的P CM會(huì)導(dǎo)致鄰近任務(wù)在相同處理器上執(zhí)行的趨勢，這會(huì)在通信量較高也就是ccr較高的情況下，通過更多地避免通信來獲得較好的性能。但是，這種方法會(huì)導(dǎo)致陷入單處理器化的局部最優(yōu)解，因此只在ccr較高時(shí)獲得了與IPPOSS相近的平均加速比，而在ccr較低時(shí)獲得了比IPPOSS差的平均加速比。圖4(c)表明，對于不同ccr值，IPPOSS算法的平均松弛度低于HEFT和PEFT。雖然在ccr≥1時(shí)，IPPOSS與PPTS的加速比接近，但是IPPOSS在SLR和松弛度指標(biāo)上仍然優(yōu)于PPTS，這意味著在此情況下IPPOSS比PPTS更容易獲得較短的調(diào)度長度和更好的穩(wěn)定性。

圖4 4種算法對不同ccr的DAG的調(diào)度結(jié)果

圖5顯示了處理器數(shù)量值為[ 4,8,16,32]的平均SLR和平均加速比。每個(gè)數(shù)據(jù)節(jié)點(diǎn)都是126000個(gè)隨機(jī)生成DAG的實(shí)驗(yàn)結(jié)果平均值。圖5表明，對于不同處理器數(shù)量，IPPOSS的平均SLR和平均加速比在大多數(shù)情況下優(yōu)于其他算法。在處理器數(shù)量為4時(shí)，IPPOSS的平均SLR與PPTS相近，平均加速比略低于PPTS。原因?yàn)镻PTS的預(yù)測策略傾向于在同一處理器上執(zhí)行任務(wù)，其在處理器數(shù)量較少時(shí)具有一定優(yōu)勢。圖5(a)表明，與HEFT算法相比，當(dāng)處理器數(shù)量為32時(shí)，IPPOSS算法的平均SLR降低最高達(dá)6.76%。圖5(b)表明，與HEFT算法相比，當(dāng)處理器數(shù)量為32時(shí)，平均加速比的提高最高達(dá)2.00%。

圖5 4種算法對不同處理器數(shù)量的DAG的調(diào)度結(jié)果

表5列出了IPPOSS與其他算法相比產(chǎn)生的更好、相等和更差的調(diào)度長度的百分比。IPPOSS算法分別在44.9%, 58.8%和66.7%的DAG中獲得了更短的調(diào)度長度，只在22.7%, 15.2%和23.5%的DAG中獲得了更長的調(diào)度長度。

表5 4種算法的調(diào)度長度的成對比較(%)

4.2 真實(shí)世界應(yīng)用的應(yīng)用圖

除了隨機(jī)生成的應(yīng)用圖，本文還評估了HEFT[11],PEFT[13], PPTS[14]和IPPOSS算法對兩種真實(shí)世界應(yīng)用的DAG圖的調(diào)度性能，包括高斯消元[25]和蒙太奇(Montage)[26]。前者是用于求解線性方程組等重要矩陣運(yùn)算中的算法，后者是一種天文圖像拼接引擎，可將天空的各個(gè)圖像組合成一個(gè)拼接圖。這兩種應(yīng)用的DAG在具有一定的并行性的同時(shí)還具有一定的復(fù)雜性。此外，它們的DAG中的任務(wù)數(shù)量可以被較靈活地定義。所以，本文實(shí)驗(yàn)中使用了這兩種真實(shí)世界的應(yīng)用。

對于這些應(yīng)用的DAG，因?yàn)榛拘螤罱Y(jié)構(gòu)已經(jīng)固定了，本文設(shè)置3種參數(shù)用于生成具有不同通信和運(yùn)算特性的應(yīng)用圖，這些參數(shù)包括：ccr=[0.1,0.2,0.5,1,2,5,10],β=[0.1,0.2,0.5,1,2] ,pn=[4,8,16,32]。

第1種真實(shí)世界應(yīng)用的應(yīng)用圖是高斯消元，其任務(wù)數(shù)量等于(m2+m-2)/2，其中m是矩陣的尺寸。實(shí)驗(yàn)中使用的矩陣尺寸m=[5,10,15,20]，對應(yīng)任務(wù)數(shù)量t n=[14,54,119,209]。

圖6顯示了不同矩陣尺寸下的平均SLR和平均加速比。圖6(a)表明對于不同矩陣尺寸值，IPPOSS的平均SLR是4種算法中最低的。與HEFT算法相比，IPPOSS算法的平均SLR降低分別為9.93%,5.57%, 5.16%和5.14%。與PPTS算法相比，IPPOSS算法的平均SLR降低分別為6.43%, 3.43%, 6.33%和6.91%。圖6(b)表明對于不同矩陣尺寸值，IPPOSS算法的平均加速比是4種算法中最高的。與HEFT算法相比，IPPOSS算法的平均加速比提高分別為3.44%, 4.21%, 3.88%和3.53%。

圖6 4種算法對不同矩陣尺寸的高斯消元應(yīng)用的調(diào)度結(jié)果

第2種真實(shí)世界應(yīng)用的應(yīng)用圖是蒙太奇，任務(wù)數(shù)量設(shè)為[ 33,50,96,195,411]。

圖7顯示了不同任務(wù)數(shù)量下的平均SLR和平均加速比。圖7(a)表明對于不同任務(wù)數(shù)量，IPPOSS算法的平均SLR是4種算法中最低的。與HEFT算法相比，IPPOSS算法的平均SLR降低分別為8.49%, 8.46%, 8.18%, 9.28%和9.68%。圖7(b)表明對于不同任務(wù)數(shù)量，IPPOSS算法的平均加速比是4種算法中最高的。

圖7 4種算法對不同任務(wù)數(shù)量的蒙太奇應(yīng)用的調(diào)度結(jié)果

5 結(jié)論

本文針對異構(gòu)列表調(diào)度問題，提出一種同時(shí)優(yōu)于PPTS和PEFT并且保持2次復(fù)雜度的調(diào)度算法IPPOSS。本算法使用IPCM進(jìn)行預(yù)測，更合理地進(jìn)行了任務(wù)優(yōu)先級排序，從而在經(jīng)過處理器選擇階段后獲得了更好的解。在隨機(jī)生成的應(yīng)用圖實(shí)驗(yàn)中，IPPOSS的SLR優(yōu)于HEFT, PEFT和PPTS。對于加速比和松弛度指標(biāo)，IPPOSS比HEFT和PEFT更好，并且與PPTS的結(jié)果相近。此外，對于相同的DAG，相比于其他3種算法，IPPOSS容易出現(xiàn)更好的調(diào)度結(jié)果。對于真實(shí)世界應(yīng)用高斯消元和蒙太奇，IPPOSS算法的SLR和加速比指標(biāo)也優(yōu)于這4種算法。