李靜梅，金勝男

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

0 引 言

異構(gòu)多核處理器以其芯片面積利用率高、處理器功耗低、應(yīng)用程序的并行化程度高等諸多優(yōu)勢(shì)成為處理器體系結(jié)構(gòu)發(fā)展的一個(gè)重要方向，同時(shí)它的出現(xiàn)給計(jì)算機(jī)學(xué)科發(fā)展帶來(lái)了新的挑戰(zhàn)［1－2］。研究發(fā)現(xiàn)多核處理器任務(wù)調(diào)度的優(yōu)劣對(duì)處理器的執(zhí)行時(shí)間、任務(wù)調(diào)度長(zhǎng)度、處理器的功耗等諸多性能產(chǎn)生直接影響。因此，多核處理器的任務(wù)調(diào)度作為影響操作系統(tǒng)性能的重要因素成為近年來(lái)系統(tǒng)結(jié)構(gòu)方向的熱點(diǎn)研究問(wèn)題之一［3－4］。當(dāng)前對(duì)異構(gòu)多核處理器上任務(wù)調(diào)度的研究很少考慮任務(wù)優(yōu)先級(jí)的選取對(duì)調(diào)度結(jié)果的影響以及使用復(fù)制技術(shù)的任務(wù)調(diào)度算法會(huì)產(chǎn)生冗余任務(wù)的問(wèn)題。本文深入分析了CPFD、HCPFD和HDEFT這3種最具有代表性的任務(wù)調(diào)度算法，并在總結(jié)目前任務(wù)調(diào)度算法存在的缺點(diǎn)基礎(chǔ)上，根據(jù)異構(gòu)多核處理器系統(tǒng)結(jié)構(gòu)的特點(diǎn)，設(shè)計(jì)了基于加權(quán)優(yōu)先級(jí)的任務(wù)調(diào)度算法（weighted priority task scheduling，WPTS），算法以3個(gè)參數(shù)構(gòu)成的加權(quán)值作為任務(wù)的優(yōu)先級(jí)，將任務(wù)排序構(gòu)成任務(wù)調(diào)度列表，然后依次將任務(wù)映射到處理器上，并在映射過(guò)程中對(duì)任務(wù)進(jìn)行優(yōu)化處理，最后通過(guò)預(yù)先設(shè)定的性能評(píng)價(jià)參數(shù)對(duì)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。本研究能有效改善原有任務(wù)調(diào)度算法的不足，提升了多核處理器在實(shí)際應(yīng)用中的性能，對(duì)異構(gòu)多核處理器上靜態(tài)任務(wù)調(diào)度技術(shù)的發(fā)展具有重大理論和現(xiàn)實(shí)意義［5－6］。

1 WPTS算法設(shè)計(jì)

1.1 3種現(xiàn)有高效算法的分析

目前基于異構(gòu)多核處理器取得較好調(diào)度性能的算法有CPFD算法、HCPFD算法和 HDEFT算法［7－8］。CPFD算法使用任務(wù)節(jié)點(diǎn)到入口節(jié)點(diǎn)的最長(zhǎng)路徑b－level作為任務(wù)調(diào)度的優(yōu)先級(jí)，將任務(wù)調(diào)度到具有最早完成時(shí)間的處理器上，其時(shí)間復(fù)雜度是O（v4），v是DAG圖中任務(wù)節(jié)點(diǎn)的數(shù)目。HCPFD算法以關(guān)鍵任務(wù)和任務(wù)的最晚開(kāi)始時(shí)間劃分任務(wù)的優(yōu)先級(jí)，將任務(wù)分配到使其完成時(shí)間最早的處理器節(jié)點(diǎn)上，在任務(wù)到處理器的映射階段優(yōu)先考慮使用處理器上的空閑時(shí)間段來(lái)處理任務(wù)，其時(shí)間復(fù)雜度為O（pv2），p是任務(wù)調(diào)度中處理器的總個(gè)數(shù)。HDEFT算法在任務(wù)分配階段采用sumu（vi）作為任務(wù)優(yōu)先級(jí)，在任務(wù)到處理器的映射階段使用任務(wù)插入和復(fù)制技術(shù)，其時(shí)間復(fù)雜度為O（pv2）。

