一種低能耗低反應(yīng)時(shí)間的并行任務(wù)調(diào)度方法

摘 要：在各種網(wǎng)絡(luò)狀嵌入式系統(tǒng)如數(shù)字信號(hào)處理、車輛跟蹤和基礎(chǔ)設(shè)備監(jiān)控中，一般同時(shí)要求低的能量消耗和低的反應(yīng)時(shí)間。傳統(tǒng)的方法通常只集中考慮能量節(jié)約問(wèn)題，而沒(méi)有考慮最優(yōu)跨度問(wèn)題，這樣調(diào)度長(zhǎng)度可能非常長(zhǎng)的情況有時(shí)讓人無(wú)法容忍。在限制調(diào)度長(zhǎng)度的條件下最小化能量消耗，并提出了一種平衡能量消耗和反應(yīng)時(shí)間的算法EATA。實(shí)驗(yàn)結(jié)果證實(shí)了該算法的有效性。

關(guān)鍵詞：嵌入式系統(tǒng)； 能量消耗； 任務(wù)調(diào)度; EATA算法

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)06-2251-03

doi:10.3969/j.issn.1001-3695.2009.06.076

Energy-driven and low-latency parallel task allocation scheme

SONG Man， LI Chun-lin

(College of Computer Science Technical， Wuhan University of Technology， Wuhan 430063， China)

Abstract:

Parallel applications with energy and low-latency constraints are emerging in various networked embedded systems like digital signal processing， vehicle tracking， and infrastructure monitoring. However， conventional energy-driven task allocation schemes only concentrate on energy-saving rather than makespan of parallel applications. The situation of the long length of the schedules is unfavorable or even not tolerated. This paper addressed the issue of allocating tasks with an objective of energy-saving and short-latency. Proposed a novel task allocation strategy EATA. Experimental results demonstrate that proposed scheme is effective in a heterogeneous embedded system.

Key words：embedded system; energy-driven; task allocation; energy-aware task allocation(EATA)

所有的并行任務(wù)包括完成一個(gè)大的應(yīng)用任務(wù)的大量子任務(wù)，這些子任務(wù)彼此間能夠相互通信。在過(guò)去的十年里，隨著并行執(zhí)行平臺(tái)如目標(biāo)追蹤和基礎(chǔ)設(shè)備監(jiān)控的出現(xiàn)，網(wǎng)絡(luò)嵌入式系統(tǒng)越來(lái)越流行。這種趨勢(shì)很大程度上因?yàn)樘幚頇C(jī)能量、網(wǎng)絡(luò)帶寬和存儲(chǔ)能力的快速提高。但是在分布式移動(dòng)或無(wú)線環(huán)境中運(yùn)行的嵌入式系統(tǒng)通常只有低的能量?jī)?chǔ)備，因此能量節(jié)約問(wèn)題對(duì)嵌入式系統(tǒng)來(lái)說(shuō)變得尤為重要。

能量節(jié)約和低的反應(yīng)時(shí)間在并行任務(wù)調(diào)度中是兩個(gè)相沖突的方面，這種沖突來(lái)自于嵌入式系統(tǒng)節(jié)點(diǎn)資源的多維異構(gòu)性。提供最早任務(wù)完成時(shí)間的處理節(jié)點(diǎn)未必就是最能節(jié)約能量的節(jié)點(diǎn)，這是因?yàn)榉峙涞角度胧焦?jié)點(diǎn)的任務(wù)的執(zhí)行時(shí)間與該節(jié)點(diǎn)的能量消耗率無(wú)關(guān)，而子任務(wù)在處理節(jié)點(diǎn)的計(jì)算能量——消耗和能量消耗率與任務(wù)執(zhí)行時(shí)間有關(guān)。本文提出的問(wèn)題是當(dāng)系統(tǒng)中能量節(jié)約和反應(yīng)時(shí)間均被要求時(shí)，如何解決能量和反應(yīng)時(shí)間的兩難局面。

1 系統(tǒng)模型

嵌入式系統(tǒng)用一個(gè)數(shù)學(xué)模型表示任務(wù)的分配框架，包括一個(gè)前驅(qū)約束的并行任務(wù)模型和一個(gè)能量消耗模型。

1.1 網(wǎng)狀嵌入式系統(tǒng)

