黃震華， 趙振岐， 林培裕， 梅建華

(1.同濟大學 電子與信息工程學院，上海 200092；2.上海昕煜實業(yè)發(fā)展有限公司，上海 200062)

基于異構(gòu)平臺的并行最大最小蟻群算法

黃震華1， 趙振岐1， 林培裕1， 梅建華2

(1.同濟大學 電子與信息工程學院，上海 200092；2.上海昕煜實業(yè)發(fā)展有限公司，上海 200062)

最大最小螞蟻系統(tǒng)(Max-min Ant System，MMAS)是一種性能優(yōu)良的啟發(fā)式算法，常用于解決組合優(yōu)化問題.當解決的目標問題規(guī)模較大、迭代輪次較多時，最大最小蟻群算法存在運行時間長的缺點.試驗以開源串行包ACOTSP為基準，利用GPU多線程并發(fā)的優(yōu)勢，采用并行螞蟻策略將MMAS在CPU-GPU協(xié)同異構(gòu)計算平臺上并發(fā)實現(xiàn).算法在GPU上運行時的影響因素，如數(shù)據(jù)傳輸、內(nèi)存層次、庫函數(shù)調(diào)用等,也得到有效分析，并作出針對性優(yōu)化.試驗最終取得了高達13倍的加速，表明并行MMAS策略具有高效性和實用性.

并行計算； 異構(gòu)平臺； 最大最小蟻群系統(tǒng)； 加速比

蟻群優(yōu)化算法(ACO)[1]來源于真實螞蟻的覓食行為，常用于解決組合優(yōu)化問題.經(jīng)過改進而產(chǎn)生的最大最小螞蟻系統(tǒng)(MMAS)[2]由于其性能優(yōu)良在車輛調(diào)度[3]、路徑規(guī)劃[4]、服務組合[5]等方面都得到成功應用.然而，傳統(tǒng)蟻群算法在解決規(guī)模較大、迭代次數(shù)較多的目標問題時，都存在算法運行時間長、效率不高的缺點.并行ACO算法將組合優(yōu)化問題的求解過程分解為多個可并行執(zhí)行的邏輯單元，每個邏輯單元包含一定的計算量[6].將并發(fā)邏輯單元的計算量稱為并發(fā)粒度.通常，細粒度并行蟻群優(yōu)化算法使用并行螞蟻策略，粗粒度算法使用并行蟻群策略.

并行螞蟻策略：細粒度并行螞蟻策略僅使用一個蟻群，以螞蟻為并發(fā)邏輯單元，最初被Bullnheimer等[7]采用.基于消息傳遞及分布式內(nèi)存架構(gòu)，對螞蟻系統(tǒng)提出了2種并行策略:第1種策略粒度較細，以主從(master-slave)模式將螞蟻分配給不同的處理單元來加速運算,在每輪迭代中，master 將信息素值廣播給slave，并行計算路徑完成之后又將該值反饋給master,這些全局通信和同步帶來了明顯的時間消耗;第2種策略提升算法粒度，經(jīng)過一定迭代次數(shù)后再進行master和slave間的信息反饋，以此減少通信時間，從而提高運行速度.對于解的質(zhì)量方面，F(xiàn)u[8]針對并行螞蟻方案提出了新的隨機選擇算法——AIR(All-In-Roulette)，旨在通過提升隨機數(shù)的質(zhì)量來影響和提高解的質(zhì)量，防止系統(tǒng)的早熟現(xiàn)象.

并行蟻群策略：粗粒度并行蟻群算法以蟻群作為并發(fā)邏輯單元.該方案同樣基于消息傳遞及分布式內(nèi)存的計算模式，旨在將所有蟻群執(zhí)行在不同的處理單元，被Stützle[9]首先引入.Middendorf等[10]擴展了該方法，引入了4種蟻群間的信息交換方式：交換全局最優(yōu)解、循環(huán)交換局部最優(yōu)解、交換遷移、交換局部最優(yōu)解和遷移,結(jié)果表明并行蟻群策略可以有效降低多個蟻群副本間的通信量，減小同步開銷.

對于執(zhí)行單元分類，又可以分為CPU-GPU異構(gòu)平臺和CPU集群2種.

