一種改進(jìn)的基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法

周超群，周亦敏

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

?

一種改進(jìn)的基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法

周超群，周亦敏

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法普遍存在復(fù)制的冗余調(diào)度過多、處理器利用率不高，產(chǎn)生大量能耗等問題。目前已有一些算法針對該問題對冗余調(diào)度進(jìn)行優(yōu)化，然而這些優(yōu)化算法存在檢測冗余時機晚、優(yōu)化空間小、時間復(fù)雜度高等問題。針對這些問題提出一種改進(jìn)的基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法，采用二路復(fù)制策略并結(jié)合冗余處理機制，旨在最小化調(diào)度長度，同時減少冗余的復(fù)制任務(wù)數(shù)量。實驗結(jié)果表明，該算法在減少冗余任務(wù)量和最小化任務(wù)調(diào)度長度兩個方面具有較好的性能。

異構(gòu)多核；復(fù)制；任務(wù)調(diào)度；冗余處理；能耗

基于復(fù)制的任務(wù)調(diào)度算法[1-5]應(yīng)歸類于貪心算法[6]，相比其他任務(wù)調(diào)度算法，在減少通信開銷，最小化任務(wù)調(diào)度長度(Makespan)方面具有明顯優(yōu)勢，然而由于其大規(guī)模地復(fù)制任務(wù)，造成了大量不必要的冗余任務(wù)調(diào)度。這些冗余調(diào)度不但造成大量的能源浪費，而且還會占用共享資源，導(dǎo)致核間任務(wù)相互阻塞，從而降低任務(wù)調(diào)度的能效。文獻(xiàn)[7]提出了一種冗余任務(wù)消除算法-RTE算法，RTE 算法能判斷并刪除使用任務(wù)復(fù)制算法后產(chǎn)生的冗余任務(wù)，從而節(jié)省處理器的調(diào)度資源，并能有效縮短任務(wù)的調(diào)度長度，但是在任務(wù)調(diào)度完成之后進(jìn)行冗余任務(wù)的處理已為時過晚，而且冗余任務(wù)刪除后處理器上會存在空閑時間片，此時對后繼任務(wù)的優(yōu)化可能導(dǎo)致更多任務(wù)需要被重新調(diào)度，增加了算法的時間復(fù)雜度。文獻(xiàn)[8]提出HLDOTS算法，該算法在任務(wù)分配階段考慮同時加入冗余任務(wù)處理階段，并將二者交替執(zhí)行，將冗余檢測時機提前，加快了冗余任務(wù)的處理過程。然而，HLDOTS算法沿用了RTE算法對冗余任務(wù)的定義，只是以不延遲后繼任務(wù)的完成時間為前提，使得部分冗余依然存在；同時，每一次任務(wù)分配之后都要循環(huán)對冗余任務(wù)列表中的待判定任務(wù)進(jìn)行冗余判定與刪除，時間復(fù)雜度較大。

針對上述問題，提出一種改進(jìn)的基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法(Improved Duplication based Scheduling with Redundancy Reduction， IDSRR)，將冗余處理機制與復(fù)制技術(shù)結(jié)合，確定更優(yōu)的冗余處理時機，對刪除冗余任務(wù)產(chǎn)生的空閑時間片進(jìn)行優(yōu)化，同時提出范圍更廣的冗余定義，以消除更多的冗余任務(wù)。減少冗余處理過后對后繼任務(wù)優(yōu)化的時間復(fù)雜度，增加對調(diào)度產(chǎn)生的空閑時間片的利用，大幅減少任務(wù)的調(diào)度長度。

1 調(diào)度模型

在異構(gòu)多核系統(tǒng)中，一個任務(wù)通常被分解為多個有相互依賴關(guān)系的子任務(wù)，本文采用有向無環(huán)圖(Directed Acyclic Graph，DAG)[9]表示任務(wù)集。DAG圖的結(jié)點Vi表示子任務(wù)，有向邊eij表示任務(wù)Vi、Vj的依賴關(guān)系和通信關(guān)系。具體可以用四元組表示：DAG={V,E,W,C}。

