一種基于異構(gòu)系統(tǒng)的實(shí)時(shí)調(diào)度算法研究

鄭小長(zhǎng),楊紅和

(1.閩南師范大學(xué) 信息與網(wǎng)絡(luò)中心，福建 漳州，363000；2.閩南師范大學(xué) 教務(wù)處，福建 漳州，363000)

?

一種基于異構(gòu)系統(tǒng)的實(shí)時(shí)調(diào)度算法研究

鄭小長(zhǎng)1,楊紅和2

(1.閩南師范大學(xué) 信息與網(wǎng)絡(luò)中心，福建 漳州，363000；2.閩南師范大學(xué) 教務(wù)處，福建 漳州，363000)

高效調(diào)度是異構(gòu)系統(tǒng)中實(shí)現(xiàn)高性能計(jì)算的關(guān)鍵.調(diào)度問題已經(jīng)被證明是NP完全問題，由于其關(guān)鍵性，調(diào)度問題已經(jīng)被國(guó)內(nèi)外研究機(jī)構(gòu)廣泛研究，并提出了多種算法.盡管在一些文獻(xiàn)中提出了異構(gòu)多處理器的調(diào)度算法，但是這些算法的調(diào)度成本較高，并且在較低的調(diào)度成本下無(wú)法提供高質(zhì)量的調(diào)度.本文提出一種最小評(píng)分優(yōu)先算法(HMSF)，該算法是一種適用于異構(gòu)系統(tǒng)的高性能、快速調(diào)度算法，通過和傳統(tǒng)的HEFT算法和DLS算法進(jìn)行試驗(yàn)對(duì)比發(fā)現(xiàn)，HMSF算法可以使調(diào)度長(zhǎng)度更短.

異構(gòu)系統(tǒng)；實(shí)時(shí)調(diào)度；DAG調(diào)度；任務(wù)圖；調(diào)度長(zhǎng)度

異構(gòu)計(jì)算系統(tǒng)是一種通過高速網(wǎng)絡(luò)將異構(gòu)計(jì)算資源連接到一起的計(jì)算平臺(tái)，可以對(duì)計(jì)算密集型的并行和分布式應(yīng)用提供支持[1].異構(gòu)計(jì)算系統(tǒng)在執(zhí)行應(yīng)用程序時(shí)需要編譯時(shí)和運(yùn)行時(shí)兩種方式的支持.對(duì)于應(yīng)用，對(duì)可用資源的有效調(diào)度是實(shí)現(xiàn)高性能的關(guān)鍵因素.

傳統(tǒng)的任務(wù)調(diào)度問題包括如何將程序分配到處理器上和如何對(duì)任務(wù)執(zhí)行順序進(jìn)行排序.一個(gè)程序可以通過靜態(tài)模型來(lái)表示，模型中的元素包括任務(wù)的運(yùn)行時(shí)間、任務(wù)間通信的數(shù)據(jù)量和任務(wù)之間的依賴關(guān)系等等[2-4].在傳統(tǒng)形式的靜態(tài)調(diào)度問題中，可以使用有向無(wú)環(huán)圖(DAG)來(lái)表示一個(gè)應(yīng)用，其中節(jié)點(diǎn)代表應(yīng)用程序中的任務(wù)，邊代表任務(wù)間的數(shù)據(jù)依賴關(guān)系.每個(gè)節(jié)點(diǎn)上標(biāo)識(shí)了該任務(wù)的計(jì)算時(shí)間消耗情況，邊上標(biāo)識(shí)了任務(wù)之間的數(shù)據(jù)通信消耗[4].該問題的研究目標(biāo)是將任務(wù)映射到處理器上，并且對(duì)他們的運(yùn)行進(jìn)行排序，從而實(shí)現(xiàn)在滿足任務(wù)優(yōu)先級(jí)的前提下，獲得總的最小的完成時(shí)間.任務(wù)調(diào)度問題通常被認(rèn)為是NP完全問題[5].