王詔遠等[11]基于內(nèi)存計算框架Spark實現(xiàn)了ACO算法，把螞蟻封裝為彈性分布式數(shù)據(jù)集，將信息素矩陣等全局信息利用Broadcast廣播共享，并通過調(diào)用Spark內(nèi)置的應用接口實現(xiàn)解構(gòu)造的并行化，最終取得了10倍以上的加速.

Delévacq等[12]以開源串行包ACOTSP為基準，采用了并行螞蟻和并行蟻群2種方式，實現(xiàn)了基于Fermi架構(gòu)GPU的最大最小螞蟻系統(tǒng)，并詳細闡述了試驗過程.在采用并行螞蟻(ant-thread)方案時，最高取得5.84倍的加速比.

雖然王詔遠等[11,13]將蟻群算法在Hadoop和Spark集群上實現(xiàn)，并取得了10倍以上的加速，但是硬件代價很大，所能解決的旅行商問題的城市規(guī)模也很有限.利用CPU-GPU異構(gòu)平臺實施蟻群算法，不僅具有代價優(yōu)勢，而且在城市規(guī)模增加時能夠提升性能.而以往蟻群算法在GPU上實現(xiàn)時雖然將計算量最大、消耗時間最長的路徑建立階段并發(fā)[12,14-15]，但并未對信息素矩陣的更新過程進行加速，Delévacq等[12]所采用的ant-thread方案的加速比也比較有限.

在對前文文獻進行理解和總結(jié)的基礎(chǔ)上，本文以經(jīng)典組合優(yōu)化問題——旅行商問題(Traveling Salesman Problem，TSP)[16]為目標，基于CPU-GPU異構(gòu)平臺運行并行版本的MMAS算法求解該問題，相較于傳統(tǒng)方式并發(fā)MMAS的路徑建立階段，為避免數(shù)據(jù)傳輸延遲而將信息素更新階段也并發(fā)實現(xiàn)，并對MMAS在GPU上運行時的優(yōu)化策略進行深入探究，最終算法取得了顯著的性能提升.以Stützle[9]所做的原始工作為基準，借助GPU多線程并發(fā)的優(yōu)勢，以并行螞蟻方式對ACO算法中的MMAS進行加速.按照Delévacq等[12]的建議，將不利于并發(fā)操作的local search[17]去除，運行基礎(chǔ)版本的蟻群算法.借鑒Dawson等[18]采用蟻群算法完成并行邊緣檢測的案例，通過控制信息素和距離的權(quán)重、迭代次數(shù)和螞蟻數(shù)目來維持解的質(zhì)量，提高運行速度和試驗效果.

1 問題描述

1.1 旅行商問題

1.2 蟻群算法

算法主要分為初始化、路徑建立和信息素更新3個階段.利用MMAS算法解決tsp問題的主要步驟偽代碼如下：

Initialize_CPU_memory_and_constants();

While( !termination_condition() ){

∥ants construct tours for tsp

TourConstruction();

PheromoneUpdate();

}

1.2.1 初始化

初始化階段主要完成路徑建立之前的數(shù)據(jù)準備工作.包括讀取tsp文件，計算距離矩陣(distance)，初始化信息素矩陣(pheromone)，申請螞蟻數(shù)組(ant_array)等操作.

1.2.2 路徑建立

該步驟對應偽代碼中的TourConstruction().

每只螞蟻具有如下屬性：走過的路徑、路徑的長度、走過城市的數(shù)量、當前所在城市編號、未訪問城市的集合.螞蟻搜索路徑流程如下：①隨機選擇一個城市作為螞蟻的出發(fā)點；②螞蟻依據(jù)狀態(tài)轉(zhuǎn)換規(guī)則(式(1))從未訪問城市集合中用“轉(zhuǎn)輪盤”方式[8]選擇下個待訪問城市；③循環(huán)執(zhí)行步驟②直到螞蟻周游所有城市1輪；④將螞蟻路徑中的城市按照距離依次求和；⑤判斷是否全部螞蟻都建立了路徑,如果為真，執(zhí)行步驟⑥,否則轉(zhuǎn)步驟①；⑥通過比較所有螞蟻的路徑長度獲得本輪最優(yōu)路徑.

在狀態(tài)轉(zhuǎn)換規(guī)則中，一只在城市i的螞蟻k通過式(1)計算訪問下個城市j的概率為

(1)

式中：τ為信息素；η為城市間距離的倒數(shù)；i,j為城市編號；N代表尚未訪問的城市集合；α,β分別為τ和η的權(quán)值.τ和η的值分別從信息素矩陣(pheromone)和距離矩陣(distance)中獲得，而α,β的值會影響解的收斂速度.