圖1 DAG圖

vip0p1p2均值v041120v132120v223430v312113v433330v534127

1.1 DAG 相關(guān)定義

為更好地闡述算法的思路和原理，先給出本文調(diào)度模型的相關(guān)定義和部分變量的計算公式。

V={vi|vi是DAG中的第i個任務(wù)}，i∈{0, 1, …,n-1} ，n為總?cè)蝿?wù)數(shù)量。E={eij|eij是vi指向vj的有向邊}，i,j∈{0, 1, …,n-1}。W={wik|wik表示任務(wù)vi在處理器核pk上的計算開銷}，其中i∈{0, 1, …,n-1}，k∈{0, 1, …,m-1}，m為多核處理器的核的數(shù)量。C={cij|cij是任務(wù)vi與任務(wù)vj的通信開銷}，若vi和vj被調(diào)度到同一個核上，則任務(wù)二者之間的通信開銷為零。

直接前驅(qū)任務(wù)集合：prec(vi)={vj|eji∈E}。

直接后繼任務(wù)集合：succ(vi)={vj|eij∈E}。

入口結(jié)點：ventry ={vi| prec(vi) = ?}。

出口結(jié)點：vexit ={vi| succ(vi) = ?}。

est(vi,pk) 表示任務(wù)vi在處理器核pk上的最早開始時間，等于所有直接前驅(qū)任務(wù)完成時間與通信時間之和的最大值，est(vi,pk)的值為

est(vi,pk)=max{efx(vj)+cji|vj∈prec(vi)}

(1)

est(vi)表示任務(wù)vi在所有處理器核上的最早開始時間，計算方式如式(2)。入口結(jié)點的最早開始時間為0，即est(ventry)= est(ventry,pk)=0。

est(vi)=min{est(vi,pk)}

(2)eft (vi,pk) 表示任務(wù)vi在處理器核pk上的最早完成時間，等于最早開始時間與執(zhí)行時間之和，計算方式如式(3)所示，其中wik是任務(wù)vi在處理器核pk上的執(zhí)行時間

eft(vi,pk)=est(vi,pk)+wik

(3)

eft(vi)表示任務(wù)vi在所有處理器核上的最早完成時間，計算方式如下

eft(vi)=min{eft(vi,pk)}

(4)

前驅(qū)數(shù)據(jù)就緒時間Dat(vj,vi)表示任務(wù)vi從它的直接前驅(qū)任務(wù)vj接收數(shù)據(jù)的完成時間。任務(wù)vi的所有直接其前驅(qū)任務(wù)數(shù)據(jù)就緒時間為Dat(vi)，大小等于所有前驅(qū)的數(shù)據(jù)就緒時間的最大值

Dat(vi)=max{Dat(vj,vi)}=max{eft(vj)+cij}

(5)

最大值所對應(yīng)的任務(wù)vj的數(shù)據(jù)到達(dá)當(dāng)前任務(wù)最晚，此時稱vj為關(guān)鍵前驅(qū)任務(wù)。入口結(jié)點的前驅(qū)數(shù)據(jù)到達(dá)時間Dat(ventry)=0。在任務(wù)調(diào)度過程中，復(fù)制關(guān)鍵前驅(qū)任務(wù)可以提前當(dāng)前任務(wù)數(shù)據(jù)就緒時間，進(jìn)而提早任務(wù)的最早開始時間，減小調(diào)度長度。

idle_piece(pk, ist, ift)表示核pk上的空閑時間片，其中，ist表示空閑開始時間，ift表示空閑結(jié)束時間。

schedule(vi,pk, est, eft)表示任務(wù)vi在核pk上的一次調(diào)度，其中最早開始時間為est，最早完成時間為eft。

1.2 任務(wù)優(yōu)先級

任務(wù)優(yōu)先級表示任務(wù)被調(diào)度的先后順序，本文采用表調(diào)度算法中的向上排序值(rank)[10]表示任務(wù)優(yōu)先級，向上排序值越大的任務(wù)優(yōu)先被調(diào)度，計算方式如式(6)所示。

