基于A*算法的2種任務(wù)-處理器分配改進(jìn)算法

高衛(wèi)斌，柳曉龍

(1.寧德職業(yè)技術(shù)學(xué)院 信息技術(shù)與工程系，福建 寧德 355000；2.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002)

隨著計(jì)算機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，分布式計(jì)算系統(tǒng)已成為富有吸引力的選擇.為了利用分布式計(jì)算系統(tǒng)的有效并行性，必須把任務(wù)恰當(dāng)?shù)胤峙浣o處理器.把任務(wù)分配給處理器可以是動(dòng)態(tài)的或靜態(tài)的.

假設(shè)把一個(gè)并行程序用一個(gè)任務(wù)來表示，一個(gè)機(jī)器網(wǎng)絡(luò)用一個(gè)處理器來表示，則分配任務(wù)給處理器也稱為分配或映射問題[1-2]；已提出了眾多算法來實(shí)現(xiàn)分布式計(jì)算系統(tǒng)中的任務(wù)分配，如網(wǎng)絡(luò)流算法[3]、狀態(tài)空間搜索算法[4]、聚類算法[5]、裝箱算法[6]以及概率和隨機(jī)優(yōu)化算法[7-8].這些算法大多可以分為最優(yōu)算法和次優(yōu)算法；最優(yōu)算法可以進(jìn)一步分為條件限制的或無(wú)條件限制算法.次優(yōu)算法又分為近似算法或啟發(fā)式算法.

在大多數(shù)情況下，任務(wù)分配問題是NP-完全的[9].一種任務(wù)分配算法總是尋求使某個(gè)成本函數(shù)最優(yōu)化，如吞吐量最大或周轉(zhuǎn)時(shí)間最小.通常，最優(yōu)解可以通過窮舉搜索來得到，但由于這種方法中m個(gè)任務(wù)可以分配給n個(gè)處理器，因而有nm種方式，故窮舉搜索往往是不現(xiàn)實(shí)的.因此，最優(yōu)解算法僅存在于有條件限制的情況下或非常小型化的問題；另一種可能性是采用提示性搜索來減少狀態(tài)空間，如A*算法.盡管A*算法可以保證最優(yōu)解，但由于其很高的時(shí)間和空間復(fù)雜度而不能應(yīng)用于大型問題.

對(duì)此，本文在對(duì)A*算法原理分析的基礎(chǔ)上，提出了2種基于A*算法的改進(jìn)算法.一種是節(jié)省內(nèi)存空間和減少任務(wù)執(zhí)行時(shí)間的按序搜索最優(yōu)分配算法，一種是提高算法執(zhí)行時(shí)的加速性的并行搜索最優(yōu)分配算法.

1 問題模型及A*算法原理

1.1 問題模型

一般情況下，有2種任務(wù)圖模型：任務(wù)優(yōu)先圖(Task Precedence Graph,TPG)和任務(wù)交互圖(Task Interacting Graph,TIG)[10-12].TPG模型通過找到任務(wù)之間的優(yōu)先級(jí)關(guān)系來表示并行程序；在TIG模型中，多個(gè)任務(wù)可以同時(shí)運(yùn)行，而不考慮它們的優(yōu)先級(jí).

本文的目標(biāo)是將一個(gè)給定的任務(wù)圖分配給一個(gè)處理器網(wǎng)絡(luò)，以使程序完成所需的時(shí)間最小化.為使提出的算法兼具實(shí)用性和通用性，采用松弛假設(shè)和任務(wù)交互圖模型，把并行程序用一個(gè)無(wú)向圖來表示：

GT=(VT,ET) ，

(1)

式中VT為頂點(diǎn)集{t1,t2,…,tm}，ET為邊集(由任務(wù)之間的通信需求量來表示).也可以把處理器網(wǎng)絡(luò)表示為一個(gè)無(wú)向圖，其頂點(diǎn)代表處理器，邊界代表處理器的通信鏈路；用一個(gè)nn連接矩陣L表示n個(gè)處理器{p1,p2,…,pn}的互連網(wǎng)絡(luò)，如果處理器i和j是直接連接的，則L中的元素Lij為 1，否則為0，不考慮i和j不直接連接的情況.