一次迭代的結(jié)果是生成本輪最優(yōu)路徑，這只是尋找最優(yōu)路徑過程中的一個步驟.在實際算法中需要設(shè)置螞蟻搜索的迭代次數(shù)或其他限制條件，即偽代碼中的termination_condition()，從而體現(xiàn)出信息素對螞蟻形成最優(yōu)解的引導作用，以便控制解的收斂速度，同時也防止程序無限執(zhí)行下去.

1.2.3 信息素更新

在得出本輪最優(yōu)路徑后，下一步要執(zhí)行信息素矩陣的更新操作，對應偽代碼中的PheromoneUpdate().該階段根據(jù)路徑建立階段的解對信息素矩陣進行更新，又分為信息素的蒸發(fā)與增強2個步驟.

(1)蒸發(fā).信息素矩陣的每個值都乘以參數(shù)γ，即

(2)

式中：τ(t)為第t輪迭代的信息素值，γ∈(0,1)，該步驟使得質(zhì)量較差的解隨著時間推移而被忘記.

(2)增強.包括經(jīng)典蟻群(Ant System)、MMAS、精英螞蟻系統(tǒng)(Elitist Strategy for Ant System，EAS)及基于排序的螞蟻系統(tǒng)(Rank Based version AS，ASrank)[14]等方法.

本文采用的是MMAS，特征是設(shè)置了信息素的最小值τmin和最大值τmax，且只有全局最優(yōu)或每輪最佳的路徑沉積信息素[16].操作如下：

(3)

式中：Δτij,best(t)=1/lenbest(t)，lenbest(t)是第t輪迭代產(chǎn)生的最優(yōu)路徑的長度.

因此螞蟻建立的路徑越短，該條路徑沉積的信息素就越多.一般情況下，被多數(shù)螞蟻經(jīng)過且屬于最短路徑的邊能夠沉積更多的信息素，因此更有可能在未來的迭代中被其他螞蟻選擇.從該種意義上，信息素τij代表了一只當前在城市i的螞蟻在下個城市選擇j的可取性.

2 并行蟻群優(yōu)化算法

在國際高性能計算組織HPC TOP 500公布的2015年榜單中，由中國國防科技大學研制的超級計算機“天河二號”依靠在Linpack基準測試最新版本中每秒33.86 千萬億次的表現(xiàn)再度榮登榜首，美國的超級計算機“泰坦”以每秒17.59千萬億次的浮點運算能力居于亞軍.綜觀整個榜單，除了使用數(shù)以萬計的Intel CPU以外，大多數(shù)超級計算機還采用了Nvidia GPU作為協(xié)處理器來提高性能，展現(xiàn)出很強的運算能力.

如今GPU在異構(gòu)計算平臺加速上的應用已經(jīng)越來越廣泛.相比于CPU，GPU將更多的晶體管用于數(shù)據(jù)處理，而非數(shù)據(jù)緩存和流控制，因此計算能力突出.其多流處理器、多線程的特點注定其適合并發(fā)操作.雖然主頻略低于CPU，但其并發(fā)優(yōu)勢卻令CPU望塵莫及.影響GPU加速的瓶頸往往在于數(shù)據(jù)傳輸?shù)臅r間，因此GPU更加適合處理數(shù)據(jù)傳輸次數(shù)較少而并行度高、計算密集的任務.

通常將CPU所在機器稱為主機，將GPU稱為設(shè)備[20].在主機上實現(xiàn)ACO 算法之后，采用CPU-GPU計算平臺對ACO算法進行提速，并測試不同的GPU內(nèi)存結(jié)構(gòu)以及不同參數(shù)對算法運行速度的影響,并對2種平臺下的試驗結(jié)果進行比較，主要包括運行速度、解的質(zhì)量等方面.

2.1 并行螞蟻策略

由于每只螞蟻獨立地搜索路徑，ACO算法的路徑建立階段本身具有良好的可并行性.但由于當前GPU架構(gòu)的限制，還無法將ACO算法完全運行在GPU上.依然要采取CPU作為主機、GPU作為設(shè)備的協(xié)同計算模式，將耗時最多的可并行部分在設(shè)備上運行，主機負責核函數(shù)調(diào)度和必要的串行處理.