(6)

表2 向上排序值

1.3 復(fù)制策略

任務(wù)復(fù)制技術(shù)可以有效減少核間通信開銷，從而縮短整體任務(wù)調(diào)度時間[11]。根據(jù)調(diào)度時復(fù)制前驅(qū)任務(wù)的數(shù)量，可以將任務(wù)復(fù)制策略分為單復(fù)制[12]和多復(fù)制[13]。單復(fù)制策略選擇復(fù)制當(dāng)前任務(wù)的關(guān)鍵前驅(qū)任務(wù)。多復(fù)制策略又分為垂直多復(fù)制和水平多復(fù)制。垂直多復(fù)制,如HNDP算法[14]，在調(diào)度時不僅考慮復(fù)制關(guān)鍵前驅(qū)任務(wù)，還會考慮復(fù)制前驅(qū)任務(wù)的前驅(qū)任務(wù)，以此類推，最大限度最小化任務(wù)開始時間；水平多復(fù)制，如STDH算法[15]，在調(diào)度時考慮復(fù)制多個直接前驅(qū)任務(wù)以最小化當(dāng)前任務(wù)的開始時間。單復(fù)制策略的時間復(fù)雜度低，而多復(fù)制策略比單復(fù)制策略更能最小化調(diào)度長度。綜合考慮兩種策略的優(yōu)缺點，本文采用二路復(fù)制策略(Binary Duplicating Policy)，考慮復(fù)制兩個直接前驅(qū)任務(wù)，即復(fù)制當(dāng)前任務(wù)的最關(guān)鍵及次關(guān)鍵前驅(qū)任務(wù)。該復(fù)制策略能兼顧算法性能和時間復(fù)雜度，而且與冗余任務(wù)處理機制結(jié)合還能消除多余的任務(wù)復(fù)制，最大限度彌補復(fù)制策略的不足。

圖2 任務(wù)調(diào)度表ScheduleList

二路復(fù)制策略算法：

binary_duplicating_policy(vi) {

int eft = MAX_INTEGER;

int p;

計算vi的最關(guān)鍵及次關(guān)鍵前驅(qū)任務(wù)vm1,vm2 ;

for pk ∈ P {

計算eft(vi,pk);

int min_eft(vi,pk) = eft(vi,pk);

if( vm1 不空 ) {

預(yù)復(fù)制vm1至pk上，計算eft'(vi,pk);

if(eft'(vi,pk) < eft(vi,pk)) {

記錄vm1的復(fù)制情況;

min_eft(vi,pk) = eft'(vi,pk);

if( vm1 不空 ) {

預(yù)復(fù)制vm2至pk上，計算eft"(vi,pk);

if(eft"(vi,pk) < eft'(vi,pk)) {

記錄vm2的復(fù)制情況;

min_eft(vi,pk) = eft"(vi,pk);

}

}

}

}

if(eft > min_eft(vi,pk)) {

eft = min_eft(vi,pk);

p=pk;

}

}

vi的調(diào)度為schedule(vi, p, est, eft);

將vi的調(diào)度及其前驅(qū)復(fù)制調(diào)度寫入ScheduleList;

改變空閑時間片狀態(tài);

}

1.4 冗余檢測與消除

采用復(fù)制技術(shù)能使每一個任務(wù)的調(diào)度都是局部最優(yōu)的，從而最小化整體調(diào)度長度，然而從全局上看，存在一部分復(fù)制任務(wù)只會影響局部處理器核上的調(diào)度時間，并不能減小全局的任務(wù)調(diào)度總時間，而消除這樣的任務(wù)也不會增加全局調(diào)度長度。這一部分被復(fù)制的前驅(qū)任務(wù)稱為冗余任務(wù)，該任務(wù)的調(diào)度稱為冗余調(diào)度。消除冗余調(diào)度后，在核上會產(chǎn)生一段空閑時間片，能提早后續(xù)任務(wù)最早開始時間。