CPFD算法和HCPFD算法的調(diào)度性能不夠理想，原因在于算法只選擇唯一任務(wù)屬性作為任務(wù)的優(yōu)先級(jí)，沒(méi)有考慮任務(wù)間的約束關(guān)系和通信開(kāi)銷(xiāo)等影響調(diào)度性能的重要因素。HDEFT算法時(shí)間復(fù)雜度不高，但沒(méi)有對(duì)使用任務(wù)復(fù)制技術(shù)后存在的冗余任務(wù)進(jìn)行處理，冗余任務(wù)延長(zhǎng)了總的任務(wù)調(diào)度完成時(shí)間，浪費(fèi)了處理器資源。

本文在總結(jié)并分析上述算法不足的基礎(chǔ)上，設(shè)計(jì)出WPTS算法，并給出任務(wù)調(diào)度實(shí)驗(yàn)以驗(yàn)證新算法的正確性和有效性。

1.2 WPTS算法執(zhí)行過(guò)程

WPTS算法的執(zhí)行分為兩個(gè)階段：任務(wù)優(yōu)先級(jí)計(jì)算和任務(wù)到處理器的映射。其中第一階段包括任務(wù)合并、任務(wù)分層和任務(wù)權(quán)值計(jì)算3個(gè)過(guò)程，第二階段包括任務(wù)分配到處理器和任務(wù)調(diào)度結(jié)果優(yōu)化兩個(gè)過(guò)程，如圖1所示。

圖1 WPTS算法執(zhí)行過(guò)程

1.3 WPTS算法實(shí)現(xiàn)原理

1.3.1 任務(wù)優(yōu)先級(jí)計(jì)算階段

（1）任務(wù)優(yōu)先級(jí)計(jì)算階段的設(shè)計(jì)思想

任務(wù)合并是將任務(wù)中較獨(dú)立、任務(wù)間通信開(kāi)銷(xiāo)較大的任務(wù)進(jìn)行合并優(yōu)化。對(duì)DAG圖進(jìn)行深度優(yōu)先搜索，當(dāng)任務(wù)vi只有一個(gè)直接后繼節(jié)點(diǎn)vj、任務(wù)vj只有一個(gè)直接前驅(qū)節(jié)點(diǎn)vi，且c（vi，vj）≥wj，k，即任務(wù)vi、vj間的通信開(kāi)銷(xiāo)大于任務(wù)vj在所有處理器上的平均執(zhí)行開(kāi)銷(xiāo)，則合并任務(wù)vi、vj，并記為vi＊，vi＊的計(jì)算開(kāi)銷(xiāo)為vi、vj計(jì)算開(kāi)銷(xiāo)的總和，在隨后的調(diào)度中任務(wù)vi＊被作為整體處理。

任務(wù)分層是為方便后續(xù)任務(wù)權(quán)值的計(jì)算。用level標(biāo)記任務(wù)在DAG圖中的層數(shù)，設(shè)置入口節(jié)點(diǎn)任務(wù)level＝0，從上到下遍歷任務(wù)DAG圖，計(jì)算任務(wù)節(jié)點(diǎn)到入口節(jié)點(diǎn)的最大通信邊數(shù)目，以此作為任務(wù)的level值。非入口節(jié)點(diǎn)任務(wù)vi的level值為其所有前驅(qū)節(jié)點(diǎn)的最大level值加1，計(jì)算公式如下所示

在任務(wù)權(quán)值計(jì)算過(guò)程中，WPTS算法綜合考慮任務(wù)各屬性對(duì)任務(wù)優(yōu)先級(jí)排序的影響，選擇使用平均計(jì)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)作為任務(wù)的優(yōu)先級(jí)參數(shù)。平均計(jì)算開(kāi)銷(xiāo)ACC是任務(wù)在所有處理器上計(jì)算開(kāi)銷(xiāo)的平均值，計(jì)算公式如式（2）所示。通信開(kāi)銷(xiāo)包括平均數(shù)據(jù)傳輸開(kāi)銷(xiāo)ADTC和平均數(shù)據(jù)接收開(kāi)銷(xiāo)ADRC，計(jì)算公式如式（3）和式（4）所示，式中x為vi直接后繼節(jié)點(diǎn)數(shù)量，y為vi直接前驅(qū)節(jié)點(diǎn)數(shù)量

定義weight（vi）為任務(wù)vi的權(quán)值，它是任務(wù)的ADTC、ADRC、ACC之和，對(duì)每個(gè)處在level＝i層的任務(wù)來(lái)說(shuō)weight（vi）的計(jì)算公式如公式下所示

（2）任務(wù)優(yōu)先級(jí)計(jì)算階段流程

任務(wù)優(yōu)先級(jí)計(jì)算流程如圖2所示。