采取并行螞蟻策略，以GPU作為協(xié)處理器，為每只螞蟻分配一個CUDA線程，并設(shè)置一定的迭代次數(shù).算法偽代碼如下：

Initialize_CPU_memory_and_constants();

copy_Distance_to_GPU();

Pheromone_initialize_on_GPU();

cuRand_generate_randoms_on_GPU();

While( !termination_condition() ){

∥each ant corresponds to a CUDA thread

antSearch_Kernel<<

N1>>>( Distance, Pheromone );

∥pheromone update in two steps

pheromoneEvaporate_Kernel<<<

ceil( cities*cities/N2 ), N2>>>

( Pheromone );

pheromoneEnhance_Kernel<<<1,

1>>>( Pheromone ); ∥single thread on GPU

copy_tour_from_GPU();

}

2.1.1 初始化

與串行版本一致，首先要進行tsp數(shù)據(jù)初始化.不同之處在于，信息素矩陣在設(shè)備端進行初始化(τ0)，而距離矩陣由主機端計算完畢后傳送到設(shè)備端.通過數(shù)組對每只螞蟻進行編號，為了在GPU上尋址的方便，需要申請一塊地址連續(xù)的空間存儲螞蟻相關(guān)數(shù)據(jù).其次，該步驟在GPU端生成了螞蟻搜索所需要的全部隨機數(shù)，并存儲在一個顯存數(shù)組中，供程序需要時讀取.在初始化tsp數(shù)據(jù)之后，執(zhí)行并行ACO 算法的路徑搜索過程，所有步驟均在設(shè)備端(GPU)實現(xiàn).流程如圖1.

2.1.2 路徑建立與信息素更新

并行蟻群算法最大的特點是為所有螞蟻分配線程，然后同時進行路徑建立過程.這能夠大大縮短路徑建立過程消耗的時間，同時掩蓋數(shù)據(jù)傳輸帶來的延遲.所有步驟均在GPU上進行，能最大限度地減少主機與設(shè)備間的數(shù)據(jù)傳輸.路徑建立及信息素更新采用多線程并發(fā)形式執(zhí)行，充分發(fā)揮GPU運算能力，而計算最優(yōu)路徑則以單線程方式在GPU上運行.

(1)初始化螞蟻數(shù)據(jù).利用GPU生成的隨機數(shù)同時為每只螞蟻隨機選擇城市作為出發(fā)點.

(2)螞蟻進行一次搜索.即螞蟻移動到下個待訪問城市，所有螞蟻同時執(zhí)行該步驟.原理同串行算法.

(3)循環(huán)執(zhí)行步驟(2)直到螞蟻周游全部城市1遍；為了保證并行螞蟻都建立自己的路徑以及數(shù)據(jù)安全，在該步驟結(jié)束時執(zhí)行_syncthreads()(線程同步)操作.

(4)計算螞蟻路徑長度.

(5)搜索當前螞蟻建立的最優(yōu)路徑.

(6)進行信息素矩陣更新.分為2步，首先對所有路徑同時執(zhí)行信息素蒸發(fā)操作，然后按照MMAS策略選擇當前最優(yōu)路徑沉積信息素.該步驟對于之后螞蟻建立路徑具有引導作用.

(7)判斷是否滿足終止條件.

步驟(1)至(5)對應圖1中核函數(shù)antSearch_Kernel，步驟(6)對應pheromoneEvaporate_Kernel，pheromoneEnhance_Kernel.核函數(shù)參數(shù)如ants/N1,N1,它們分別表示線程塊數(shù)和每個線程塊中的線程數(shù)，其中ants代表螞蟻數(shù)量.核函數(shù)的線程組織實際是對串行算法中for循環(huán)的分解，在盡可能增大數(shù)據(jù)并行度的同時，避免因數(shù)據(jù)相關(guān)性引起“寫沖突”，從而導致解的質(zhì)量下降.其中，pheromoneEnhance的并發(fā)性是由MMAS的特點決定的.由于每輪迭代結(jié)束后只有建立當前最優(yōu)路徑的螞蟻執(zhí)行信息素增強的操作，不存在2只螞蟻同時修改信息素矩陣的情況，因此避免了“寫沖突”.其并發(fā)點在于可以對當前最優(yōu)路徑的不同路段同時進行信息素的增強操作.