上文提出的二路復(fù)制策略雖然能兼顧算法性能和時間復(fù)雜度，但相比于單復(fù)制策略，將前驅(qū)任務(wù)被冗余復(fù)制的機會增加了一倍，因此大幅增加了冗余任務(wù)的數(shù)量。采用冗余處理機制與二路復(fù)制策略結(jié)合，能夠在最小化調(diào)度長度的前提下，減少多余的復(fù)制任務(wù)數(shù)量，進(jìn)而減少資源占用和能耗，增加處理器的利用率。

1.4.1 檢測時機

對于單復(fù)制、水平多復(fù)制及本文的二路復(fù)制策略，一個任務(wù)的復(fù)制機會只存在其直接后繼任務(wù)調(diào)度的階段，即任務(wù)的復(fù)制與否是取決于其直接后繼任務(wù)的，一旦某個任務(wù)的所有直接后繼任務(wù)全部被調(diào)度完，那么后續(xù)的任務(wù)調(diào)度就不會涉及到對該任務(wù)的復(fù)制，所以此時是對該任務(wù)做冗余探測的最佳時機，即當(dāng)任務(wù)vi的所有直接后繼任務(wù)已經(jīng)全部被調(diào)度時，檢測vi的調(diào)度是否為冗余調(diào)度。

1.4.2 冗余消除

本文采用更廣泛的冗余任務(wù)定義：在任務(wù)集合完全執(zhí)行的前提下，凡是刪除后不增加調(diào)度總長度的調(diào)度都是冗余調(diào)度。任務(wù)之間的依賴關(guān)系體現(xiàn)在后繼任務(wù)將來自于所有前驅(qū)任務(wù)的數(shù)據(jù)接收完畢后才能開始執(zhí)行。消除冗余復(fù)制就是消除多余的直接前驅(qū)任務(wù)的副本，而消除冗余任務(wù)副本的前提是使直接后繼任務(wù)能從其他核上的直接前驅(qū)任務(wù)接收數(shù)據(jù)，解除前驅(qū)副本與其后繼的依賴關(guān)系。具體消除原則如下：

如果任務(wù)vi存在復(fù)制調(diào)度schedule(vi, pk, est, eft)，且調(diào)度符合下面任一條件：

(1)任務(wù)vi的所有位于pk核上的直接后繼任務(wù)都能從其他核上的前驅(qū)任務(wù)接收數(shù)據(jù)且完成時間不改變；

(2)設(shè)vj是vi的直接后繼任務(wù)且調(diào)度在當(dāng)前核pk上，若在vj的調(diào)度后存在一個空閑時間片idle_piece(pk, ist, ift)使得延遲vj調(diào)度的最早完成時間后滿足條件(1)。

那么稱schedule(vi,pk, est, eft)是冗余調(diào)度，將該調(diào)度從ScheduleList中刪除掉。具體算法如下：

冗余處理的算法

redundant_handle(vj) {

if(ScheduleList[j].dn <= 1)

continue;

獲取vj的復(fù)制調(diào)度集合schedule[](vj, pk, est, eft);

for(vj的復(fù)制調(diào)度schedule(vj, pk, est, eft)) {

獲取pk上vj的直接后繼vn;

if(min(Dat(vj,vn)) <= est(vn, pk)) {

ScheduleList.remove(vj, pk);

}else{

delta = min(Dat(vj, vn)) - est(vn, pk);

獲取idle_piece(pk, ist, ift)且ist>eft(vn,pk);

if(idle_piece != null && delta <= ift - ist) {

延遲vn的調(diào)度執(zhí)行時間;

ScheduleList.remove(vj, pk);

}

}

}

}

2 調(diào)度算法

2.1 算法描述