任務(wù)優(yōu)先級(jí)計(jì)算階段完成后，所有的任務(wù)已經(jīng)按照優(yōu)先級(jí)從高到低的次序加入到調(diào)度列表中，可以繼續(xù)執(zhí)行任務(wù)到處理器映射階段的步驟。

1.3.2 任務(wù)到處理器映射階段

（1）任務(wù)到處理器映射階段的設(shè)計(jì)思想

任務(wù)到處理器映射階段包括任務(wù)映射到處理器和處理器上的冗余任務(wù)處理。

圖2 任務(wù)優(yōu)先級(jí)計(jì)算階段流程

在任務(wù)映射到處理器的過(guò)程中，遍歷所有處理器，直接將任務(wù)vi分配到具有最早完成時(shí)間的處理器上，其完成時(shí)間記為EFT1；將vi分配具有空閑時(shí)間段的處理器上且不使用任務(wù)復(fù)制技術(shù)的最早完成時(shí)間為EFT2；記使用復(fù)制任務(wù)技術(shù)復(fù)制任務(wù)vi的直接前驅(qū)節(jié)點(diǎn)到vi所處的處理器空閑時(shí)間段上最早完成時(shí)間為EFT3。比較三者的值，將任務(wù)vi分配到具有最小完成時(shí)間的處理器上。EFT1、EFT2、EFT3的計(jì)算公式如下

式中：AST（vi，pn）——任務(wù)vi在處理器pn上的實(shí)際開(kāi)始時(shí)間；AFT（vi，pk）——任務(wù)vi在處理器pk上的實(shí)際完成時(shí)間；vpar——最后一個(gè)與任務(wù)vi通信的任務(wù)；Avail（pn）——處理器pn執(zhí)行完分配到其上的所有任務(wù)的時(shí)間。

通過(guò)對(duì)DAG圖的深入研究發(fā)現(xiàn)，某層冗余任務(wù)的處理在其下一層任務(wù)到處理器的映射之后執(zhí)行效果最好，如對(duì)level＝1層任務(wù)調(diào)度完成后對(duì)level＝0層任務(wù)進(jìn)行冗余判斷，將任務(wù)分配到處理器和冗余任務(wù)處理兩個(gè)過(guò)程交替執(zhí)行，直到冗余任務(wù)列表為空。

（2）任務(wù)到處理器映射流程

任務(wù)到處理器映射流程如圖3所示。

（3）任務(wù)到處理器映射階段具體步驟

步驟1 初始化level＝0，判斷任務(wù)調(diào)度列表TL在level層的任務(wù)是否調(diào)度完畢，如果是則跳轉(zhuǎn)到步驟5；否則向下執(zhí)行步驟2。

步驟2 取任務(wù)調(diào)度列表TL的首任務(wù)記為vi，遍歷所有處理器，如果處理器存在空閑時(shí)間段且滿(mǎn)足vi插入條件，則將vi分配到空閑時(shí)間段，并計(jì)算其最小最早完成時(shí)間，記為EFT1；否則向下執(zhí)行步驟3。

步驟3 計(jì)算將vi分配到所有處理器上的最小最早完成時(shí)間，記為EFT2。如果處理器上存在空閑時(shí)間段且能使用任務(wù)復(fù)制技術(shù)，則計(jì)算在處理器上復(fù)制vi的前驅(qū)獲得最小最早完成時(shí)間，記為EFT3，繼續(xù)執(zhí)行步驟4。

步驟4 選擇EFT1、EFT2、EFT3的最小值，并將任務(wù)分配到具有最早完成時(shí)間的處理器上，從調(diào)度列表中刪除vi，建立冗余任務(wù)列表RTL，將被復(fù)制的任務(wù)加入到RTL中，格式為vi，0～vi，k，vi為被復(fù)制的任務(wù)節(jié)點(diǎn)，k為任務(wù)所在處理器的編號(hào)。

步驟5 判斷RTL中是否有（level－1）層任務(wù)，如果是則跳轉(zhuǎn)到步驟6；否則跳轉(zhuǎn)到步驟8。

步驟6 取RTL首任務(wù)節(jié)點(diǎn)，記為vi，k，判斷刪除任務(wù)vi，k后vi，k直接后繼節(jié)點(diǎn)的最早開(kāi)始時(shí)間是否延遲，如果延遲，判定任務(wù)vi，k非冗余任務(wù)，從RTL中刪除vi，k，跳轉(zhuǎn)到步驟5；否則判定任務(wù)vi，k為冗余節(jié)點(diǎn)，從RTL中刪除vi，k，從任務(wù)映射圖中刪除vi，k，跳轉(zhuǎn)到步驟7繼續(xù)執(zhí)行。