如果給定城市規(guī)模為n，則解空間的大小為n!.由于采用啟發(fā)式解法，MMAS求解TSP問題的時間復雜度為O(mn2)，其中m是螞蟻數(shù)量.由分析可知，路徑建立階段的時間復雜度為O(n2)，且需要重復m次.而算法其他部分所需計算量均少于建立階段，如路徑評估的時間復雜度為O(mn)，信息素揮發(fā)的時間復雜度為O(n2).假設(shè)有q個可用的并行處理單元，理論上算法時間復雜度可以降為O(mn2q-1).在并行MMAS策略中，可用的并行處理單元的數(shù)目即為核函數(shù)的2個參數(shù)(線程、線程塊數(shù))的乘積.

2.2 優(yōu)化技術(shù)

經(jīng)過對并行程序的分析，將影響加速比的因素列舉如下，并給出相應的優(yōu)化策略.

(1)數(shù)據(jù)傳輸.在主機和設(shè)備之間傳送數(shù)據(jù)造成的延遲是限制程序性能提升的重要因素.以往ACO程序的任務劃分是將具有并行特性、且消耗時間最多的路徑建立階段在GPU上并發(fā)，而對最優(yōu)路徑的求解和信息素的更新在CPU上進行.由于距離矩陣和信息素矩陣的規(guī)模均為n2，隨著城市規(guī)模的增加，二者的大小以平方形式增長.考慮到數(shù)據(jù)傳輸帶來的延遲以及充分發(fā)揮GPU的運算能力，將信息素的更新步驟在GPU上進行多線程并發(fā)，而最優(yōu)路徑求解以單線程方式在GPU上執(zhí)行.每輪迭代結(jié)束時只傳送當前最優(yōu)解，如此一來距離矩陣和信息素矩陣就可以常駐設(shè)備內(nèi)存，最大限度避免設(shè)備和主機之間的數(shù)據(jù)傳輸.

(2)冪次計算.每只螞蟻在計算狀態(tài)轉(zhuǎn)換規(guī)則時都要用到α和β，由于是冪次運算，所以存在相當大的浮點計算量.以往蟻群算法在計算狀態(tài)轉(zhuǎn)換規(guī)則(式(1))時，對于冪次的計算均通過C庫函數(shù)(頭文件“math.h”)中的pow函數(shù)來完成.經(jīng)研究發(fā)現(xiàn)，調(diào)用pow函數(shù)并傳參(雙精度)的開銷較大，會消耗許多寄存器，并且會破壞CPU的分支預測和緩存優(yōu)化.而在GPU端調(diào)用該庫函數(shù)由于需要啟動總線，開銷更是成倍增加.但是α和β的值往往是較小的整數(shù)，對于概率p的計算可以簡化為手動相乘，這樣一來大大減少了計算量，非常有利于程序在GPU上速度的提升.而pow函數(shù)最好在求非整數(shù)冪時采用.

(3)隨機數(shù).螞蟻在選擇出發(fā)城市和下個城市時需要用到隨機數(shù).隨機數(shù)由主機生成后傳送給設(shè)備的開銷較大，由GPU調(diào)用CUDA隨機數(shù)庫cuRand生成隨機數(shù)可以節(jié)省時間.

(4)城市數(shù)目與螞蟻只數(shù).CUDA文檔[21]強烈建議使用每塊的線程是線程束(warp，由連續(xù)的32個線程組成)的倍數(shù)，因此選擇與城市數(shù)目相接近的2n作為螞蟻數(shù)目，以便最大限度提升計算效率.同時適當增加螞蟻數(shù)目也能夠加快解的收斂速度.

(5)并行度.采用單個螞蟻對應單一線程的方式，如果在一個線程塊(block)中設(shè)置的線程數(shù)過多，會由于線程間的資源競爭(register)而導致程序運行速度減慢.同一block中的所有線程都會被分配到同一個處理器核上運行，共享有限的存儲資源.應根據(jù)螞蟻數(shù)目設(shè)置相應block中的thread數(shù)量.

(6)內(nèi)存層次.在GPU端，相比于全局內(nèi)存(global memory)，紋理內(nèi)存(texture memory)是有緩存(cache)的.如果同一個warp內(nèi)thread的訪問地址很相近，那么訪問速度更快，性能會更高.因此使用紋理內(nèi)存的效果要好于全局內(nèi)存.本文對2個最大的矩陣——距離矩陣和信息素矩陣，采用紋理內(nèi)存進行存儲.