算法分為3個階段：任務(wù)優(yōu)先級計算階段，任務(wù)調(diào)度階段，冗余處理階段。其中任務(wù)優(yōu)先級計算階段產(chǎn)生調(diào)度優(yōu)先級隊列，再依次取出隊列首任務(wù)進(jìn)行任務(wù)調(diào)度和冗余處理。在任務(wù)處理階段采用二路復(fù)制策略，同時若在處理器核上存在合適大小的空閑時間片，優(yōu)先將任務(wù)插入到空閑時間片執(zhí)行，提早任務(wù)最早開始時間。根據(jù)上文對調(diào)度模型的闡述，給出調(diào)度算法如下：

schedule_algorithm(){

計算任務(wù)優(yōu)先級，獲取優(yōu)先級隊列 TaskList;

while( !TaskList.isEmpty() ) {

vi = TaskList.pop();

binary_duplicating_policy (vi);

if (存在vj∈prec(vi) && succ(vj)已經(jīng)完全調(diào)度) {

redundant_handle(vj);

}

}

}

2.2 時間復(fù)雜度分析

算法的時間復(fù)雜度主要由3個部分構(gòu)成：優(yōu)先級計算、任務(wù)調(diào)度、冗余處理。優(yōu)先級計算采用HEFT算法中的向上排序值rank作為任務(wù)優(yōu)先級，算法復(fù)雜度為O(v2)，v為任務(wù)數(shù)。任務(wù)調(diào)度采用二路復(fù)制策略，任務(wù)在核上計算最早完成時間eft(vi,pk)的時間復(fù)雜度為O(vp) ，v為任務(wù)數(shù)，p為處理器核數(shù)，所以任務(wù)調(diào)度時間復(fù)雜度為O(vp2)。冗余處理算法的時間復(fù)雜度為O(v2)，因此整體調(diào)度算法的時間復(fù)雜度為O(v2+v(vp2+v2))，即為O(n3)，不高于其他同類算法。

3 性能驗證

3.1 性能評估指標(biāo)

衡量調(diào)度算法性能的最基本指標(biāo)就是任務(wù)調(diào)度總長度makespan，而不同任務(wù)圖具有不同特性，因此需要對調(diào)度長度標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)化的調(diào)度長度被稱為SLR(Schedule Length Ratio)，是調(diào)度總長度與關(guān)鍵路徑上所有任務(wù)計算開銷之和的比值。關(guān)鍵路徑是DAG圖中的一條最長執(zhí)行路徑，是整個任務(wù)調(diào)度長度的瓶頸，SLR值越小說明算法性能越好，makespan和SLR計算公式如下

makespan=max{ft(vi,pk)|vi∈V,pk∈P|}

(7)

(8)

此外，為驗證冗余處理機制的有效性，在計算SLR的同時還應(yīng)計算調(diào)度算法產(chǎn)生的復(fù)制任務(wù)數(shù)量NoD(Number of Duplications)，等于實際調(diào)度任務(wù)數(shù)減去原任務(wù)數(shù)，NoD越小算法性能越好。

3.2 實驗方案

實驗的任務(wù)集采用隨機生成圖[16]的方式產(chǎn)生，選取五個隨機參數(shù)分別為任務(wù)數(shù)量N、處理器核數(shù)P、通信計算比CCR、任務(wù)結(jié)點最大出度α、異構(gòu)執(zhí)行時間影響因子β生成隨機任務(wù)圖，將本文的IDSRR算法與STDH算法、HLDOTS算法做對比實驗，分析各算法在不同實驗參數(shù)下的性能表現(xiàn)。隨機參數(shù)選取范圍如下：

SETN = {20, 40, 60, 80, 100} ;

SETP = {4, 8, 16, 32, 64} ;

SETCCR = {0.2, 0.5, 1.0, 2.0, 5.0} ;

SETα = {2, 4, 6, 8, 10} ;

SETβ = {0.1, 0.5, 1.0, 1.5, 2.0} .

上述參數(shù)設(shè)定產(chǎn)生3 125組任務(wù)圖類型，每組類型隨機生成10個任務(wù)圖，一共產(chǎn)生隨機任務(wù)圖個數(shù)為31 250。對生成的任務(wù)集合在模擬實驗平臺上調(diào)度，記錄實驗的性能評估指標(biāo)SLR和NoD的平均值。分別統(tǒng)計在不同任務(wù)數(shù)量和不同通信計算比的情況下，3種算法的性能評估指標(biāo)，實驗結(jié)果如圖3～圖6所示。

