面向單機相依任務(wù)調(diào)度的GPU并行蟻群算法

鄧向陽，張立民，劉 凱，黃曉冬

（海軍航空工程學(xué)院 a．電子信息工程系；b．科研部，山東 煙臺 264001）

當(dāng)前許多系統(tǒng)面臨的都是多機多任務(wù)的復(fù)雜環(huán)境，在一個系統(tǒng)內(nèi)會不斷出現(xiàn)需要服務(wù)的任務(wù)，并且在系統(tǒng)中往往存在多個可以進行服務(wù)的機器設(shè)備，對這類系統(tǒng)執(zhí)行效率的研究受到了高度重視。此類系統(tǒng)的優(yōu)化目的一般都是以執(zhí)行時間最小為目的，是一個調(diào)度排序問題。雖然現(xiàn)實中的多機系統(tǒng)很復(fù)雜，但是大量多機系統(tǒng)具有松散耦合的特性，不同機器之間任務(wù)的聯(lián)系不是非常緊密，不同機器之間的資源關(guān)聯(lián)很小，在這種多機系統(tǒng)的任務(wù)調(diào)度過程中，可采用單機系統(tǒng)模型的線性疊加實現(xiàn)。另外，單機系統(tǒng)本身也以實體形式存在于許多應(yīng)用領(lǐng)域。因此，有許多學(xué)者對單機調(diào)度問題進行了研究，如楊善林[1]等提出了一種啟發(fā)式算法，研究了部分可續(xù)型單機的最大完工時間調(diào)度問題；盧冰原[2]等采用粒子群算法研究了時間參數(shù)模糊化的多目標差異作業(yè)單機批調(diào)度問題模型；王栓獅[3]等采用蟻群算法對一種差異工件單機批調(diào)度問題進行了研究。

本文以單機相依任務(wù)調(diào)度問題(Dependent Task Scheduling on Single Machine，DTSSM)研究為重點，建立單機調(diào)度問題的優(yōu)化模型，基于通用計算架構(gòu)(Compute Unified Device Architecture，CUDA)在流多處理器(Stream Multi-Processors，SM)中實現(xiàn)基于局部信息素更新的實時種群進化機制，并通過多SM 上基于全局信息素更新機制的多種群協(xié)同規(guī)約，建立一種基于GPU 的并行蟻群算法，并將該算法結(jié)合單機調(diào)度問題模型，實現(xiàn)了一種低傳輸量、魯棒性好、并行化計算的單機相依任務(wù)調(diào)度算法。

1 單機相依任務(wù)調(diào)度問題模型

單機調(diào)度模型是應(yīng)用領(lǐng)域的一個基本問題，對其進行深入研究是研究復(fù)雜多機系統(tǒng)的基礎(chǔ)。單機調(diào)度模型主要討論多個任務(wù)在單個機器上的執(zhí)行過程，以達到效益最大化。

每個需要在機器上執(zhí)行的任務(wù)叫做一個單任務(wù)，其具有如下性質(zhì)：

1)由某個機器一次性單獨完成；

2)單任務(wù)需求之間可能相互依賴，單任務(wù)在不同執(zhí)行序下所需的時間不同。

據(jù)此，DTSSM 問題是一個相依多任務(wù)的排序問題，通過建立任務(wù)的作業(yè)順序，使得任務(wù)之間的相依性最大，完成時間最短。DTSSM 問題的數(shù)學(xué)模型可定義為P=＜ID,T,C＞，其中，P為單任務(wù)集合，ID為該任務(wù)的編碼集合，T為相依時間關(guān)系，C為任務(wù)執(zhí)行的順序號。

設(shè)有n個任務(wù){(diào)ei}，相依時間關(guān)系矩陣為T={tij}，tij表示ej在ei之后執(zhí)行時需要的時間，要求ej和ei之間具有緊前緊后執(zhí)行關(guān)系，執(zhí)行序變量為vi,x，其表示ei在第x序號執(zhí)行，得到的DTSSM問題模型為：