網(wǎng)狀嵌入式系統(tǒng)由一組向量P={p1，p2，…，pm}構(gòu)成。P表示單跳有線或無(wú)線網(wǎng)絡(luò)連接的異構(gòu)嵌入式計(jì)算節(jié)點(diǎn)。點(diǎn)對(duì)點(diǎn)連接的節(jié)點(diǎn)圖（圖1）表示網(wǎng)絡(luò)狀的嵌入式系統(tǒng)，圖中的頂點(diǎn)代表嵌入式節(jié)點(diǎn)。如果兩個(gè)節(jié)點(diǎn)能相互通信，兩個(gè)頂點(diǎn)間就用一條帶權(quán)值的邊連接。系統(tǒng)中每個(gè)節(jié)點(diǎn)都有一個(gè)能量消耗率（ECN），用朱利/單位時(shí)間來(lái)量度；同時(shí)每個(gè)網(wǎng)絡(luò)連接也有一個(gè)能量消耗率(ECL)。而通信能量消耗則由此鏈路上的傳遞率即鏈路帶寬，也就是對(duì)應(yīng)模型上邊的權(quán)值wij（表示節(jié)點(diǎn)pi與pj之間相連的邊）和通信能量消耗率ECL決定。用n×m二元矩陣X表示n個(gè)任務(wù)到m個(gè)節(jié)點(diǎn)的映射：當(dāng)任務(wù)ti被分配到節(jié)點(diǎn)pj上時(shí)，xij=1；否則，xij=0。這里的異構(gòu)性包含多層意思：a)任務(wù)在不同節(jié)點(diǎn)的執(zhí)行時(shí)間不同，因?yàn)椴煌蝿?wù)有不同的處理能力b)處理任務(wù)ti的執(zhí)行時(shí)間短的節(jié)點(diǎn)在處理另一任務(wù)tj時(shí)的執(zhí)行時(shí)間不一定短，因?yàn)椴煌?jié)點(diǎn)可能有不同的處理體系，這說(shuō)明系統(tǒng)中不同的節(jié)點(diǎn)適合不同的任務(wù)在其上執(zhí)行；c)每條鏈路的傳遞率即帶寬是不一樣的；d)每個(gè)節(jié)點(diǎn)的能量消耗率ECN也是不一樣的。在將一切損失忽略不計(jì)的前提下，假定系統(tǒng)中的所有節(jié)點(diǎn)是完全連接的，每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)通信來(lái)傳遞信息，并且分配到相同節(jié)點(diǎn)的兩個(gè)任務(wù)的通信時(shí)間忽略不計(jì)。

1.2 任務(wù)模型

相關(guān)任務(wù)的模型用定向無(wú)環(huán)圖DAG（圖2）表示。文中將并行任務(wù)的DAG圖看成一個(gè)二元組，即DAG（T，E）。其中：T={t1，t2，…，tn}表示一組計(jì)算子任務(wù)；E是一組含權(quán)值的有向邊，用來(lái)表示一組通信子任務(wù)。例如（ti，tj）∈E表示任務(wù)ti、tj之間的信息傳遞；E表示了任務(wù)的前驅(qū)約束。在節(jié)點(diǎn)pu上運(yùn)行的任務(wù)ti和在節(jié)點(diǎn)pv上運(yùn)行的任務(wù)tj之間的通信時(shí)間由sij/buv的值決定。其中sij是所傳遞的數(shù)據(jù)量，buv是指兩節(jié)點(diǎn)連接鏈路的數(shù)據(jù)傳遞率即帶寬的值。任務(wù)ti的執(zhí)行時(shí)間用向量Ci=(c1i， c2i，…， cmi)表示。其中cji表示任務(wù)ti在第j個(gè)節(jié)點(diǎn)上的執(zhí)行時(shí)間。

圖1~3是一個(gè)任務(wù)圖和網(wǎng)狀嵌入式系統(tǒng)的例子。此任務(wù)圖中包含11個(gè)任務(wù)和3個(gè)處理節(jié)點(diǎn)。節(jié)點(diǎn)p1和p2間的傳遞率(t12=t21)和通信能量消耗率(ECL12)分別為2和0.8；p1節(jié)點(diǎn)計(jì)算能量消耗率為12.6。二維向量給出了每個(gè)任務(wù)在每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間，如任務(wù)t1在三個(gè)計(jì)算節(jié)點(diǎn)的執(zhí)行時(shí)間分別為3.1 s、4.3 s和1.9 s。



1.3 能量消耗模型

系統(tǒng)的總能量消耗分成兩部分，即每個(gè)節(jié)點(diǎn)的計(jì)算能量消耗和節(jié)點(diǎn)間的通信能量消耗。

用eji表示任務(wù)ti運(yùn)行在節(jié)點(diǎn)pj上的能量消耗。ECNj表示第j個(gè)節(jié)點(diǎn)的能量消耗率，cji表示任務(wù)ti在節(jié)點(diǎn)j上的執(zhí)行時(shí)間。任務(wù)ti的計(jì)算能量消耗eji可用式(1)表示如下：