3.3 實驗結(jié)果分析與總結(jié)

圖3和圖4表示的是3種算法在任務(wù)數(shù)不同時的SLR和NoD比較，由實驗結(jié)果可以看出，隨著任務(wù)數(shù)的增加，SLR和NoD都呈上升趨勢。STDH算法采用多復(fù)制策略，所以其復(fù)制的任務(wù)數(shù)量最多，但是由于沒有對冗余的復(fù)制任務(wù)調(diào)度進(jìn)行檢測與消除，因此在調(diào)度長度方面的性能表現(xiàn)不如另外兩種算法；HLDOTS算法采用了單復(fù)制策略和冗余消除機制，復(fù)制任務(wù)數(shù)量明顯減少，但是對冗余的定義和處理方法單一，仍有部分冗余未被消除，從而失去了縮短后續(xù)調(diào)度完成時間的機會，因此在SLR上的表現(xiàn)不如本文算法；本文提出的IDSRR算法采用二路復(fù)制策略，能更好的平衡復(fù)制策略的性能優(yōu)勢和時間復(fù)雜度，加上與更進(jìn)一步的冗余處理機制相結(jié)合，因此在不同任務(wù)數(shù)的情況下，該算法的調(diào)度長度與任務(wù)復(fù)制數(shù)量均小于其余兩種算法，具有更好的性能。

圖3 任務(wù)數(shù)不同時的SLR

圖4 任務(wù)數(shù)不同時的復(fù)制任務(wù)數(shù)量

圖5和圖6表示的是3種算法在通信計算比CCR不同時的SLR和NoD比較。從總體趨勢來看，3種算法的調(diào)度長度和復(fù)制任務(wù)數(shù)量都會隨著CCR的增大而增大。當(dāng)CCR=0.2時，3種算法的性能差別不大，因為當(dāng)CCR較小時，任務(wù)集的通信開銷所占比例較小，復(fù)制策略并不會提前后繼任務(wù)的最早開始時間，也就不能帶來性能的收益。由圖5可知，在CCR=5時，STDH算法在SLR上的性能超過了HLDOTS算法，這是由于隨著CCR的增大，任務(wù)集的通信開銷所占比例增加，復(fù)制策略取得優(yōu)勢，而STDH算法的多復(fù)制策略相比于HLDOTS算法的單復(fù)制策略在最小化調(diào)度長度方面具有更明顯的優(yōu)勢，然而STDH算法對任務(wù)的復(fù)制數(shù)量也遠(yuǎn)遠(yuǎn)高于其余算法。同時也可以看出IDSRR算法在SLR和NoD兩個性能指標(biāo)上均優(yōu)于STDH算法和HLDOTS算法，這是由于二路復(fù)制策略在CCR較高時也會具有很好的減少調(diào)度長度的優(yōu)勢，而增強的冗余處理機制更能減少冗余復(fù)制，因此復(fù)制任務(wù)數(shù)量也小于STDH算法和HLDOTS算法。

圖5 CCR不同時的SLR

圖6 CCR不同時的復(fù)制任務(wù)數(shù)量

4 結(jié)束語

通過研究典型的基于復(fù)制的任務(wù)調(diào)度算法，分析這些算法存在的不足之處，提出一種改進(jìn)的異構(gòu)調(diào)度算法，該算法能發(fā)揮復(fù)制策略在最小化調(diào)度長度方面的優(yōu)勢，同時也克服了復(fù)制策略帶來的大規(guī)模冗余復(fù)制的缺陷。實驗結(jié)果表明，本文算法在通信計算比較大的情況下更能發(fā)揮優(yōu)勢。但是本文提出的冗余處理機制只能解決單復(fù)制、水平多復(fù)制以及本文提出的二路復(fù)制策略帶來的冗余復(fù)制問題，未能解決類似于HNDP算法中的垂直多復(fù)制策略導(dǎo)致的大規(guī)模冗余復(fù)制問題，這將是今后研究的方向。