近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)任務(wù)調(diào)度問題進(jìn)行了充分的研究，并提出了如靜態(tài)任務(wù)調(diào)度算法、啟發(fā)式算法、列表調(diào)度算法、聚類啟發(fā)式算法、任務(wù)復(fù)制啟發(fā)式算法、遺傳算法和隨機(jī)引導(dǎo)搜索算法等方法[6-8].本文提出了一種靜態(tài)調(diào)度方法：最小評(píng)分優(yōu)先算法，盡管異構(gòu)系統(tǒng)的靜態(tài)調(diào)度都是離線調(diào)度，但是為了使調(diào)度方案更貼近實(shí)際，人們通常把算法的調(diào)度長(zhǎng)度(調(diào)度總時(shí)間)作為考量算法性能優(yōu)劣的關(guān)鍵約束條件.因此本文提出的算法的動(dòng)機(jī)是為了在保證高質(zhì)量調(diào)度的同時(shí)，盡量降低調(diào)度算法的資源消耗.

本文其余部分按如下組織：第2節(jié)主要描述了本文對(duì)異構(gòu)系統(tǒng)任務(wù)調(diào)度的理解，將任務(wù)調(diào)度抽象成數(shù)學(xué)模型，使用有向無(wú)環(huán)圖來(lái)表示任務(wù)集合，并給出一個(gè)異構(gòu)系統(tǒng)多任務(wù)調(diào)度的實(shí)例；在第3節(jié)中，詳細(xì)描述了最小評(píng)分優(yōu)先算法的計(jì)算過程，并給出第2節(jié)中給出的任務(wù)集合的調(diào)度方案；第4節(jié)通過仿真試驗(yàn)將多種不同調(diào)度算法進(jìn)行對(duì)比，通過比較試驗(yàn)數(shù)據(jù)來(lái)分析最小評(píng)分優(yōu)先算法的有效性、合理性和優(yōu)越性；在文章的最后，給出了全文的總結(jié).

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

任務(wù)調(diào)度模型由一個(gè)三元組表示.M=，其中G為應(yīng)用任務(wù)圖、Q為目標(biāo)系統(tǒng)、W為性能要求.應(yīng)用任務(wù)圖是一個(gè)有向無(wú)環(huán)圖G=(V,E)，其中V代表任務(wù)v的集合、E代表任務(wù)之間的邊e的集合.在任務(wù)圖中沒有父節(jié)點(diǎn)的任務(wù)叫做入口任務(wù)，沒有子節(jié)點(diǎn)的任務(wù)叫做出口任務(wù).假設(shè)目標(biāo)系統(tǒng)由一組異構(gòu)處理器集合Q組成，集合Q中的q個(gè)異構(gòu)處理器相互連接成拓?fù)浣Y(jié)構(gòu).在該模型中，計(jì)算時(shí)間包含通信消耗時(shí)間，并假定所有任務(wù)都是非搶占的.w是一個(gè)vXq的計(jì)算消耗矩陣，wi,j為任務(wù)ni在處理器Pj上的運(yùn)行時(shí)間預(yù)估值.在調(diào)度之前，所有任務(wù)使用平均運(yùn)行時(shí)間來(lái)標(biāo)識(shí).

任務(wù)ni的平均運(yùn)行時(shí)間定義該任務(wù)在所有處理器上運(yùn)行時(shí)間的總和除以q.

任務(wù)ni和任務(wù)nk的通信消耗定義為

其中，Tbuild代表處理器啟動(dòng)并建立通信所消耗的時(shí)間，S用于存儲(chǔ)不同處理器之間的數(shù)據(jù)傳輸速率，datai,k是任務(wù)ni向任務(wù)nk發(fā)送的數(shù)據(jù)量.如果任務(wù)ni和任務(wù)nk在用一個(gè)處理器上執(zhí)行，在這兩個(gè)任務(wù)之間沒有通信消耗，則ci,k的值為0.

平均通信消耗時(shí)間定義為

EST(ni,pj)為任務(wù)ni在處理器pj運(yùn)行的最早開始時(shí)間，EFT(ni,pj)為任務(wù)ni在處理器pj運(yùn)行的最早結(jié)束時(shí)間.對(duì)于入口任務(wù)nentry，