可以在n個(gè)處理器系統(tǒng)上的任何一個(gè)處理器上執(zhí)行集合VT中的一個(gè)任務(wù)ti.每個(gè)任務(wù)在一個(gè)給定的處理器上都有一個(gè)相關(guān)的執(zhí)行成本，用矩陣X表示任務(wù)執(zhí)行成本，矩陣X中的元素Xip表示任務(wù)i在處理器p上的執(zhí)行成本；在2個(gè)不同處理器上執(zhí)行的2個(gè)任務(wù)ti和tj當(dāng)它們需要交換數(shù)據(jù)時(shí)會(huì)導(dǎo)致一個(gè)通信成本；任務(wù)映射將2個(gè)通信任務(wù)分配給同一處理器或2個(gè)直接連接的不同處理器；用矩陣C表示任務(wù)之間的通信，矩陣C中的元素Cij為任務(wù)i和j之間的通信成本(i和j為2個(gè)不同的處理器).

一個(gè)處理器的負(fù)荷(成本)包括與其分配的任務(wù)相關(guān)的全部執(zhí)行和通信成本，最重負(fù)荷處理器所需要的時(shí)間決定整個(gè)程序的完成時(shí)間；任務(wù)分配問題必須找到一組m個(gè)任務(wù)到n個(gè)處理器的映射，使得程序完成時(shí)間最小化.把任務(wù)分配(映射)給處理器用一個(gè)矩陣A來表示，如果任務(wù)i分配給處理器p，則Aip為1，否則為0，p上的負(fù)荷表示為：

(2)

式中第一部分為分配給處理器p的任務(wù)的總執(zhí)行成本，第二部分為處理器p上的通信開銷，Aip和Ajq分別表示任務(wù)i和j分配給2個(gè)不同的處理器p和q，Lpq表示p和q是直接連接的.為了找到最重負(fù)荷的處理器，需要計(jì)算n個(gè)處理器中每個(gè)處理器上的負(fù)荷.

1.2 A *算法原理

A*算法是一種優(yōu)先搜索算法，用公式表示為：

f(n)=g(n)+h(n) .

(3)

式中f(n)是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的估計(jì)成本，g(n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際成本，h(n)是從狀態(tài)n到目標(biāo)狀態(tài)的最短路徑的估計(jì)成本(對(duì)于路徑搜索問題，狀態(tài)就是圖中的節(jié)點(diǎn)，成本就是距離或時(shí)間).

為了找到最短路徑(最優(yōu)解)，關(guān)鍵在于成本函數(shù)f(n)的選取，由于g(n)很容易得到，所以f(n)的選取其實(shí)就是關(guān)于h(n)的選取.

為了得到成本函數(shù)f(n)，由于g(n)容易得到，所以主要是計(jì)算h(n)；為了計(jì)算h(n)，定義2個(gè)集合：Tp—分配給最重負(fù)荷處理器p的任務(wù)集，U—在搜索階段未被分配的任務(wù)集.U中的每個(gè)任務(wù)都將被分配給處理器p或與p有直接通信鏈路的任何其他處理器q.因此，可以把2種成本與每個(gè)ti的分配關(guān)聯(lián)起來：或者Xip(在p上的任務(wù)ti的執(zhí)行成本)或Tp中與ti鏈接的全部任務(wù)的通信成本的總和.這意味著考慮ti的分配，必須決定是否ti應(yīng)當(dāng)分配給p(考慮這2種情況下的最低成本).令cost(ti)為這兩個(gè)成本的最小值，則h(n)為：

h(n)=∑ti∈Ucost(ti) .

(4)

1.3 A *算法在任務(wù)分配中的應(yīng)用

下面用實(shí)例問題來說明A*算法在任務(wù)分配中的具體實(shí)現(xiàn)過程.

假設(shè)有5個(gè)任務(wù){(diào)t0,t1,t2,t3,t4}的任務(wù)集和3個(gè)處理器{p0,p1,p2}的處理器集，如圖1所示，圖1(a)中兩個(gè)任務(wù)之間的連線上的數(shù)字表示它們之間的通信成本，圖1(b)為3個(gè)處理器構(gòu)成的環(huán)形拓?fù)?，圖1(c)中的行數(shù)字是位于該行的任務(wù)分別在3個(gè)不同處理器上的執(zhí)行成本；采用A*算法得到的搜索樹如圖2所示.