[1] Bozdaǒ D,?zgüner, Füsun,et al. A task duplication based scheduling algorithm using partial schedules[C].France:International Conference on Parallel Processing,2005.

[2] Bansal S,Kumar P,Singh K.Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs[J].Journal of Parallel & Distributed Computing,2005,65(4):479-491.

[3] Hagras T,Janecek J,Hagras T.A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems[J]. Parallel Computing,2005, 31(7):653-670.

[4] Tang X, Li K,Liao G,et al.List scheduling with duplication for heterogeneous computing systems[J].Journal of Parallel & Distributed Computing,2010,70(4):323-329.

[5] Ahmad I,Kwok Y K.A new approach to scheduling parallel programs using task duplication[J].Proceeding of the ICPP, 1998(2):47-51.

[6] 蘭舟,孫世新.基于動態(tài)關(guān)鍵任務(wù)的多處理器任務(wù)分配算法[J].計算機學(xué)報,2007, 30(3):454-462.

[7] 吳佳駿.多核多線程處理器上任務(wù)調(diào)度技術(shù)研究[D].北京:中國科學(xué)院計算技術(shù)研究所, 2006.

[8] 李靜梅,孫冬微,韓啟龍.基于異構(gòu)CMP的靜態(tài)任務(wù)調(diào)度研究[J].小型微型計算機系統(tǒng), 2014(12):2770-2774.

[9] 陳茂強.一種基于DAG的并行系統(tǒng)任務(wù)調(diào)度方法[J].電子科技,2014,27(9):29-32.

[10] Topcuouglu H,Hariri S,Wu M Y. Performance-effective and low - complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel & Distributed Systems,2002,13(3):260-274.

[11] 耿曉中.基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D].長春:吉林大學(xué), 2013.

[12] 何琨,趙勇,黃文奇.基于任務(wù)復(fù)制的分簇與調(diào)度算法[J].計算機學(xué)報, 2005,31(5):733-740.

[13] Darbha S,Agrawal D P.Optimal scheduling algorithm for distributed-memory machines[J]. IEEE Transactions on Parallel & Distributed Systems,1998,9(1):87-95.

[14] Baskiyar S,Dickinson C.Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication[J].Journal of Parallel & Distributed Computing,2005,65(8):911-921.

[15] 孟憲福,劉偉偉.基于選擇性復(fù)制前驅(qū)任務(wù)的DAG調(diào)度算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2010,22(6):1056-1062.

[16] Salamy H,Ramanujam J.An effective solution to task scheduling and memory partitioning for multiprocessor system-on-chip[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2012, 31(31):717-725.

An Improved Duplication Based Heterogeneous Multi-core Scheduling Algorithm

ZHOU Chaoqun，ZHOU Yimin

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Duplication based heterogeneous multi-core task scheduling algorithms generally suffers redundant scheduling, low processor utilization, and high energy consumption. At present, some algorithms have been proposed to optimize the redundant scheduling problem. However, the detection of the redundancy by these algorithms is late with high time complexity, leaving little space for optimization, and. An improved duplication based heterogeneous multi-core task scheduling algorithm is proposed by combining the binary duplicating policy with the redundant processing mechanism to minimize the scheduling length while reducing the number of redundant replication tasks. Experimental results show that the proposed algorithm has better performance in aspects of reducing redundant tasks and minimizing the length of the task scheduling.

heterogeneous multi-core; duplication; task scheduling; redundancy handle; energy consumption

2016- 08- 01

周超群(1991-)，男，碩士研究生。研究方向：嵌入式系統(tǒng)。周亦敏(1962-)，男，副教授。研究方向：嵌入式系統(tǒng)等。

10.16180/j.cnki.issn1007-7820.2017.06.016

TP301.6

A

1007-7820(2017)06-057-06