式(1)中2 個執(zhí)行序變量相乘表示的含義為：只有當(dāng)ei和ej具有緊前緊后執(zhí)行關(guān)系時，ej的執(zhí)行時間才計入總時間消耗。

相依時間矩陣T表示了不同任務(wù)相依關(guān)系下執(zhí)行時間的經(jīng)驗，則T為一個非對稱的非負矩陣，通過該矩陣定義了一個非對稱加權(quán)的有向圖G=(V,E)，其中頂點為任務(wù)ei的集合，弧為相依任務(wù)執(zhí)行時間的集合。如果兩節(jié)點代表的任務(wù)之間可以相繼執(zhí)行，則建立弧，權(quán)值大小代表了相依執(zhí)行序下的完成時間，如果2 個任務(wù)間不能夠相繼執(zhí)行，則節(jié)點之間不存在弧，而節(jié)點的自連接，為任務(wù)無緊前任務(wù)時的執(zhí)行時間。

通過上述轉(zhuǎn)換，相依任務(wù)單機調(diào)度問題轉(zhuǎn)為在每個G中搜索一條路徑，該路徑遍歷G的所有節(jié)點，使加權(quán)和最小。該問題可等效為一個 ATSP (Asymmetric traveling salesman problem)。

2 單機相依任務(wù)調(diào)度蟻群算法

蟻群算法(Ant Colony Optimization，ACO)是一種群智能算法，通過螞蟻個體之間的簡單行為涌現(xiàn)出復(fù)雜的計算能力，具有并行化、正反饋、自組織、容易實現(xiàn)等優(yōu)點，在不同領(lǐng)域得到了廣泛的應(yīng)用，ATSP 模型求解是蟻群算法的經(jīng)典應(yīng)用領(lǐng)域。本文研究的面向DTSSM 問題的蟻群算法模型以蟻群系統(tǒng)(Ant Colony System，ACS)[4]為基礎(chǔ)，針對單機相依任務(wù)調(diào)度問題進行設(shè)計，定義為單機相依任務(wù)調(diào)度蟻群算法(DTSSM based on ACO，DTSSM-ACO)。

DTSSM-ACO 算法通過偽隨機比例規(guī)則選擇相繼執(zhí)行任務(wù)，根據(jù)各條執(zhí)行路徑上的信息量和啟發(fā)函數(shù)值來計算狀態(tài)轉(zhuǎn)移概率。設(shè)表示螞蟻k在執(zhí)行完ei后繼續(xù)執(zhí)行ej的概率，可以通過下式計算：

式(3)中：α為信息啟發(fā)式因子，表示軌跡的相對重要性；β為期望啟發(fā)式因子，表示相依時間關(guān)系的相對重要性；τij為弧上的信息素密度；ηij為弧上的啟發(fā)函數(shù)的值。ηij可以通過下式計算：

式中，tij表示pj在pi之后執(zhí)行時的所需作業(yè)時間。

在每次迭代之后，全局信息素更新通過計算最優(yōu)路徑上的耗費時間得出，按照如下規(guī)則更新最優(yōu)路徑上的信息素：

式(5)中：Δτij為路徑上的信息素增量；Tm*為本輪最優(yōu)路徑所耗費的總時間；ρ為信息素揮發(fā)系數(shù)。

3 基于GPU的DTSSM-ACO算法并行化設(shè)計

3.1 蟻群算法的并行化設(shè)計

蟻群算法是一種自然的并行化算法，只有運行在并行環(huán)境中才能體現(xiàn)其效能。目前，已有學(xué)者針對蟻群算法研究了4 種層次上的并行化：種群層次的并行化、螞蟻層次的并行化、數(shù)據(jù)層次的并行化和函數(shù)層次的并行化[5]。對于種群層次的并行化和數(shù)據(jù)層次的并行化屬于粗粒度并行化，而螞蟻層次的并行化和函數(shù)層次的并行化屬于細粒度并行化。整體來說，對蟻群算法進行并行化研究的文獻較少，主要有M Dorigo[6]等實現(xiàn)了一種多種群的并行蟻群算法，得到了數(shù)據(jù)層次上的并行化設(shè)計；Marcus Randall[7]等設(shè)計了一種不需要通信的獨立多處理器并行蟻群算法；于濱[8]等在多處理機上實現(xiàn)了一種粗粒度的并行蟻群算法。