EST(nentry,Pj)=0.

在計(jì)算任務(wù)ni的EFT之前，該任務(wù)的所有前序任務(wù)必須全部調(diào)度完畢，即

EST(ni,pj)=max{avail[j],maxnm∈pred(nj)

(AFT(nm)+cm,i)},

EFT(ni,pj)=wi,j+EST(ni,pj),

其中，pred(ni)是任務(wù)的前序任務(wù)集合，avail[j]是處理器Pj的最早可用時(shí)間.如果任務(wù)ni是處理器pj執(zhí)行的最后一個(gè)任務(wù)，那么avail[j]就是處理器pj執(zhí)行完任務(wù)ni的時(shí)間.

當(dāng)任務(wù)nm被調(diào)度到處理器pj上運(yùn)行之后，EST(nm,pj)和該任務(wù)的實(shí)際開始時(shí)間AST(nm)相同，EFT(nm,pj)和該任務(wù)的實(shí)際結(jié)束時(shí)間AFT(nm)相同.當(dāng)任務(wù)圖中的所有任務(wù)都調(diào)度完成之后，調(diào)度完成時(shí)間為出口任務(wù)nexit的實(shí)際結(jié)束時(shí)間.

圖1是一個(gè)經(jīng)典的異構(gòu)系統(tǒng)執(zhí)行多任務(wù)的案例，該案例中共有10個(gè)任務(wù)，n1是入口任務(wù)，n10是出口任務(wù)，該異構(gòu)系統(tǒng)由兩個(gè)異構(gòu)處理器組成，表1展示了不同任務(wù)在不同處理器下的計(jì)算消耗.

圖1 任務(wù)圖Fig.1 Task graph

表1 任務(wù)計(jì)算消耗圖Table 1 task calculation consumption graph

2 任務(wù)調(diào)度算法

本文提出了一種基于優(yōu)先級(jí)評(píng)分的最小評(píng)分優(yōu)先算法(HMSF).HMSF(Heterogeneous-Minimal-Score-First)算法包含兩個(gè)階段：任務(wù)選擇階段和處理器選擇階段.

HMSF算法的第一個(gè)階段是任務(wù)選擇階段.在任務(wù)選擇階段中，算法根據(jù)任務(wù)ni的平均計(jì)算量和平均通信消耗計(jì)算出任務(wù)的優(yōu)先級(jí)評(píng)分sni，并對(duì)優(yōu)先級(jí)sni進(jìn)行降序排序.sni的計(jì)算方法為

HMSF算法的第二個(gè)階段是處理器選擇階段.對(duì)于大多數(shù)的任務(wù)調(diào)度算法，一個(gè)處理器的最早可用時(shí)間是該處理器所處理的上一個(gè)任務(wù)的截止時(shí)間.HMSF算法采用與常規(guī)方法相同的處理方法，當(dāng)處理器處于空閑時(shí)，就可以從就緒任務(wù)列表中按照任務(wù)選擇階段的方法挑選一個(gè)待調(diào)度的任務(wù)，分配給空閑的處理器.當(dāng)同時(shí)存在多個(gè)空閑處理器時(shí)，對(duì)于已選擇出的任務(wù)，找到執(zhí)行該任務(wù)運(yùn)行時(shí)間最短的處理器，將該任務(wù)分配到該處理器上，從而實(shí)現(xiàn)整體性能的最優(yōu)化.

HMSF算法的詳細(xì)描述如下:

1)為每個(gè)任務(wù)預(yù)估計(jì)算時(shí)間消耗和任務(wù)間通信時(shí)間消耗；

2)從出口任務(wù)向上遞歸遍歷任務(wù)圖，為所有任務(wù)計(jì)算優(yōu)先級(jí)評(píng)分；

3)對(duì)調(diào)度列表中的任務(wù)集合按照優(yōu)先級(jí)評(píng)分降序的順序排序；