圖1 實(shí)例任務(wù)集和處理器集

圖2 采用A*算法得到的搜索樹(生成42個(gè)節(jié)點(diǎn),14個(gè)擴(kuò)展節(jié)點(diǎn))

搜索樹節(jié)點(diǎn)(圖2中的矩形方框)包括分配給處理器的部分任務(wù)(方框中第一排帶X的內(nèi)容)和f值(方框中第二排圓括弧中的數(shù)字，即部分分配的成本).把m個(gè)任務(wù)分配給n個(gè)處理器用一個(gè)m進(jìn)制字符串a(chǎn)0,a1,…,am-1來表示，ai(0≤i≤m-1)表示算法已經(jīng)分配第i個(gè)任務(wù)的處理器(0～n-1).部分分配意味著某些任務(wù)未被分配；ai的值為X表示第i個(gè)任務(wù)還沒有被分配.樹的每級(jí)對(duì)應(yīng)一個(gè)任務(wù)，這樣，將這個(gè)任務(wù)分配給一個(gè)處理器來替換具有某個(gè)處理器編號(hào)的分配字符串中的X.節(jié)點(diǎn)擴(kuò)展意味著添加一個(gè)新的任務(wù)分配到部分分配中.因此，搜索樹的深度d等于任務(wù)數(shù)m，且樹的任何節(jié)點(diǎn)都可以有一個(gè)最大值后繼節(jié)點(diǎn)數(shù)n.

根節(jié)點(diǎn)包含全部未分配任務(wù)XXXXX的集合.如圖2，考慮把t0分配給p0(0XXXX)，t0分配給p1(1XXXX)和t0分配給p2(2XXXX)，以確定樹的第一級(jí)分配成本.把t0分配給p0(0XXXX)得到總成本f(n)等于30.在這種情況下，g(n)等于15，這就是在p0上執(zhí)行t0的執(zhí)行成本，h(n)也等于15，這就是t1和t4(與t0相連接的任務(wù))的最小執(zhí)行或通信成本的總和；類似地，可計(jì)算出把t0分配給p1的總成本是26，把t0分配給p2的總成本是24.算法將這3個(gè)節(jié)點(diǎn)插入到OPEN列表.因?yàn)?4是最小成本，故算法選擇節(jié)點(diǎn)2XXXX作為擴(kuò)展.

算法用下列方式擴(kuò)展節(jié)點(diǎn)2XXXX.在樹的第二級(jí)，算法會(huì)考慮分配t1，20XXX、21XXX和22XXX為3個(gè)可能的分配；對(duì)于20XXX，它的f(n)值是28，計(jì)算如下：選擇具有最重負(fù)荷的處理器，這時(shí)是p0，g(n)等于22，即在p0上執(zhí)行t1的執(zhí)行成本(14)加上t1和t0之間的通信成本(8)，因?yàn)樗鼈儽环峙浣o2個(gè)不同的處理器，h(n)等于6，這是t2的最小執(zhí)行或通信成本(唯一與t1相連接的未分配的任務(wù))；同樣方式可計(jì)算出21XXX和22XXX的f(n)值.這時(shí)，節(jié)點(diǎn)0XXXX、1XXXX、20XXX、21XXX和22XXX在OPEN列表中.由于節(jié)點(diǎn)1XXXX有最小的節(jié)點(diǎn)成本，故算法下一步擴(kuò)展它，得到節(jié)點(diǎn)10XXX，11XXX和12XXX.