eji=ECNj×cji(1)

系統(tǒng)的能量消耗率ECN是一個(gè)一維向量集，由給出的并行任務(wù)集T和二維分配矩陣X表示。于是所有子任務(wù)總的能量消耗用式(2)表示如下：

en(T，X，ECN)=∑ni=1∑mj=1xij×eji=∑ni=1∑mj=1xij×ECNj×cji=

∑mj=1ECNj×∑ni=1xij×cji(2)

同樣，用êij表示信息（ti，tj）∈E傳遞的能量消耗，即通信能量消耗。假設(shè)ti和tj分別表示分配到節(jié)點(diǎn)u和v執(zhí)行的任務(wù)，可用式(3)表示節(jié)點(diǎn)間通信能量消耗：

êij=ECLuv(buv)×（Sij/buv）(3)

其中:ECLuv(buv)是節(jié)點(diǎn)u和v之間鏈路的能量消耗率；sij/buv是數(shù)據(jù)傳輸時(shí)間。注意這里鏈路的能量消耗率取決于鏈路的傳輸速度。本文的模型使用與文獻(xiàn)[1]相同的能量消耗延遲率。

鏈路的能量消耗率是一個(gè)m×m矩陣ECL=(ECLuv)。其中ECLuv是節(jié)點(diǎn)pu、pv之間鏈路的能量消耗率；而此鏈路的能量消耗用eluv(T，X，ECL）表示，指在此鏈路上所有信息傳遞所消耗的能量。鏈路的能量消耗eluv可用式(4)表示如下：

eluv(T，X，ECL)= ∑ei，ej∈Luvêij=∑ei，ej∈LuvECLuv(buv)×（Sij/buv）=∑ni=1 ∑nj=1，j≠ixiu×xjv×ECLuv(buv)×（Sij/buv）(4)

其中:Luv表示節(jié)點(diǎn)pu與pv之間鏈路的信息傳遞集合，Luv可定義為 Luv={(ti，tj)∈E，1≤u，v≤m|Sij＞0∧xjv=1}。

式(4)是假設(shè)所有鏈路的信息傳遞率是相同的情況，而實(shí)際情況不是這樣的。所以放棄先前的假設(shè)，假設(shè)不同的鏈路有不同的信息傳遞率。這里每條鏈路的信息傳遞率由文獻(xiàn)[1]提到的潛在的能量信息感知機(jī)制獲得。這里用定義bijuv表示鏈路節(jié)點(diǎn)pu、pv之間鏈路信息(ti，tj)傳遞時(shí)的速率，則eluv可用式(5)表示如下：

eluv(T，X，ECL)=∑ni=1∑nj=1，j≠ixiu×xjv×ECLuv(bijuv)×（Sij/buv）(5)

式(5)得到了一條鏈路的能量消耗，則整個(gè)系統(tǒng)的總的通信能量消耗el(T，X，ECL)用式(6)表示如下：

el(T，X，ECL)=∑ni=1 ∑nj=1，j≠i∑mu=1 ∑mv=1，v≠uxiu×xjv×ECLuv(bijuv)×（Sij/buv）(6)

由式(2)和(6)得到系統(tǒng)總的能量消耗為

e(T，X，ECN，ECL)=en(T，X，ECN)+el(T，X，ECL) (7)

2 EATA算法

算法EATA設(shè)計(jì)綜合考慮系統(tǒng)的任務(wù)調(diào)度和能量保存。為了使能量節(jié)約和調(diào)度長(zhǎng)度達(dá)到最好的平衡，引入了能量適應(yīng)窗口。其中每個(gè)任務(wù)選擇節(jié)點(diǎn)依據(jù)兩個(gè)指標(biāo)，即低的能量消耗和早的任務(wù)完成時(shí)間。

具體算法如下：

1.for 每個(gè)任務(wù) ti∈tdo

2. for 系統(tǒng)中每個(gè)節(jié)點(diǎn)pu∈p do

3. 計(jì)算estu(ti)的值 //由式(9)計(jì)算得來(lái)

4. 計(jì)算fu(ti)的值//由式(10)計(jì)算得來(lái)

5. end for

6. 根據(jù)任務(wù)ti的完成時(shí)間將所有的節(jié)點(diǎn)排序

7. for 每個(gè)在能量適應(yīng)窗口內(nèi)的節(jié)點(diǎn) do

8. 計(jì)算任務(wù)ti的能量消耗

9. for 任務(wù)ti的每個(gè)前驅(qū)節(jié)點(diǎn)tj do

10.計(jì)算（tj，ti）之間的通信能量消耗

11.計(jì)算ti總的能量消耗及其前驅(qū)節(jié)點(diǎn)傳送的信息量

12. end for

13.end for

14.為任務(wù)ti選擇能量消耗窗口中提供最小能量消耗的節(jié)點(diǎn)pv和從前驅(qū)節(jié)點(diǎn)傳遞的信息量的值

15.將任務(wù)ti分配到節(jié)點(diǎn)pv

16.更新節(jié)點(diǎn)pv的調(diào)度表

17.計(jì)算任務(wù)ti在pv上的能量消耗和任務(wù)ti收到的信息量值

18.記錄任務(wù)ti的開(kāi)始時(shí)間和完成時(shí)間

19.end for

算法通過(guò)減少能量消耗來(lái)增加處理節(jié)點(diǎn)的生存時(shí)間（第14步）。在最小化任務(wù)tj的能量消耗之前，算法將任務(wù)按其最早完成時(shí)間的非遞減序列排序。第8步計(jì)算任務(wù)tj在一個(gè)節(jié)點(diǎn)計(jì)算能量消耗；第9、10步計(jì)算節(jié)點(diǎn)tj接收它的前驅(qū)節(jié)點(diǎn)的消息所消耗的能量即通信能量消耗；第14步在所有的能量適應(yīng)窗口中列出的供選節(jié)點(diǎn)中選出最合適的節(jié)點(diǎn)，此節(jié)點(diǎn)擁有任務(wù)執(zhí)行和通信的最小的能量消耗，因此在沒(méi)有過(guò)分性能破壞的基礎(chǔ)上保存了能量；第15步將任務(wù)分配給最合適節(jié)點(diǎn)；在任務(wù)分配完成后，第16步更新每個(gè)節(jié)點(diǎn)的任務(wù)調(diào)度表。

算法提到的兩個(gè)重要的參數(shù)是節(jié)點(diǎn)的最早開(kāi)始時(shí)間和完成時(shí)間。將任務(wù)ti在節(jié)點(diǎn)pu的最早開(kāi)始時(shí)間和完成時(shí)間分別記為estu(ti)和fu(ti)。下面看如何得到這兩個(gè)參數(shù)：假設(shè)任務(wù)ti只有一個(gè)前驅(qū)任務(wù)tj，任務(wù)ti最早可能開(kāi)始時(shí)間estu(tj，ti)依賴三個(gè)參數(shù)：a)任務(wù)tj的完成時(shí)間fj；b)信息傳遞的開(kāi)始時(shí)間mst(tj，ti);c)傳送時(shí)間sji/bvu。其中信息從任務(wù)tj傳遞到任務(wù)ti，任務(wù)tj在節(jié)點(diǎn)pv上執(zhí)行。注意這里忽略了系統(tǒng)空轉(zhuǎn)時(shí)間，并且假設(shè)若兩個(gè)任務(wù)在同一處理節(jié)點(diǎn)上執(zhí)行，那么傳送時(shí)間忽略不計(jì)。由此可得estu(tj，ti)的計(jì)算式為

