周超群，周亦敏

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

?

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

周超群，周亦敏

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

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

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

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

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

1 調(diào)度模型

在異構(gòu)多核系統(tǒng)中，一個(gè)任務(wù)通常被分解為多個(gè)有相互依賴關(guān)系的子任務(wù)，本文采用有向無環(huán)圖(Directed Acyclic Graph，DAG)[9]表示任務(wù)集。DAG圖的結(jié)點(diǎn)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)定義和部分變量的計(jì)算公式。

V={vi|vi是DAG中的第i個(gè)任務(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上的計(jì)算開銷}，其中i∈{0, 1, …,n-1}，k∈{0, 1, …,m-1}，m為多核處理器的核的數(shù)量。C={cij|cij是任務(wù)vi與任務(wù)vj的通信開銷}，若vi和vj被調(diào)度到同一個(gè)核上，則任務(wù)二者之間的通信開銷為零。

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

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

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

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

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

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

(1)

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

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

(6)

表2 向上排序值

1.3 復(fù)制策略

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

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

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

binary_duplicating_policy(vi) {

int eft = MAX_INTEGER;

int p;

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

for pk ∈ P {

計(jì)算eft(vi,pk);

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

if( vm1 不空 ) {

預(yù)復(fù)制vm1至pk上，計(jì)算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上，計(jì)算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;

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

}

1.4 冗余檢測(cè)與消除

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

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

1.4.1 檢測(cè)時(shí)機(jī)

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

1.4.2 冗余消除

本文采用更廣泛的冗余任務(wù)定義：在任務(wù)集合完全執(zhí)行的前提下，凡是刪除后不增加調(diào)度總長(zhǎng)度的調(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ù)且完成時(shí)間不改變；

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

ScheduleList.remove(vj, pk);

}

}

}

}

2 調(diào)度算法

2.1 算法描述

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

schedule_algorithm(){

計(jì)算任務(wù)優(yōu)先級(jí)，獲取優(yōu)先級(jí)隊(duì)列 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 時(shí)間復(fù)雜度分析

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

3 性能驗(yàn)證

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

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

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

(7)

(8)

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

3.2 實(shí)驗(yàn)方案

實(shí)驗(yàn)的任務(wù)集采用隨機(jī)生成圖[16]的方式產(chǎn)生，選取五個(gè)隨機(jī)參數(shù)分別為任務(wù)數(shù)量N、處理器核數(shù)P、通信計(jì)算比CCR、任務(wù)結(jié)點(diǎn)最大出度α、異構(gòu)執(zhí)行時(shí)間影響因子β生成隨機(jī)任務(wù)圖，將本文的IDSRR算法與STDH算法、HLDOTS算法做對(duì)比實(shí)驗(yàn)，分析各算法在不同實(shí)驗(yàn)參數(shù)下的性能表現(xiàn)。隨機(jī)參數(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ù)圖類型，每組類型隨機(jī)生成10個(gè)任務(wù)圖，一共產(chǎn)生隨機(jī)任務(wù)圖個(gè)數(shù)為31 250。對(duì)生成的任務(wù)集合在模擬實(shí)驗(yàn)平臺(tái)上調(diào)度，記錄實(shí)驗(yàn)的性能評(píng)估指標(biāo)SLR和NoD的平均值。分別統(tǒng)計(jì)在不同任務(wù)數(shù)量和不同通信計(jì)算比的情況下，3種算法的性能評(píng)估指標(biāo)，實(shí)驗(yàn)結(jié)果如圖3～圖6所示。

3.3 實(shí)驗(yàn)結(jié)果分析與總結(jié)

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

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

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

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

圖5 CCR不同時(shí)的SLR

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

4 結(jié)束語

通過研究典型的基于復(fù)制的任務(wù)調(diào)度算法，分析這些算法存在的不足之處，提出一種改進(jìn)的異構(gòu)調(diào)度算法，該算法能發(fā)揮復(fù)制策略在最小化調(diào)度長(zhǎng)度方面的優(yōu)勢(shì)，同時(shí)也克服了復(fù)制策略帶來的大規(guī)模冗余復(fù)制的缺陷。實(shí)驗(yàn)結(jié)果表明，本文算法在通信計(jì)算比較大的情況下更能發(fā)揮優(yōu)勢(shì)。但是本文提出的冗余處理機(jī)制只能解決單復(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] 蘭舟,孫世新.基于動(dòng)態(tài)關(guān)鍵任務(wù)的多處理器任務(wù)分配算法[J].計(jì)算機(jī)學(xué)報(bào),2007, 30(3):454-462.

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

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

[9] 陳茂強(qiáng).一種基于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].長(zhǎng)春:吉林大學(xué), 2013.

[12] 何琨,趙勇,黃文奇.基于任務(wù)復(fù)制的分簇與調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào), 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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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