3 試驗設(shè)計與結(jié)果分析

3.1 試驗設(shè)計

利用Linux性能分析工具Gprof[22]對ACO 算法進行分析，能夠找到消耗最多運行時間的函數(shù).基于不同的tsp，分析結(jié)果顯示TourConstruction()階段占總運行時間的95%以上，并且隨著城市數(shù)目增加該比例呈上升趨勢.由Amdahl加速比定律[23]可知，如果將TourConstruction()階段并發(fā)，理論上最大加速比可達10倍以上.

由于本文盡力使并行MMAS各計算階段的前驅(qū)后繼關(guān)系與原始串行算法相照應，宏觀上二者具有相同的執(zhí)行邏輯，且GPU的運算精度與CPU相當[21]，因此在提高加速比的同時能夠保持解的質(zhì)量.根據(jù)并行螞蟻思想，以單個螞蟻對應單一線程的方案實現(xiàn)了基于CPU-GPU異構(gòu)平臺的并行MMAS算法.

試驗中相關(guān)參數(shù)的值設(shè)置如下：α=2.0，β=3.0，γ=0.1，迭代次數(shù)為1 000.進行測試的tsp文件均來自通用測試集TSPLIB[24]，并選擇與城市數(shù)目相接近的2n作為螞蟻數(shù)目.由于每次試驗過程中所產(chǎn)生的隨機數(shù)不盡相同，導致結(jié)果會有細微差異，因此取5次測試結(jié)果的平均值作為最優(yōu)路徑長度.

試驗環(huán)境如下：①硬件環(huán)境.CPU：Intel Xeon E5-2620 處理器，六核十二線程，主頻2.00GHz，最大睿頻2.60GHz；QPI總線.GPU：NVIDIA Tesla K20C，參數(shù)詳見表1.②軟件環(huán)境.CentOS Linux release 7.1 64位操作系統(tǒng)，NVCC編譯器，CUDA7.5版本.

3.2 數(shù)據(jù)采集與分析

(1)第1次試驗.并行MMAS采用pow函數(shù)計算狀態(tài)轉(zhuǎn)換規(guī)則(式(1))，部分結(jié)果見表2.

表1 Tesla K20C計算卡參數(shù)Tab.1 Specifications of Tesla K20C

表2 采用pow函數(shù)計算MMAS狀態(tài)轉(zhuǎn)換規(guī)則的部分結(jié)果Tab.2 Partial results of MMAS computing transition rules with pow function

(2)第2次試驗.并行MMAS采用直接相乘方式計算狀態(tài)轉(zhuǎn)換規(guī)則(式(1))，部分結(jié)果見表3.

表3 采用直接相乘計算MMAS狀態(tài)轉(zhuǎn)換規(guī)則的部分結(jié)果Tab.3 Partial results of MMAS computing transition rules by direct multiplying

依據(jù)2次試驗結(jié)果作圖如圖2.結(jié)果表明，將MMAS算法耗時最多的路徑建立過程及信息素矩陣更新過程在CPU-GPU異構(gòu)平臺上進行并發(fā)執(zhí)行，在城市規(guī)模達到一定數(shù)量時，并行MMAS(pow)對串行算法體現(xiàn)出明顯的性能提升，最大加速比可達8.16，且解的質(zhì)量也與串行算法基本保持一致.對于設(shè)備端pow函數(shù)的優(yōu)化使得并行MMAS(pow)在加速基礎(chǔ)上獲得了更為顯著的性能提升.并行MMAS算法在不損失結(jié)果精度的前提下，獲得了最高可達13.53倍的加速比，并且隨著城市規(guī)模的增大加速比呈上升趨勢.

由圖3可知，隨著城市規(guī)模的增大，tsp文件的讀取時間并未明顯增加，而數(shù)據(jù)傳輸與運算時間顯著提升.以pcb442為例[24]，圖4所示的是tsp文件讀取后數(shù)據(jù)在CPU和GPU之間傳遞和運算的時間分布，該分布表明并行MMAS將計算量最大的運算任務如路徑建立階段及信息素更新階段在GPU上執(zhí)行，充分發(fā)揮其多核多線程的計算優(yōu)勢，因而能給算法帶來顯著的性能提升.

圖2 并行MMAS算法加速趨勢Fig.2 Speedup trend of parallel MMAS