圖2中某些節(jié)點(diǎn)上圓圈中的數(shù)字表示該節(jié)點(diǎn)被選擇為擴(kuò)展采用的順序，圖中的粗實(shí)線表示連接到得到最優(yōu)分配的節(jié)點(diǎn)邊界.搜索繼續(xù)進(jìn)行，直到進(jìn)程選擇具有完全分配(20112)的節(jié)點(diǎn)作為擴(kuò)展.這時(shí)，因?yàn)樵摴?jié)點(diǎn)具有完全分配和最小成本，所以它是目標(biāo)節(jié)點(diǎn)，全部分配字符串是唯一的；圖2中，算法考慮分配任務(wù)的順序是{t0，t1，t2，t3，t4}.在最優(yōu)解的搜索過程中，生成42個(gè)節(jié)點(diǎn)并擴(kuò)展14個(gè)節(jié)點(diǎn).

2 提出的改進(jìn)算法

2.1 按序搜索最優(yōu)分配算法

按序搜索最優(yōu)分配(Optimal Assignment with Sequential Search,OASS)算法采用A*搜索技術(shù)，但有2個(gè)明顯的不同.首先，算法得到一個(gè)隨機(jī)解，并刪除在最優(yōu)解搜索過程中比此解的成本高的全部節(jié)點(diǎn).刪除不必要的節(jié)點(diǎn)不僅節(jié)省了內(nèi)存，而且還節(jié)省了插入節(jié)點(diǎn)到OPEN所需的時(shí)間；其次，對(duì)于全部葉子節(jié)點(diǎn)，算法設(shè)置f(n)的值等于g(n)，因?yàn)閷?duì)于一個(gè)葉子節(jié)點(diǎn)n來說，h(n)等于0就避免了全部葉子節(jié)點(diǎn)上的h(n)的不必要的計(jì)算；算法實(shí)現(xiàn)的偽代碼如算法1所示，算法1對(duì)于前面的實(shí)例問題得到的搜索樹如圖3所示.顯然，算法的效率明顯得到提高.

圖3 按序搜索最優(yōu)分配算法得到實(shí)例問題的搜索樹

算法1 按序搜索最優(yōu)分配算法實(shí)現(xiàn)的偽代碼

1.得到一個(gè)隨機(jī)解

2.設(shè)S_opt為這個(gè)解的成本

3.對(duì)任務(wù)重新排序

4.構(gòu)建初始節(jié)點(diǎn)s并把它插入到OPEN列表

5.令f(s)=0

6.repeat

7.選擇具有最小f值的節(jié)點(diǎn)n

8.if(n不是解)

9.生成n的后繼節(jié)點(diǎn)

10.for每個(gè)后繼節(jié)點(diǎn)ndo

11.if(n不位于搜索樹的最后一級(jí))

12.f(n)=g(n)+h(n)

13.elsef(n)=g(n)

14.if(f(n)=S_opt)

15.插入n到OPEN列表

16.endfor

17.endif

18.if(n是解)

19.報(bào)告解并終止運(yùn)行

20.until(n是解)或(OPEN列表為空)

2.2 并行搜索最優(yōu)分配算法