因為一般的并行化需要多個處理器執(zhí)行，多處理器的調(diào)度、并行編程等本身也是一個問題，廣泛應(yīng)用受到限制。因為GPU 的普及和結(jié)構(gòu)簡單等特點，近幾年有學(xué)者將蟻群算法移植到GPU 上實現(xiàn)：李建明[9]等人首次采用GPU 實現(xiàn)了一種細粒度的并行蟻群算法；趙元[10]等人提出了基于多叉樹并行蟻群算法的區(qū)位選址優(yōu)化方法，并采用GPU 對其實現(xiàn)了并行加速設(shè)計；白洪濤[11]等人實現(xiàn)了一種基于共享信息素矩陣的并行蟻群算法，并證明了算法是值收斂和解收斂的。

GPU 就是我們通常所說的顯卡的核心部分，它是一種浮點數(shù)處理器，是專為圖形數(shù)據(jù)這種計算密集型、高度并行化的情況而設(shè)計的。因此，面向GPU的設(shè)計必須轉(zhuǎn)化為標準的圖形處理過程，這種移植過程需要專業(yè)的圖形專業(yè)人員，實現(xiàn)難度大。

3.2 基于CUDA 的DTSSM-ACO 并行優(yōu)化

為了解決GPU 應(yīng)用專業(yè)受限的問題，NVIDIA公司于2007年推出了面向GPU 通用計算的CUDA架構(gòu)。CUDA 是一種將CPU 和GPU 協(xié)同進行計算的架構(gòu)，通過運行在CPU 上的程序進行任務(wù)的分支、選擇等操作，而采用GPU 完成面向數(shù)據(jù)的處理操作，在CPU 上串行處理，稱為Host 端的處理；在GPU 上并行處理，稱為Device 端的處理。在Host端的主控函數(shù)中，依次調(diào)用Kernel 函數(shù)進行串行運算，而每一個Kernel 函數(shù)都是一段GPU 計算過程，調(diào)用時都會將計算轉(zhuǎn)移到GPU 上執(zhí)行，執(zhí)行完之后返回。在Device 端的計算過程中，函數(shù)的處理過程被組織成大量的并行線程，進行同步處理。CUDA支持大量的線程并行，并在Device 中動態(tài)地創(chuàng)建、調(diào)度和執(zhí)行這些線程。

針對前述的DTSSM-ACO 算法，下面實現(xiàn)一種基于CUDA 的多蟻群并行進化，且各蟻群內(nèi)螞蟻并行執(zhí)行的兩級并行策略。首先，將每個蟻群組織為一個Block，所有Block 共用一個路徑矩陣存儲空間，每個Block 中的螞蟻進行某個任務(wù)階段的路徑搜索工作，每個Block 具有獨立的信息素存儲空間，通過共享存儲器實現(xiàn)通信；每個Block 對應(yīng)一個SM，在其中分配多個螞蟻，每個螞蟻對應(yīng)一個線程，在一個流處理器上執(zhí)行。

在上述的兩級并行策略中，每個蟻群屬于一個Block，該蟻群的所有螞蟻的私有信息，包括已有解路徑、禁忌表等信息，都存儲在共享存儲器中。獨立蟻群在計算過程中，每次螞蟻的移動都采用局部信息素更新策略更新信息素矩陣，信息素矩陣存儲在共享存儲器中，實現(xiàn)獨立種群的即時信息素共享；在所有獨立蟻群執(zhí)行完畢之后，將各自的信息素矩陣讀回CPU 內(nèi)存進行規(guī)約，并進行所有種群的信息素更新，該過程采用全局信息素更新策略，使不同獨立種群之間進行通信，達到所有螞蟻協(xié)同進化的目的。DTSSM-ACO 算法流程如圖1 所示。

圖1 DTSSM-ACO算法流程

4 實驗結(jié)果及分析