圖3 單次運算數(shù)據(jù)讀取時間與運算時間Fig.3 Data access time and computing time in single run

圖4 CPU-GPU平臺運算時間分布Fig.4 Computing time distribution of CPU-GPU platform

4 結(jié)語

提出并行MMAS算法采用CPU作為主機、GPU作為設(shè)備的協(xié)同計算模式，CPU負責控制，GPU執(zhí)行絕大部分的運算任務.在邏輯層面，算法使用并行蟻群策略，在運算量最大的路徑建立階段為每只螞蟻分配CUDA線程.

詳細分析了MMAS算法每個階段的計算量和并發(fā)潛力，分別采用了2個對提高算法運行速度至關(guān)重要的策略：

(1)距離矩陣和信息素矩陣常駐設(shè)備內(nèi)存，有效避免了每輪迭代結(jié)束后2個矩陣在主機內(nèi)存和設(shè)備內(nèi)存之間的傳輸，極大減少了數(shù)據(jù)延遲.

(2)用直接相乘方式代替pow函數(shù)計算狀態(tài)轉(zhuǎn)換規(guī)則，這一改變大大減少了計算量，非常有利于程序在GPU上運行速度的提升.

借鑒CUDA編程模型的數(shù)據(jù)流并行特點，對數(shù)據(jù)傳輸、內(nèi)存層次、庫函數(shù)調(diào)用實施針對性的優(yōu)化，并行MMAS算法比Delévacq等采用的并行螞蟻方案取得顯著的性能提升.該方式使得并行MMAS更加適合GPU的多線程架構(gòu)，提供了細粒度條件下并行算法行之有效的優(yōu)化策略，充分挖掘了單GPU異構(gòu)計算模式的計算潛能.同時建立了在CPU-GPU異構(gòu)平臺上并行ACO算法解決組合優(yōu)化問題的模型，對其他蟻群算法在異構(gòu)平臺的性能提升也有啟發(fā)意義.由于不同蟻群算法的特點主要表現(xiàn)于信息素矩陣的更新過程，因此對于路徑建立階段存在并發(fā)潛力的螞蟻系統(tǒng)如AS(Ant System)，GPU的加速效果是可復制的，僅需要針對不同ACO算法的信息素更新操作來制定相應的并發(fā)策略.而ACS(Ant Colony System)存在信息素矩陣局部更新操作，使不同螞蟻的路徑建立過程存在依賴性，所以很難對此過程進行并發(fā).

[1] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29.

[2] Stützle T, Hoos H H. Max-min ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889.

[3] 王建玲, 齊紫茜, 何璐. 基于蟻群算法的車輛調(diào)度問題[J]. 交通科技與經(jīng)濟, 2014, 16(6):37.

WANG Jianling, QI Ziqian, HE Lu. Research on vehicle scheduling problem based on ant colony algorithm[J]. Technology & Economy in Areas of Communications, 2014, 16(6):37.

[4] 周明秀, 程科, 汪正霞. 動態(tài)路徑規(guī)劃中的改進蟻群算法[J]. 計算機科學, 2013, 40(1): 314.

ZHOU Mingxiu, CHENG Ke, WANG Zhengxia. Improved ant colony algorithm with planning of dynamic path[J]. Computer Science, 2013, 40(1): 314.

[5] 夏亞梅, 程渤, 陳俊亮,等. 基于改進蟻群算法的服務組合優(yōu)化[J]. 計算機學報, 2012, 35(2):270.

XIA Yamei, CHENG Bo, CHEN Junliang,etal. Optimizing services composition based on improved ant colony algorithm[J]. Chinese Journal of Computers, 2012, 35(2):270.

[6] Khatri K, Gupta V K. A survey paper on solving TSP using ant colony optimization on GPU[J]. Compusoft, 2014, 3(12): 1354.

[7] Bullnheimer B, Kotsis G, Strauβ C. Parallelization strategies for the ant system[M]∥ High Performance Algorithms and Software in Nonlinear Optimization.[S.l.]: Springer US, 1998:1-8.

[8] Fu J. Parallel ant colony optimization algorithm with GPU-acceleration based on All-In-Roulette selection[J]. Computer & Digital Engineering, 2011, 84(10):260.

[9] Stützle T. ACOTSP: A software package of various ant colony optimization algorithms applied to the symmetric traveling salesman problem[EB/OL]. [2015-12-01]. http:∥www. aco-metaheuristic.org/aco-code.