并行搜索最優(yōu)分配(Optimal Assignment with Parallel Search,OAPS)算法是盡可能使用并行處理加速搜索，通過將搜索樹在處理單元(Processing Elements,PEs)之間盡可能均勻地進(jìn)行劃分和通過避免不必要的節(jié)點(diǎn)擴(kuò)展來實(shí)現(xiàn)的.算法基于系統(tǒng)中PEs的數(shù)目P以及搜索樹中一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)的最大數(shù)目S靜態(tài)地劃分搜索樹.為了說明算法原理，采用2個(gè)PE(PE1和PE2)，將10個(gè)任務(wù)分配給4個(gè)處理器.這里S為4，指一個(gè)搜索樹節(jié)點(diǎn)最多可以有4個(gè)后繼節(jié)點(diǎn)，即每個(gè)PE生成編號(hào)為1到4的4個(gè)節(jié)點(diǎn)，如圖4所示(圖中矩形框里的數(shù)字是節(jié)點(diǎn)的f值)，PE1得到分配的節(jié)點(diǎn)1和3，PE2得到節(jié)點(diǎn)2和4.

圖4 并行搜索最優(yōu)分配算法的初始靜態(tài)劃分

由于PEs被連成一個(gè)網(wǎng)狀拓?fù)洌室粋€(gè)PE最多可以有4個(gè)鄰居，且PE首先與它的鄰居通信，故得到相對(duì)較小的通信開銷，使得算法比采用全局通信策略更具可擴(kuò)展性.算法2所示為OAPS算法實(shí)現(xiàn)的偽代碼.采用初始負(fù)荷劃分，每個(gè)PE在它的OPEN列表中有1個(gè)或多個(gè)節(jié)點(diǎn)，全部PE建立起它們的鄰居來找到它們的相鄰PEs.一個(gè)PE確定它的鄰居是通過使用它自己的處理器網(wǎng)格位置和它的x、y坐標(biāo)；一個(gè)PE用初始節(jié)點(diǎn)擴(kuò)展開始節(jié)點(diǎn)，周期性地采用RR方式選擇一個(gè)鄰居，而且發(fā)送它最好的節(jié)點(diǎn)給鄰居來實(shí)現(xiàn)鄰近搜索空間的最好部分的共享；除了這種負(fù)荷均衡方式外，一個(gè)PE也廣播它的解(當(dāng)它得到一個(gè)解時(shí))給所有PE，這樣有助于避免一個(gè)PE不必要工作在搜索空間差的部分；一旦一個(gè)節(jié)點(diǎn)接收到一個(gè)比它目前最好節(jié)點(diǎn)還好的成本解，就停止擴(kuò)展不必要的節(jié)點(diǎn)；得到第一個(gè)解的PE廣播它的成本給所有其他PE.然后，當(dāng)且僅當(dāng)一個(gè)PE的成本優(yōu)于先前接收到的解時(shí)，它才廣播這個(gè)解；當(dāng)一個(gè)PE得到一個(gè)解時(shí)，則記錄下這個(gè)解并停止，即得到最低成本的最優(yōu)解.

算法2并行搜索最優(yōu)分配算法實(shí)現(xiàn)的偽代碼

1.初始劃分

2.建立鄰居

3.repeat

4.擴(kuò)展OPEN中最好成本的節(jié)點(diǎn)

5.if(得到一個(gè)解)

6.if(如果這個(gè)解比先前得到的任何解都好)

7.把這個(gè)解廣播給全部PE

8.else

9.告知鄰居

10.endif

11.記錄下解并終止運(yùn)行

12.endif

13.if(OPEN的長(zhǎng)度增加)

14.采用RR選擇一個(gè)臨近的PE j

15.發(fā)送OPEN中當(dāng)前最好的節(jié)點(diǎn)給j

16.endif

17.if(從鄰居接收到一個(gè)節(jié)點(diǎn))

18.把它插入到OPEN

19.if(從PE接收到一個(gè)解)

20.把它插入到OPEN

21.if(解發(fā)送者是一個(gè)鄰居)

22.從鄰居列表中移除它

23.endif

24.until(OPEN為空)或(OPEN為滿)

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

3.1 負(fù)荷生成