4)對(duì)于每個(gè)為調(diào)度的任務(wù)進(jìn)行如下操作：

a)從任務(wù)列表中選取任務(wù)ni；

b)對(duì)于處理器集合中的每個(gè)處理器pj進(jìn)行如下操作：計(jì)算任務(wù)ni在處理器pj上的最早結(jié)束時(shí)間EST(ni,pj)；

c)將任務(wù)ni分配到處理器pj上，使得任務(wù)ni的最早結(jié)束時(shí)間EST(ni,pj)最小.

對(duì)于圖1中的案例，使用HMSF算法的計(jì)算過程圖表2所示，算法將得到如圖2所示的調(diào)度方案.

表2 優(yōu)先級(jí)得分表Table 2 Priority score table

圖2 調(diào)度方案Fig.2 Scheduling scheme

圖2的調(diào)度方案展示的調(diào)度方案為：

(1)選擇任務(wù)1分配給處理器P2，運(yùn)行時(shí)間區(qū)間為[0,9]；

(2)選擇任務(wù)3分配給處理器P1，運(yùn)行時(shí)間區(qū)間為[9,16]；

(3)選擇任務(wù)2分配給處理器P2，運(yùn)行時(shí)間區(qū)間為[9,27]；

(4)選擇任務(wù)4分配給處理器P1，運(yùn)行時(shí)間區(qū)間為[16,32]；

(5)選擇任務(wù)6分配給處理器P2，運(yùn)行時(shí)間區(qū)間為[27,41]；

(6)選擇任務(wù)7分配給處理器P1，運(yùn)行時(shí)間區(qū)間為[32,45]；

(7)選擇任務(wù)5分配給處理器P2，運(yùn)行時(shí)間區(qū)間為[41,63]；

(8)選擇任務(wù)8分配給處理器P1，運(yùn)行時(shí)間區(qū)間為[63,76]；

(9)選擇任務(wù)9分配給處理器P2，運(yùn)行時(shí)間區(qū)間為[63,77]；

(10)選擇任務(wù)10分配給處理器P1，運(yùn)行時(shí)間區(qū)間為[77,94].

任務(wù)集合在該異構(gòu)系統(tǒng)的調(diào)度長(zhǎng)度為94，處理器占用率為76%.

3 仿真試驗(yàn)

在本節(jié)中，我們通過使用幾種不同的調(diào)度算法來(lái)調(diào)度同一組任務(wù)圖來(lái)對(duì)比調(diào)度算法的性能.調(diào)度長(zhǎng)度是考核異構(gòu)系統(tǒng)調(diào)度算法最重要的指標(biāo)之一，調(diào)度長(zhǎng)度的長(zhǎng)短可以有效的衡量出調(diào)度算法調(diào)度結(jié)果的好壞程度.本文通過使用隨機(jī)圖形生成系統(tǒng)，隨機(jī)生成出3550個(gè)不同參數(shù)屬性的加強(qiáng)有向無(wú)環(huán)圖作為任務(wù)集合，并針對(duì)每個(gè)任務(wù)集合隨機(jī)生成了異構(gòu)系統(tǒng)計(jì)算消耗表，其中任務(wù)數(shù)量為{10,20,30,40,50,60,70,80,90,100}，處理器數(shù)量都是4.針對(duì)每個(gè)任務(wù)集合和其對(duì)應(yīng)的計(jì)算消耗表，本文選取了HEFT算法[6]、DLS算法[8]和HMSF算法進(jìn)行比較，比較結(jié)果如圖3所示.

圖3 調(diào)度算法對(duì)比結(jié)果Fig.3 Comparison of scheduling algorithms

圖3中展示了任務(wù)數(shù)量從10個(gè)增加到100個(gè)的過程中，不同算法調(diào)度長(zhǎng)度增長(zhǎng)的態(tài)勢(shì).從圖3中我們可以看出，隨著任務(wù)數(shù)量的增長(zhǎng)，各算法的調(diào)度長(zhǎng)度不斷增加，但HMSF算法的調(diào)度長(zhǎng)度相對(duì)更短，從實(shí)驗(yàn)結(jié)果可以看出，HMSF算法的調(diào)度效率更高.