estu(tj，ti)= fjpu=pvmst(tj，ti)+sji/bvu其他(8)

任務(wù)ti的最早開(kāi)始時(shí)間estu(ti)是任務(wù)ti所有前驅(qū)節(jié)點(diǎn)estu(tj，ti)的最大值，即有

estu(ti)=max(tj，ti)∈E{estu(tj，ti)}(9)

節(jié)點(diǎn)完成時(shí)間由式(10)得到

fu(ti)=estu(ti)+cui(10)

3 性能評(píng)估

為了證實(shí)所提出的能量反應(yīng)時(shí)間任務(wù)調(diào)度算法的有效性，將EATA算法和LIST算法在相同的狀況下進(jìn)行比較。LIST算法是一個(gè)有名的并行任務(wù)的調(diào)度算法，其調(diào)度任務(wù)用最常見(jiàn)的DAG表示。該算法中，每個(gè)任務(wù)調(diào)度時(shí)選擇提供任務(wù)最早完成時(shí)間的計(jì)算節(jié)點(diǎn)。其中的最早完成時(shí)間考慮通信時(shí)間和計(jì)算時(shí)間。其目標(biāo)是DAG的最短調(diào)度長(zhǎng)度，也就是最優(yōu)跨度。

3.1 模擬的相關(guān)設(shè)置