[10] Middendorf M, Reischle F, Schmeck H. Multi colony ant algorithms[J]. Journal of Heuristics, 2002, 8(3):305.

[11] 王詔遠, 王宏杰, 邢煥來, 等. 基于Spark的蟻群優(yōu)化算法[J]. 計算機應用, 2015, 35(10): 2777.

WANG Zhaoyuan, WANG Hongjie, XING Huanlai,etal. Ant colony optimization algorithm based on Spark[J]. Computer Application, 2015, 35(10): 2777.

[12] Delévacq A, Delisle P, Gravel M,etal. Parallel ant colony optimization on graphics processing units[J]. Journal of Parallel & Distributed Computing, 2013, 73(1): 52.

[13] Wang Z Y, Tian-Rui L I, Xiu-Wen Y I. Approach for development of ant colony optimization based on mapReduce[J]. Computer Science, 2014, 41(7):261.

[14] Khatri K, Gupta V K. Research on solving travelling salesman problem using rank based ant system on GPU[J]. Compusoft, 2015, 4(5): 1778.

[15] Cecilia J M, García J M, Nisbet A,etal. Enhancing data parallelism for ant colony optimization on gpus[J]. Journal of Parallel & Distributed Computing, 2013, 73(1):42.

[16] 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.

[17] Stutzle T, Hoos H. Max-min ant system and local search for the traveling salesman problem[C]∥Evolutionary Computation. Indianapolis: IEEE, 1997: 309-314.

[18] Dawson L, Stewart I A. Accelerating ant colony optimization-based edge detection on the GPU using CUDA[C]∥ Evolutionary Computation. Beijing: IEEE, 2014:1736-1743.

[19] Garey M R, Johnson D S, Stockmeyer L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science, 1976, 1(3): 237.

[20] Sanders J, Kandrot E. CUDA by example: An introduction to general-purpose GPU programming[M]. [S.l.]:Addison-Wesley Professional, 2011.

[21] Nvidia C. Nvidia Cuda C programming guide[J]. Nvdia Corporation, 2011, 120(18): 8.

[22] Graham S L, Kessler P B, Mckusick M K. Gprof: A call graph execution profiler[J]. ACM Sigplan Notices, 2004，39(4): 49.

[23] Amdahl G M. Validity of the single-processor approach to achieving large scale computing capabilities[C]∥Spring Joint Computer Conference. Atlantic City: ACM, 1967: 483-485.

[24] Reinelt G. TSPLIB—A traveling salesman problem library[J]. ORSA Journal on Computing, 1991, 3(4): 376.

Parallel Max-min Ant System Based on Heterogeneous Platform

HUANGZhenhua1,ZHAOZhenqi1,LINPeiyu1,MEIJianhua2

(1.College of Electronics and Information Engineering, Tongji University, Shanghai 200092, China; 2.Shanghai Xinyu Industrial Development Co.,Ltd., Shanghai 200062, China)

Max-min Ant System is a kind of heuristic algorithm with excellent performance, which is commonly used to solve combinatorial optimization problems. But it costs a long time when scale of the target problem is large as well as iterations are a lot. The experiment took the open source packet ACOTSP as a reference, used the advantage of multi-threaded GPU, and implemented ACO algorithm on CPU-GPU platform by parallel ants strategy. While the parallel algorithm is running on GPU, we also analyzed the impact factors carefully, such as data transmission, memory hierarchy, library calls et al, and made useful optimization. Eventually, the experiment made 13 times speedup, proving the parallel strategy is highly efficient and applicable.

parallel computing; heterogeneous platform; Max-min Ant System; speedup ratio

2015-12-23

國家自然科學基金(61272268)；上海市青年科技啟明星計劃 (15QA1403900)；霍英東教育基金會高等院校青年教師基金(142002)；教育部新世紀優(yōu)秀人才支持計劃(NCET-12-0413)；同濟大學中央高?；究蒲袠I(yè)務費專項資金

黃震華(1981—)，男，副教授，工學博士，主要研究方向為信息推薦、分布式計算、數(shù)據(jù)挖掘. E-mail: huangzhenhua@#edu.cn

趙振岐(1992—)，男，碩士生，主要研究方向為高性能計算、數(shù)據(jù)挖掘.E-mail: zhaozhenqi@#edu.cn

TP301.6

A