步驟7 判斷任務(wù)vi，k的后繼任務(wù)能否提前執(zhí)行，如果能則將其前移執(zhí)行，修改任務(wù)映射圖，跳轉(zhuǎn)到步驟5；否則，直接跳轉(zhuǎn)到步驟5。

步驟8 如果level＜Max（level），令level＝level＋1，跳轉(zhuǎn)到步驟1；否則任務(wù)到處理器映射階段執(zhí)行完畢。

2 WPTS算法時(shí)間復(fù)雜度分析

圖3 任務(wù)到處理器映射階段流程

任務(wù)合并過(guò)程是對(duì)DAG圖進(jìn)行一次深度優(yōu)先遍歷，因此其時(shí)間復(fù)雜度為O（v＋e），v為DAG圖中任務(wù)的數(shù)量，e為有向邊的數(shù)目。任務(wù)分層是從上到下計(jì)算每個(gè)節(jié)點(diǎn)的level值，時(shí)間復(fù)雜度為O（n＋e），n為任務(wù)合并后DAG圖中任務(wù)的數(shù)量。任務(wù)權(quán)值計(jì)算對(duì)DAG圖進(jìn)行廣度優(yōu)先遍歷，計(jì)算任務(wù)節(jié)點(diǎn)的weight值和尋找關(guān)鍵路徑節(jié)點(diǎn)，時(shí)間復(fù)雜度為O（n2），因此任務(wù)優(yōu)先級(jí)計(jì)算階段的時(shí)間復(fù)雜度為O（v＋e）＋O（n＋e）＋O（n2）；任務(wù)到處理器的映射階段考慮了處理器空閑時(shí)間段插入和任務(wù)復(fù)制技術(shù)，因此每層任務(wù)被映射到處理器上的時(shí)間復(fù)雜度為O（kp），k為每層的任務(wù)數(shù)量，p為處理器的數(shù)量，冗余任務(wù)處理的時(shí)間復(fù)雜度為O（k2），將所有任務(wù)映射到處理器上并完成調(diào)度結(jié)果優(yōu)化所需的時(shí)間復(fù)雜度為O（kpm＋k2m），m為任務(wù)DAG圖的層數(shù)，其在最壞情況下等于任務(wù)數(shù)量v。

綜上所述，WPTS算法的時(shí)間復(fù)雜度為O（v＋e）＋O（n＋e）＋O（n2）＋O（kpm＋k2m），即 O（v3），算法沒(méi)有提高時(shí)間復(fù)雜度，且能有效處理使用任務(wù)復(fù)制技術(shù)帶來(lái)的冗余任務(wù)，減少任務(wù)的調(diào)度長(zhǎng)度，避免處理器資源的浪費(fèi)。

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

3.1 性能評(píng)價(jià)參數(shù)

在靜態(tài)任務(wù)調(diào)度中，任務(wù)調(diào)度的開(kāi)銷(xiāo)比較小，任務(wù)調(diào)度的總長(zhǎng)度成為評(píng)價(jià)一個(gè)任務(wù)調(diào)度算法的性能標(biāo)準(zhǔn)，除此之外還有任務(wù)調(diào)度長(zhǎng)度比率、算法的效率等，具體的評(píng)定標(biāo)準(zhǔn)和公式如下：

（1）調(diào)度長(zhǎng)度makespan，為所有處理器上的最大任務(wù)調(diào)度長(zhǎng)度。

（2）調(diào)度長(zhǎng)度比率SLR，計(jì)算公式如式（9）所示，分母為所有關(guān)鍵路徑任務(wù)執(zhí)行時(shí)間的最小值之和。SLR的值總是大于等于1的，且值越小，任務(wù)調(diào)度算法性能越好。

（3）算法效率Efficiency，計(jì)算公式如式（10）所示，分子為任務(wù)調(diào)度的加速比，計(jì)算公式如式（11）所示，分母為任務(wù)調(diào)度中處理器的數(shù)量，Efficiency值越大表明任務(wù)調(diào)度算法的性能越好

3.2 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)將任務(wù)調(diào)度性能測(cè)試分成兩組，通過(guò)仿真實(shí)驗(yàn)檢驗(yàn)WPTS算法在不同任務(wù)圖中的性能［9］。