為了測(cè)試本文提出的2種改進(jìn)算法的性能，收集10～20個(gè)節(jié)點(diǎn)的任務(wù)圖數(shù)據(jù)和5個(gè)不同的通信-成本率(Communication-to-Cost Ratios,CCR)以及采用完全連接和環(huán)形2種不同拓?fù)浣Y(jié)構(gòu)的4節(jié)點(diǎn)處理器圖，對(duì)于OAPS算法，采用2、4、8和16個(gè)32位英特爾Paragon 作為PE，CCR的5個(gè)值取0.1、0.2、1、5和10.

3.2 OASS算法的存儲(chǔ)效率

首先來比較OASS算法和A*算法的內(nèi)存節(jié)省情況.A*和OASS都開始于重新排序任務(wù)，但OASS得到一個(gè)隨機(jī)解來消除不必要的節(jié)點(diǎn)，從而節(jié)省了大量?jī)?nèi)存，得到的實(shí)驗(yàn)結(jié)果如表1所示.從表1可見，CCR為0.1的4個(gè)處理器采用完全連接拓?fù)浣Y(jié)構(gòu)時(shí)，10～20個(gè)節(jié)點(diǎn)的任務(wù)圖的OASS算法生成的節(jié)點(diǎn)數(shù)和擴(kuò)展的節(jié)點(diǎn)數(shù)都要比A*算法少得多，平均節(jié)省內(nèi)存約72.14%.

表1 環(huán)形連接拓?fù)浣Y(jié)構(gòu)(CCR=0.1)時(shí)的內(nèi)存節(jié)省情況

表2為4個(gè)處理器在完全連接拓?fù)淝闆r下的A*算法和OASS算法得到的運(yùn)行時(shí)間.從表2可見，OASS算法在運(yùn)行時(shí)間上比A*算法有很大幅度的減少，A*算法對(duì)于16個(gè)以上的任務(wù)不能得到解，而本文的OASS算法相比于A*算法，不僅在運(yùn)行時(shí)間上有改善，而且能得到全部任務(wù)的解.

表2 完全連接拓?fù)浣Y(jié)構(gòu)時(shí)(CCR=0.1)的執(zhí)行時(shí)間

3.3 OAPS算法的加速性能

本節(jié)通過在不同數(shù)量的PEs上運(yùn)行本文提出的OAPS算法和A*算法，觀察2種算法的加速比，從而來評(píng)價(jià)OAPS算法的加速性能.表3所示為對(duì)于4個(gè)處理器在完全連接拓?fù)浜虲CR為0.1時(shí)得到的加速比結(jié)果.表的第二、第三、第四和第五列分別對(duì)應(yīng)于2、4、8和16個(gè)Paragon PE情況下的加速比，最后一行為所考慮的全部任務(wù)圖的平均加速比.從表3可見，在不同PEs數(shù)目的情況下，對(duì)于全部任務(wù)圖來說，OAPS算法與A*算法的加速比始終大于1，說明OAPS算法具有比A*算法更好的加速性；而且在相同PEs的情況下，加速比幾乎是呈線性的，隨著PEs數(shù)目的增加而增大，說明本文提出的OAPS算法是穩(wěn)定可靠的，同時(shí)有很好的擴(kuò)展性.

表3 全連接拓?fù)浣Y(jié)構(gòu)(CCR=0.1)時(shí)2種算法的加速比

4 結(jié) 論

分配問題的NP-完全性決定了其最壞情況下的復(fù)雜性為指數(shù)級(jí)，而本文提出的基于A*算法的2種改進(jìn)算法大大降低了復(fù)雜度，有助于得到中等規(guī)模問題的最優(yōu)解；按序搜索算法在內(nèi)存和時(shí)間方面得到了相當(dāng)大的改進(jìn)，而且采用完全連接的處理器拓?fù)浣Y(jié)構(gòu)將進(jìn)一步提高算法的性能；并行搜索算法在加速性能方面更有優(yōu)勢(shì)，如果不考慮最優(yōu)解而考慮接近于最優(yōu)的解，則有更好的加速性能.