4 結(jié)語(yǔ)

本文提出了一種基于優(yōu)先級(jí)評(píng)分的最小評(píng)分有限算法(HMSF)，該算法用于對(duì)異構(gòu)系統(tǒng)中的任務(wù)集合進(jìn)行合理調(diào)度.通過對(duì)大量隨機(jī)生成的任務(wù)圖進(jìn)行試驗(yàn)、對(duì)比和分析發(fā)現(xiàn)，HMSF算法的調(diào)度長(zhǎng)度明顯比其他算法短，調(diào)度效率更高.在未來(lái)的工作中，我們將對(duì)不同算法的調(diào)度質(zhì)量進(jìn)行更深入的調(diào)查和分析，同時(shí)我們計(jì)劃對(duì)HMSF算法進(jìn)行擴(kuò)展，實(shí)現(xiàn)對(duì)任務(wù)進(jìn)行重新調(diào)度以應(yīng)對(duì)處理負(fù)載和網(wǎng)絡(luò)負(fù)載的變化情況.

[1]RITCHIE G,LEVINE J.A fast effective local search for scheduling independent jobs in heterogeneous computing environments[C]//G Hay ward.Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group.Glasgow,UK:Journal of Computer Applications,2003:178-183.

[2]支青,蔣昌俊.一種適于異構(gòu)環(huán)境的任務(wù)調(diào)度算法[J].自動(dòng)化學(xué)報(bào),2005,31(6):835-872.

[3]IBARRA O H.Heuristic algorithms for scheduling independent tasks on non-identical processors[J].Journal of the ACM,1997,24(2):280-289.

[4]YEN TY,WOLF W.Hardware/Software Co-Synthesis of Distrubuted Embedded System[M].Netherlands:Kluwer Academic Publishers,1996.

[5]KWOK YK,AHMAD I.Dynamic critical-path scheduling:An effective technique for allocation task graphs to multiprocessors[J].IEEE Trans.On Parallel and Distributed Systems,1996,7(5):506-521.

[6]TOPCUOGLU H,HARIRI S,WU MY.Performance-Effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Trans.On Parallel andDis ributed Systems,2002,13(3):260-274.

[7]馮國(guó)富,董小社.面向Cell寬帶引擎架構(gòu)的異構(gòu)多核訪存技術(shù)[J].西安交通大學(xué)學(xué)報(bào),2009,43(2):1-5.

[8]SIH GC,LEE EA.A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures[J].IEEE Trans.On Parallel and Distributed Systems,1993,4(2):175-186.

Real-time scheduling algorithm based on heterogeneous systems

ZHENG Xiaochang1,YANG Honghe2

(1.Information and Network Center,Minnan Normal University,Zhangzhou 363000，China;2.Office of Educational Administration,Minnan Normal University,Zhangzhou 363000,China)

Efficient scheduling is the key to high performance computing in heterogeneous system.The scheduling problem has been proved to be NP-complete problem.Because of its significance,it has been studied extensively in research institutes at home and abroad,and a variety of algorithms have been put forward.Despite the fact that some scheduling algorithms of heterogeneous multi-core processor are proposed in some literatures,the scheduling cost of these algorithms is high and high-quality scheduling is not to be achieved at low cost of scheduling.In this paper,a minimum score priority algorithm (HMSF) is proposed.The algorithm is applicable in heterogeneous system with the advantage of high performance and speed.The HMSF can shorten the scheduling length,which is found in comparison tests between traditional heft algorithm and DLS algorithms.

heterogeneous systems; real-time scheduling ; DAG scheduling; task graph; scheduling length

1672-7010(2016)02-0036-05

2016-03-17

閩南師范大學(xué)教學(xué)改革項(xiàng)目(JG201542)

鄭小長(zhǎng)(1977-)，男，福建漳州人，碩士，講師，從事云計(jì)算、軟件工程研究；E-mail:53388110@qq.com

TP302

A