實(shí)驗(yàn)1：利用隨機(jī)任務(wù)圖產(chǎn)生器［10－11］，根據(jù)參數(shù)值v（DAG的任務(wù)數(shù)量，取值為 ｛30，40，50，60，70，80，90，100｝）、α（DAG 的形狀參數(shù)，取值為｛0.5，1.0，2.0｝、β（節(jié)點(diǎn)的出度，取值為 ｛1，2，3，4，5｝）、γ（節(jié)點(diǎn)的入度，取值為 ｛1，2，3，4，5｝）、CCR（通信計(jì)算時(shí)間比，取值為 ｛0.1，0.5，1.0，5.0，10.0｝）產(chǎn)生3000組DAG類(lèi)型，每組類(lèi)型中隨機(jī)產(chǎn)生20個(gè)具有不同節(jié)點(diǎn)權(quán)值的DAG圖，共產(chǎn)生60000個(gè)隨機(jī)任務(wù)圖。

將隨機(jī)任務(wù)圖以參數(shù)形式輸入算法中，通過(guò)Socket將算法運(yùn)行結(jié)果傳遞到仿真實(shí)驗(yàn)環(huán)境中。仿真實(shí)驗(yàn)使用Simics模擬多核異構(gòu)處理器結(jié)構(gòu)，通過(guò)C語(yǔ)言實(shí)現(xiàn)算法和Socket通信模塊，實(shí)現(xiàn)虛擬多核環(huán)境和算法之間的有效信息交互，通過(guò)對(duì)任務(wù)圖的完成時(shí)間長(zhǎng)短判斷算法優(yōu)劣（依次比較兩種算法，完成時(shí)間差在線(xiàn)性級(jí)之內(nèi)的標(biāo)記為Equal，其它情況下，算法1較算法2完成時(shí)間短時(shí)標(biāo)記為Better，完成時(shí)間長(zhǎng)時(shí)標(biāo)記為Worse），實(shí)驗(yàn)方案結(jié)構(gòu)如圖4所示。

將WPTS算法與CPFD算法、HCPFD算法、HDEFT算法進(jìn)行比較，統(tǒng)計(jì)WPTS算法較其它3種算法取得Better、Equal和Worse調(diào)度性能的次數(shù)和所占的比例，比較結(jié)果見(jiàn)表1。

圖4 驗(yàn)證方案結(jié)構(gòu)

表1 算法調(diào)度性能對(duì)比

從表1可以看出在隨機(jī)實(shí)驗(yàn)環(huán)境下，在將3種算法綜合的情況下，WPTS算法能取得最優(yōu)調(diào)度的比例為71.53%，優(yōu)于其它3種算法。

實(shí)驗(yàn)2：（1）令α＝｛0.5，1.0，2.0｝，改變隨機(jī)任務(wù)圖的其它參數(shù)，計(jì)算各算法的平均SLR和Efficiency，計(jì)算公式如式（9）、式（10），實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

圖5 形狀參數(shù)α變化時(shí)算法的平均SLR

從對(duì)比圖可以看出，任務(wù)形狀參數(shù)α變化會(huì)影響任務(wù)調(diào)度的結(jié)果：α值為0.5時(shí)，DAG圖高度較小，任務(wù)之間并行性較高；α值為1.5時(shí)，DAG圖高度較大，任務(wù)之間并行性較低。4種算法在任務(wù)并行性較高時(shí)都能取得很好的性能，其中WPTS算法的性能最優(yōu)，原因是任務(wù)并行性較高時(shí)，處理器上的空閑時(shí)間較少，處理器的利用率較高，而WPTS算法能及時(shí)處理任務(wù)調(diào)度中存在的冗余任務(wù)，提高處理器的執(zhí)行效率。

圖6 形狀參數(shù)α變化時(shí)算法的Efficiency

（2）改變處理器數(shù)量，使其分別為4、8、12、16、20，其它參數(shù)不變，各算法的性能如圖7、圖8所示。

從對(duì)比圖可以看出，與其它任務(wù)調(diào)度算法相比，WPTS算法更具有性能優(yōu)勢(shì)，其原因在于新算法充分利用處理器上的空閑時(shí)間調(diào)度任務(wù)，并及時(shí)對(duì)產(chǎn)生的冗余任務(wù)進(jìn)行處理，提前后繼任務(wù)的最早開(kāi)始時(shí)間，因此取得了更好的調(diào)度性能。

（3）CCR取值分別為0.1，0.5，1.0，5.0，10.0，其它參數(shù)值不變，各算法的性能測(cè)試結(jié)果如圖9、圖10所示。

