基于A*算法的2種任務-處理器分配改進算法

高衛斌，柳曉龍

(1.寧德職業技術學院 信息技術與工程系，福建 寧德 355000；2.福建農林大學 計算機與信息學院，福建 福州 350002)

隨著計算機和計算機網絡的發展，分布式計算系統已成為富有吸引力的選擇.為了利用分布式計算系統的有效并行性，必須把任務恰當地分配給處理器.把任務分配給處理器可以是動態的或靜態的.

假設把一個并行程序用一個任務來表示，一個機器網絡用一個處理器來表示，則分配任務給處理器也稱為分配或映射問題[1-2]；已提出了眾多算法來實現分布式計算系統中的任務分配，如網絡流算法[3]、狀態空間搜索算法[4]、聚類算法[5]、裝箱算法[6]以及概率和隨機優化算法[7-8].這些算法大多可以分為最優算法和次優算法；最優算法可以進一步分為條件限制的或無條件限制算法.次優算法又分為近似算法或啟發式算法.

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

對此，本文在對A*算法原理分析的基礎上，提出了2種基于A*算法的改進算法.一種是節省內存空間和減少任務執行時間的按序搜索最優分配算法，一種是提高算法執行時的加速性的并行搜索最優分配算法.

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

1.1 問題模型

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

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

GT=(VT,ET) ，

(1)

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

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

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

(2)

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

1.2 A *算法原理

A*算法是一種優先搜索算法，用公式表示為：

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

(3)

式中f(n)是從初始狀態經由狀態n到目標狀態的估計成本，g(n)是在狀態空間中從初始狀態到狀態n的實際成本，h(n)是從狀態n到目標狀態的最短路徑的估計成本(對于路徑搜索問題，狀態就是圖中的節點，成本就是距離或時間).

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

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

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

(4)

1.3 A *算法在任務分配中的應用

下面用實例問題來說明A*算法在任務分配中的具體實現過程.

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

圖1 實例任務集和處理器集

圖2 采用A*算法得到的搜索樹(生成42個節點,14個擴展節點)

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

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

算法用下列方式擴展節點2XXXX.在樹的第二級，算法會考慮分配t1，20XXX、21XXX和22XXX為3個可能的分配；對于20XXX，它的f(n)值是28，計算如下：選擇具有最重負荷的處理器，這時是p0，g(n)等于22，即在p0上執行t1的執行成本(14)加上t1和t0之間的通信成本(8)，因為它們被分配給2個不同的處理器，h(n)等于6，這是t2的最小執行或通信成本(唯一與t1相連接的未分配的任務)；同樣方式可計算出21XXX和22XXX的f(n)值.這時，節點0XXXX、1XXXX、20XXX、21XXX和22XXX在OPEN列表中.由于節點1XXXX有最小的節點成本，故算法下一步擴展它，得到節點10XXX，11XXX和12XXX.

圖2中某些節點上圓圈中的數字表示該節點被選擇為擴展采用的順序，圖中的粗實線表示連接到得到最優分配的節點邊界.搜索繼續進行，直到進程選擇具有完全分配(20112)的節點作為擴展.這時，因為該節點具有完全分配和最小成本，所以它是目標節點，全部分配字符串是唯一的；圖2中，算法考慮分配任務的順序是{t0，t1，t2，t3，t4}.在最優解的搜索過程中，生成42個節點并擴展14個節點.

2 提出的改進算法

2.1 按序搜索最優分配算法

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

圖3 按序搜索最優分配算法得到實例問題的搜索樹

算法1 按序搜索最優分配算法實現的偽代碼

1.得到一個隨機解

2.設S_opt為這個解的成本

3.對任務重新排序

4.構建初始節點s并把它插入到OPEN列表

5.令f(s)=0

6.repeat

7.選擇具有最小f值的節點n

8.if(n不是解)

9.生成n的后繼節點

10.for每個后繼節點ndo

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

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.報告解并終止運行

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

2.2 并行搜索最優分配算法

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

圖4 并行搜索最優分配算法的初始靜態劃分

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

算法2并行搜索最優分配算法實現的偽代碼

1.初始劃分

2.建立鄰居

3.repeat

4.擴展OPEN中最好成本的節點

5.if(得到一個解)

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

7.把這個解廣播給全部PE

8.else

9.告知鄰居

10.endif

11.記錄下解并終止運行

12.endif

13.if(OPEN的長度增加)

14.采用RR選擇一個臨近的PE j

15.發送OPEN中當前最好的節點給j

16.endif

17.if(從鄰居接收到一個節點)

18.把它插入到OPEN

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

20.把它插入到OPEN

21.if(解發送者是一個鄰居)

22.從鄰居列表中移除它

23.endif

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

3 實驗結果

3.1 負荷生成

為了測試本文提出的2種改進算法的性能，收集10～20個節點的任務圖數據和5個不同的通信-成本率(Communication-to-Cost Ratios,CCR)以及采用完全連接和環形2種不同拓撲結構的4節點處理器圖，對于OAPS算法，采用2、4、8和16個32位英特爾Paragon 作為PE，CCR的5個值取0.1、0.2、1、5和10.

3.2 OASS算法的存儲效率

首先來比較OASS算法和A*算法的內存節省情況.A*和OASS都開始于重新排序任務，但OASS得到一個隨機解來消除不必要的節點，從而節省了大量內存，得到的實驗結果如表1所示.從表1可見，CCR為0.1的4個處理器采用完全連接拓撲結構時，10～20個節點的任務圖的OASS算法生成的節點數和擴展的節點數都要比A*算法少得多，平均節省內存約72.14%.

表1 環形連接拓撲結構(CCR=0.1)時的內存節省情況

表2為4個處理器在完全連接拓撲情況下的A*算法和OASS算法得到的運行時間.從表2可見，OASS算法在運行時間上比A*算法有很大幅度的減少，A*算法對于16個以上的任務不能得到解，而本文的OASS算法相比于A*算法，不僅在運行時間上有改善，而且能得到全部任務的解.

表2 完全連接拓撲結構時(CCR=0.1)的執行時間

3.3 OAPS算法的加速性能

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

表3 全連接拓撲結構(CCR=0.1)時2種算法的加速比

4 結 論

分配問題的NP-完全性決定了其最壞情況下的復雜性為指數級，而本文提出的基于A*算法的2種改進算法大大降低了復雜度，有助于得到中等規模問題的最優解；按序搜索算法在內存和時間方面得到了相當大的改進，而且采用完全連接的處理器拓撲結構將進一步提高算法的性能；并行搜索算法在加速性能方面更有優勢，如果不考慮最優解而考慮接近于最優的解，則有更好的加速性能.