DTSSM-ACO 算法實驗的環(huán)境為：CPU 為Intel Core i5 760@2.8GHz；內(nèi)存為4GB RAM；操作系統(tǒng)為Windows 7，顯卡為GeForce GTX 460，CUDA的計算能力為2.1。實驗過程選取了50、100、200、400、800 個任務(wù)分5 次測試，任務(wù)之間的相依作業(yè)時間在[5, 15]之間隨機產(chǎn)生，每個種群輸出30 只螞蟻進行搜索，其他參數(shù)設(shè)置為ρ=0.1、α=2、β=1.2、τ0=0.001，算法循環(huán)300 次，由算法得到的全局最優(yōu)值曲線和加速比如圖2 所示。

圖2 最優(yōu)解變化過程和加速比

通過圖2 可分析知，算法在110 次迭代左右達到了收斂狀態(tài)，在后期保持了算法的穩(wěn)定性，表明DTSSM-ACO 算法具有可行性。同時，通過在GPU上的并行優(yōu)化設(shè)計，使得算法在5 種不同規(guī)模任務(wù)環(huán)境中得到了從3 到39 不等的加速比。在任務(wù)數(shù)較小時，得到的加速比小，這是因為任務(wù)數(shù)較小時并行算法的大部分時間花在從CPU 內(nèi)存上載數(shù)據(jù)到GPU 內(nèi)存，以及相反的數(shù)據(jù)傳輸過程，得不到好的加速效果，但是隨著問題規(guī)模的增大，大部分時間需要完成計算功能時，加速效果得到了明顯的改善。

5 結(jié)論

本文探討了一種單機相依任務(wù)調(diào)度問題，通過將該問題等效為非對稱TSP 問題，采用蟻群算法對其進行了求解，為了獲得更好的求解效率，對面向單機相依任務(wù)調(diào)度問題的蟻群算法基于GPU 進行了并行化設(shè)計，取得了較好的加速比。但是，本文沒有探討多機環(huán)境下的調(diào)度模型，也沒有對基于GPU 的并行化算法進行了更加深層次的加速，這將是后續(xù)的重點研究內(nèi)容。

[1] 楊善林, 馬英, 魯付俊. 帶不可用時間段的單機調(diào)度問題的啟發(fā)式算法[J]. 系統(tǒng)工程學(xué)報, 2011,26(4): 500-506.

[2] 盧冰原, 黃傳峰, 賈兆紅. 模糊環(huán)境下多目標差異作業(yè)單機批調(diào)度問題研究[J]. 控制與決策, 2011,26(11): 1675-1680.

[3] 王栓獅, 陳華平, 程八一, 等. 一種差異工件單機批調(diào)度問題的蟻群優(yōu)化算法[J]. 管理科學(xué)學(xué)報, 2009, 12(6):71-81.

[4] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[5] ANDRIES P ENGELBRECHT. 計算群體智能基礎(chǔ)[M]. 譚營, 譯. 北京: 清華大學(xué)出版社, 2009:303-306.

[6] M DORIGO, DI CARO G. The ant colony optimization meta-heuristic[R]. London: McGraw Hill, 1999.

[7] MARCUS RANDALL, JAMES MONTGOMERY. Candidate set strategies for ant colony optimization[R]. Queensland: School of Information Technology, Bond University, 2002.

[8] 于濱, 程春田, 楊忠振. 一種改進的粗粒度并行蟻群算法[J]. 系統(tǒng)工程與電子技術(shù), 2006,28(4):626-629.

[9] 李建明, 胡祥培, 龐占龍, 等. 一種基于GPU 加速的細粒度并行蟻群算法[J]. 控制與決策, 2009,24(8): 1132-1136.

[10] 趙元, 張新長, 康停軍. 并行蟻群算法及其在區(qū)位選址中的應(yīng)用[J]. 測繪學(xué)報, 2010,39(3):322-327.

[11] 白洪濤, 歐陽丹彤, 李熙銘 等. 基于GPU 的共享信息素矩陣多蟻群算法[J]. 吉林大學(xué)學(xué)報: 工學(xué)版, 2011,41(6):1678-1683.