從對(duì)比圖可以看出，CCR不同時(shí)，因?yàn)閃PTS算法對(duì)冗余任務(wù)有較好的處理，因此較其它3種算法取得了更好的性能。

根據(jù)這兩組測(cè)試結(jié)果，可以看出WPTS算法要優(yōu)于CPFD、HCPFD和HDEFT算法，隨著任務(wù)規(guī)模的增大，WPTS算法的優(yōu)勢(shì)越明顯。

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

通過(guò)深入分析目前異構(gòu)多核處理器任務(wù)調(diào)度算法存在的不足，提出了WPTS算法。WPTS算法使用加權(quán)值weight標(biāo)記任務(wù)的優(yōu)先級(jí)，新優(yōu)先級(jí)計(jì)算方法克服了優(yōu)先級(jí)選取單一帶來(lái)的問(wèn)題，能更準(zhǔn)確地反映任務(wù)在DAG圖中的位置和屬性；在任務(wù)到處理器的映射階段及時(shí)消除任務(wù)調(diào)度中產(chǎn)生的冗余任務(wù)，提前后續(xù)任務(wù)的最早開(kāi)始執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，新算法能取得最優(yōu)調(diào)度的比例為71.53%，且在DAG形狀、處理器數(shù)量和CCR不同時(shí)較已有算法均能取得更好的性能。

［1］JIANG Wen.Research of task scheduling algorithms for heterogeneous computing environment［D］.Hunan：Master’s Graduation Thesis of Hunan University，2010：9－25（in Chinese）.［江文.異構(gòu)計(jì)算環(huán)境下任務(wù)調(diào)度算法的研究［D］.湖南：湖南大學(xué)碩士學(xué)位論文，2010：9－25.］

［2］Ahmad Ishfaq，Ranka Sanjay，Khan Samee Ullah.Using game theory for scheduling tasks on multi－core processors for simultaneous optimization of performance and energy［J］.IEEE International Symposium on Parallel and Distributed Processing，2008：2645－2650.

［3］WU Jiajun.Research on task scheduling technology based on heterogeneous multi－core and multi－threaded processors［D］.Anhui：Doctor’s Graduation Thesis of Institute of Computing Technology Chinese Academy of Sciences，2006：4－17（in Chinese）.［吳佳駿.多核多線(xiàn)程處理器上任務(wù)調(diào)度技術(shù)研究［D］.安徽：中國(guó)科學(xué)院計(jì)算技術(shù)研究所博士學(xué)位論文，2006：4－17.］

［4］Laura De Giusti，Emilio Luque，F(xiàn)ranco Chichizola.AMTHA：An algorithm for automatically mapping tasks to processors in heterogeneous multiprocessor architectures［C］／／World Congress on Computer Science and Information Engineering，2009：481－485.

［5］Mohammad I Daoud，Nawwaf Kharma.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2008，68（4）：399－409.

［6］Sah S K，Singh R S.Critical path based scheduling of multiple applications in heterogeneous distributed computing［C］／／IEEE International Advance Computing Conference，2009：99－104.

［7］Hagras T，Janecek.A high performance，low complexity algorithm for compile－time task scheduling in heterogeneous system［J］.Parallel Computing，2005，31（7）：653－670.

［8］JIANG Yunlian.Task Scheduling in parallel heterogeneous systems［D］.Anhui：Master’s Graduation thesis of University of Science and Technology of China，2006：22－43（in Chinese）.［蔣韻聯(lián).并行異構(gòu)系統(tǒng)任務(wù)調(diào)度問(wèn)題研究［D］.安徽：中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文，2006：22－43.］

［9］ZHANG Jianjun，SONG Yexin，HUANG Dengbin.Task scheduling algorithm for Fork－Join task graphs in heterogeneous environment［J］.Computer Engineering and Design，2010，31（3）：486－489（in Chinese）.［張建軍，宋業(yè)新，黃登斌.異構(gòu)環(huán)境中Fork－Join任務(wù)圖的調(diào)度算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（3）：486－489.］

［10］Young Choon Lee，Albert Y Zomaya.A novel state transition method for metaheuristic－based scheduling in heterogeneous computing systems［J］.IEEE Trans on Parallel and Distributed Systems，2008，19（9）：1215－1223.

［11］Matthieu Gallet，Loris Marchal.Efficient scheduling of task graph collections on heterogeneous resources［C］／／International Parallel and Distributed Processing Symposium，2009：1－11.