本文提出模擬模型如下：計(jì)算節(jié)點(diǎn)的模擬參數(shù)類似于真實(shí)世界的Intel StrongARM 1100。能量消耗率與帶寬之間的對(duì)應(yīng)關(guān)系是：100 mW對(duì)應(yīng)100 kbps，即傳遞1 bit數(shù)據(jù)的時(shí)間和能量消耗是10 us和1 uJ(能量單位Joule)。所有的并行任務(wù)使用文獻(xiàn)[3]提出的TGFF方法生成；一個(gè)隨機(jī)的任務(wù)調(diào)度列表通過(guò)文獻(xiàn)[4]提出的方法生成。系統(tǒng)參數(shù)簡(jiǎn)單描述如表1所示。

表1 系統(tǒng)參數(shù)表



參數(shù)固定值變化值

任務(wù)數(shù)30050，100，…，500

能量適應(yīng)值窗口42，4，6，…，16

節(jié)點(diǎn)數(shù)60

能量消耗率1.2

標(biāo)準(zhǔn)節(jié)點(diǎn)能量消耗率200 mW

通信能量消耗率同文獻(xiàn)[1]中能量傳遞模型

根據(jù)表1任務(wù)數(shù)量、計(jì)算節(jié)點(diǎn)數(shù)量和任務(wù)執(zhí)行時(shí)間已經(jīng)生成，本文測(cè)試了其他工作參數(shù)對(duì)系統(tǒng)性能的影響。評(píng)估的參數(shù)包括：a)最優(yōu)跨度，DAG中最后一個(gè)任務(wù)的完成時(shí)間；b)能量消耗，總的能量消耗包括計(jì)算能量消耗和通信能量消耗。

3.2 總體性能比較

比較提出的EATA算法與傳統(tǒng)LIST算法在任務(wù)數(shù)量不同時(shí)最優(yōu)跨度和能量消耗的不同。實(shí)驗(yàn)結(jié)果如圖4、5所示。

從圖4可以看出兩種算法在最優(yōu)跨度方面的性能非常接近，但是當(dāng)任務(wù)數(shù)是300時(shí)，EATA算法比LIST算法最優(yōu)跨度小。由此可以看出傳統(tǒng)的LIST算法在生成最小的任務(wù)跨度值方面并不是最好的，因?yàn)樵诋悩?gòu)的環(huán)境下用LIST算法進(jìn)行任務(wù)調(diào)度時(shí)缺乏未調(diào)度任務(wù)的信息，并且在異構(gòu)的環(huán)境下不同節(jié)點(diǎn)上任務(wù)的執(zhí)行時(shí)間大大地不同。比較兩種算法的結(jié)果是EATA算法在僅僅增加跨度2.9%的基礎(chǔ)上節(jié)約能量12.1%。圖5說(shuō)明EATA算法在節(jié)能方面的性能比LIST算法好。

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

本文提出了異構(gòu)的嵌入式系統(tǒng)中考慮能量約束和反應(yīng)時(shí)間的并行任務(wù)分配問(wèn)題；同時(shí)提出了一種考慮能量消耗和調(diào)度串長(zhǎng)度的算法EATA解決這一問(wèn)題。關(guān)于EATA算法，本文提出了數(shù)學(xué)模型去描述系統(tǒng)框架、并行任務(wù)間的前驅(qū)約束和能量消耗模型。最后在真實(shí)的環(huán)境下作了大量模擬實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證實(shí)EATA算法大大減少任務(wù)分配時(shí)的能量消耗和反應(yīng)時(shí)間。相比LIST算法，EATA在節(jié)約能量消耗12.1%的基礎(chǔ)上僅僅增加了2.9%的反應(yīng)時(shí)間。

參考文獻(xiàn)：

[1]MOHAMMED A， TAO Xie， XIAO Qin. PARM: a power-aware message scheduling algorithm for real-time wireless networks[C]//Proc of the 1st ACM International Workshop on Wireless Multimedia Networking and Performance Modeling. New York:ACM Press， 2005: 86-92.

[2]XIAO Qin， HONG Jiang. A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters [J].Parallel and Distributed Computing，2005， 65(8):885-900.

[3]DICK R P， RHODES D L， WOLF W. TGFF:task graphs for free[C]//Proc of the 6th International Workshop on Hardware/Software Codesign. Washington DC:IEEE Computer Society，1998: 97-101.

[4]WOODSIDE C M， MONFORTON G G. Fast allocation of processes in distributed and parallel systems[J]. IEE Trans on Parallel and Distributed Systems，1993， 4(2): 164-174.

[5]都志輝，陳渝，劉鵬.網(wǎng)格計(jì)算[M].北京:清華大學(xué)出版社，2002:32-38.

[6]羅紅，慕德俊，鄧智群，等.網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2005，22(5):16-19.