基于C++ AMP加速并行蟻群算法

林超

摘? 要： 蟻群算法與同類智能算法相比具有計(jì)算速度快、收斂迅速、算法穩(wěn)定性好等優(yōu)點(diǎn)，但是隨著數(shù)據(jù)量的增大，計(jì)算用時(shí)呈現(xiàn)指數(shù)型增長(zhǎng)。為了更好地解決大數(shù)據(jù)量蟻群算法計(jì)算慢的問(wèn)題，結(jié)合蟻群算法天然的并行性，基于最新的GPU并行化接口C++ AMP實(shí)現(xiàn)了并行蟻群算法，使計(jì)算用時(shí)大幅度減少。經(jīng)試驗(yàn)分析，該算法可以達(dá)到3倍的加速效果。

關(guān)鍵詞： 蟻群算法； 并行蟻群算法； C++ AMP； GPU計(jì)算

中圖分類號(hào)： TN911.7?34； TP18??????????? 文獻(xiàn)標(biāo)識(shí)碼： A??????????????????????? 文章編號(hào)： 1004?373X（2014）23?0069?03

Abstract： Compared with similar intelligent algorithms， ant colony algorithm has the advantages of faster calculation， more rapid convergence and more perfect stability. However， with the increasing amount of data， its computation time emerges the exponential growth. In order to solve the problem that the large amount of data ant colony algorithm is slow， by utilizing the natural parallelism of ant colony algorithm， the parallel ant colony algorithm was achieved on the basis of the latest GPU parallel interface C++AMP， which realized the substantial reduction of computation time. The analysis result indicates that the reduction extent is up to 3 times the acceleration effect.

Keyword： ant colony algorithm； parallel ant colony algorithm； C++ AMP； GPU computation

蟻群算法是由Macro Dorigo等人于1991年提出的一種啟發(fā)式智能算法[1]。蟻群算法的設(shè)計(jì)靈感源于蟻群尋找食物的過(guò)程，一群螞蟻通過(guò)相互協(xié)作就能找到從螞蟻巢穴到食物的最短路徑。其算法核心為路徑上的信息素積累，導(dǎo)致更多的螞蟻選擇這一路徑，最后幾乎所有螞蟻選擇經(jīng)過(guò)該路徑，于是就找出了一條從螞蟻巢穴到食物的最短路徑。蟻群算法有著較高的隱含并行性，并且其在很多經(jīng)典問(wèn)題上有著出色的表現(xiàn)，如旅行商問(wèn)題TSP（Traveling Salesman Problem）[2?5]、車輛調(diào)度問(wèn)題[6?7]、集成電路設(shè)計(jì)[8]以及通信網(wǎng)絡(luò)負(fù)載[9]等問(wèn)題。隨著數(shù)據(jù)量的增大，串行程序的計(jì)算用時(shí)成指數(shù)型增長(zhǎng)，顯然不滿足人們的需要。為了更快求解這類問(wèn)題，基于蟻群算法天然的并行性，把算法并行化是很好的選擇。文獻(xiàn)[10]應(yīng)用云計(jì)算技術(shù)將蟻群算法并行化，提出了基于MapReduce的蟻群算法；文獻(xiàn)[11?13]實(shí)現(xiàn)了基于MPI并行計(jì)算的蟻群聚類算法；文獻(xiàn)[14?15]研究了基于OpenMP技術(shù)的多核架構(gòu)下并行蟻群算法；文獻(xiàn)[16?17]建立了一種基于CUDA的并行蟻群算法。本文基于最新的GPU并行化接口C++ AMP實(shí)現(xiàn)蟻群算法的并行化，并通過(guò)數(shù)值驗(yàn)證加速效果。

1? C++ AMP介紹

GPU計(jì)算由來(lái)已久，已經(jīng)成熟的接口包括NVIDIA的CUDA C和AMD的OPENCL接口，隨著微軟公司Visual Studio 2012的發(fā)布，在Build大會(huì)上微軟向大家呈現(xiàn)了一種新的GPU并行計(jì)算模式C++ AMP，其最低運(yùn)行環(huán)境是：Win7系統(tǒng)+Visual Studio 2012+DirectX11，所以它比另外兩種并行端口適用范圍更廣，可以實(shí)現(xiàn)真正意義上的跨平臺(tái)運(yùn)行。C++ AMP采用面向?qū)ο蟮腃++語(yǔ)言開(kāi)發(fā)，支持CPU，GPU等跨平臺(tái)編譯運(yùn)行，具有邏輯結(jié)構(gòu)簡(jiǎn)單、數(shù)據(jù)隱式拷貝、自動(dòng)負(fù)載均衡等特點(diǎn)，可以快速、穩(wěn)定地實(shí)現(xiàn)并行計(jì)算。

一個(gè)C++ AMP計(jì)算過(guò)程中最重要的包括：

（1）數(shù)據(jù)，其基本數(shù)據(jù)類型有array<；T，N>；，array_view<；T，N>；，index<；N>；，extent<；N>；，tiled_extent<；D0，D1，D2>；，title_index（D0，D1，D2>；，accelerator，accelerator_view，texture<；T，N>；等；

（2） 迭代函數(shù)parallel_for_each函數(shù)，是C++AMP并行計(jì)算的核心部分，負(fù)責(zé)線程開(kāi)辟、核函數(shù)計(jì)算等工作，基本的計(jì)算過(guò)程由核函數(shù)指定，通常核函數(shù)為L(zhǎng)ambda表達(dá)式，也可以是由限定符restrict（amp）限定的GPU函數(shù)；

（3） 線程索引index類，線程開(kāi)辟大小extent類，他們兩者是一一對(duì)應(yīng)的。如果extent是二維的，則index也是二維的，由index類對(duì)象來(lái)實(shí)現(xiàn)對(duì)線程的惟一標(biāo)示；

（4） 數(shù)學(xué)函數(shù)，數(shù)學(xué)函數(shù)庫(kù)有雙精度數(shù)學(xué)函數(shù)與快速數(shù)學(xué)函數(shù)兩種，根據(jù)需要選擇。

C++ AMP的執(zhí)行模式是由CPU線程控制、由parallel_for_each函數(shù)作為詳細(xì)設(shè)置、由核函數(shù)完成核心計(jì)算任務(wù)、數(shù)據(jù)隱式拷貝的執(zhí)行模型。程序開(kāi)始運(yùn)行時(shí)，只有CPU主線程活動(dòng)，當(dāng)執(zhí)行到并行區(qū)域時(shí)，主線程根據(jù)parallel_for_each函數(shù)的設(shè)置，啟動(dòng)GPU線程組來(lái)完成相應(yīng)的計(jì)算任務(wù)，最后拷貝數(shù)據(jù)回CPU主線程，這時(shí)GPU線程掛起或者退出，控制流又回到CPU主線程中。

2? 蟻群算法介紹

為了更加清楚詳細(xì)地描述蟻群算法，本文借助經(jīng)典的TSP問(wèn)題來(lái)描述（TSP問(wèn)題：已知[n]個(gè)城市以及城市兩兩之間的距離，求一條遍歷所有城市的最短路徑，除初始城市之外每個(gè)城市訪問(wèn)且僅訪問(wèn)一次）。

蟻群算法可以定義如下：設(shè)有[n]個(gè)城市，[m]個(gè)螞蟻，任意城市[i]與城市[j]之間的距離為[d（i，j）]，啟發(fā)函數(shù)定義為[η（i，j）=1d（i，j），]任意城市[i]與城市[j]之間的信息素濃度為[τ（i，j）]，并且初始時(shí)刻信息素濃度相同，螞蟻[k]經(jīng)過(guò)城市[i]轉(zhuǎn)到城市[j]的概率計(jì)算公式如下所示：

[pkij=[τ（i，j）]α?[η（i，j）]βs∈J（k）[τ（i，s）]α?[η（i，s）]β，s∈J（k）0，others] （1）

式中：[J（k）]是螞蟻[k]下一步允許選擇的城市的集合；[α，][β]為權(quán)重系數(shù)。當(dāng)所有螞蟻都完成一次循環(huán)后，對(duì)信息素矩陣進(jìn)行更新操作，這樣，新時(shí)刻路徑[（i，j）]上的信息素濃度采用調(diào)整式（2）進(jìn)行調(diào)節(jié)：

[τ（i，j）=ρτ（i，j）+k=1mΔτk（i，j）] （2）

式中：[ρ（0<；ρ<；1）]表示信息素保留程度，其值越大表示信息素?fù)]發(fā)速率越慢；[Δτk（i，j）]表示在本次循環(huán)中第[k]只螞蟻在路徑[（i，j）]上的信息素貢獻(xiàn)。每只螞蟻的信息素貢獻(xiàn)可以用式（3）進(jìn)行計(jì)算：

[Δτk（i，j）=QLk，第k只螞蟻在本次循環(huán)中經(jīng)過(guò)（i，j）0，否則] （3）

式中：[Q]是信息素強(qiáng)度，它影響算法的收斂速度；[Lk]表示第[k]只螞蟻在本次循環(huán)中所有的路徑總和[4]。

3? 并行蟻群算法

根據(jù)上述介紹，可以看出每只螞蟻尋找自己路徑依賴于上次循環(huán)產(chǎn)生的信息素矩陣以及各城市之間的靜態(tài)路徑長(zhǎng)度，兩兩螞蟻之間沒(méi)有信息素交流，經(jīng)過(guò)分析，這是一種符合SIMD模型的過(guò)程，故可以將每只螞蟻尋找最優(yōu)路徑的過(guò)程并行進(jìn)行，從而加速算法計(jì)算。并行蟻群算法可以用如下算法進(jìn)行描述：

Step1：初始化所有參數(shù)、變量，如權(quán)重系數(shù)[α，][β；]螞蟻個(gè)數(shù)[m；]最大迭代步數(shù)NC；信息素矩陣初始值[τ（i，j）=1。]

Step2：按照螞蟻個(gè)數(shù)分配線程，每個(gè)線程代表一只螞蟻。每只螞蟻獨(dú)立構(gòu)造一個(gè)解（解即一條遍歷所有城市的路徑），詳細(xì)描述為：螞蟻[k]隨機(jī)選取一個(gè)城市[i]作為自己的初始點(diǎn)，再根據(jù)轉(zhuǎn)移概率公式計(jì)算轉(zhuǎn)移概率[pkij；]根據(jù)概率最大者選擇下一個(gè)城市[j]，從而螞蟻?zhàn)哌^(guò)路徑為[（i，j）。]若當(dāng)前路徑長(zhǎng)度大于上一循環(huán)求得最短路徑長(zhǎng)度，則結(jié)束本次循環(huán)；否則繼續(xù)循環(huán)，直到螞蟻[k]尋找到一個(gè)解。

Step3：規(guī)約Step2中所有螞蟻產(chǎn)生的解，求解出所有解中的最優(yōu)解和最優(yōu)值進(jìn)行保存操作。

Step4：根據(jù)當(dāng)前最優(yōu)解和最優(yōu)值信息，進(jìn)行信息素矩陣更新操作。

Step5：判斷是否滿足結(jié)束條件，若滿足，則輸出最優(yōu)解和最優(yōu)值；否則，循環(huán)執(zhí)行次數(shù)+1，轉(zhuǎn)Step2。結(jié)束條件為循環(huán)次數(shù)大于NC或者當(dāng)前解已經(jīng)穩(wěn)定（通常兩步解出的最優(yōu)解與最優(yōu)值相同即可認(rèn)為當(dāng)前解已經(jīng)穩(wěn)定）。

串行蟻群算法的時(shí)間復(fù)雜度為[O（NC?m?n2）]，計(jì)算量主要集中在螞蟻各自構(gòu)造一個(gè)解的過(guò)程。蟻群算法在一代迭代中包括螞蟻獨(dú)立求解、相互交流得到較優(yōu)解和改變信息素的過(guò)程，且信息素的改變直接影響下一代概率計(jì)算的結(jié)果，從而產(chǎn)生不同的解，并向較優(yōu)解進(jìn)化。由于把算法并行化，采用每只螞蟻并行尋找路徑的模式進(jìn)行，則并行蟻群算法的時(shí)間復(fù)雜度減小為[O（NC?n2）]，使算法有明顯的加速。

4? 數(shù)值實(shí)驗(yàn)

4.1? 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境采用NVIDIA GeForce GT 440環(huán)境，具體參數(shù)配置如表1所示。

4.2? 數(shù)值結(jié)果

數(shù)值實(shí)驗(yàn)采用的數(shù)據(jù)為隨機(jī)生成的二維坐標(biāo)，取值范圍在[0，1 000]，分城市數(shù)目[n、]螞蟻數(shù)目[m、]迭代次數(shù)[NC]等三個(gè)參數(shù)進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如表2所示。

由表2前三行可知，串行時(shí)間與并行時(shí)間隨著迭代次數(shù)的增加呈現(xiàn)線性增長(zhǎng)趨勢(shì)，這也符合第3節(jié)的理論推導(dǎo)，此時(shí)串行時(shí)間與并行時(shí)間相當(dāng)，加速比在[1-0.01，1+0.01]范圍之內(nèi)，可以認(rèn)為此時(shí)沒(méi)有加速效果。由此三行知道，加速比和運(yùn)行時(shí)間都與迭代次數(shù)無(wú)關(guān)。下面選取小的迭代次數(shù)來(lái)進(jìn)行數(shù)值實(shí)驗(yàn)，分析城市數(shù)目與螞蟻數(shù)目對(duì)串行時(shí)間、并行時(shí)間、加速比的影響。

表1 實(shí)驗(yàn)環(huán)境GeForce GT 440配置參數(shù)

[項(xiàng)目＼&；參數(shù)＼&；操作系統(tǒng)＼&；Windows 7， 64-bits＼&；內(nèi)存＼&；4 GB＼&；運(yùn)行環(huán)境＼&；Visual Studio 2012＼&；CPU＼&；Intel（R） Xeon（R） W3520@ 2.67 GHz x 4＼&；GPU＼&；顯卡型號(hào)：NVIDIA GeForce GT 440

顯存：512 MB DDR3

帶寬：54.4 GB/s

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲(chǔ)頻率：850 MHz

渲染頻率：1 700 MHz

SM個(gè)數(shù)：2個(gè)

SP個(gè)數(shù)：96個(gè)＼&；]

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

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時(shí)間

?；/s＼&；并行時(shí)間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當(dāng)城市數(shù)目及螞蟻數(shù)目較大時(shí)，對(duì)數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時(shí)間呈現(xiàn)線性增長(zhǎng)，而并行時(shí)間的增長(zhǎng)率小于線性，加速比越來(lái)越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時(shí)間增長(zhǎng)率比線性還小。但是此時(shí)并行時(shí)間并沒(méi)有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開(kāi)辟了[m]個(gè)，但是最終的物理執(zhí)行過(guò)程同時(shí)運(yùn)行的線程個(gè)數(shù)為96個(gè)（SP個(gè)數(shù)），又涉及到CPU?GPU異構(gòu)通信時(shí)間，從而使得整體并行時(shí)間沒(méi)有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負(fù)載相對(duì)越均衡，物理資源占用越充分，從而加速效果越來(lái)越明顯，直到達(dá)到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對(duì)比出，螞蟻數(shù)目[m]一定時(shí)，城市數(shù)目[n]對(duì)于串行、并行算法時(shí)間的影響。對(duì)比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對(duì)比6，8兩行可以看出，螞蟻數(shù)目一樣時(shí)，城市數(shù)目的改變對(duì)于整個(gè)算法的加速比影響并不是很大。這個(gè)也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時(shí)間以及算法本身所用時(shí)間方面進(jìn)行分析，這個(gè)加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計(jì)實(shí)現(xiàn)了并行蟻群算法，經(jīng)過(guò)數(shù)值實(shí)驗(yàn)分析，可以達(dá)到3倍的加速效果，對(duì)于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導(dǎo)致。

參考文獻(xiàn)

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進(jìn)的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學(xué)軍.基于蟻群算法的艦艇編隊(duì)海上補(bǔ)給路徑規(guī)劃方法[J].海軍工程大學(xué)學(xué)報(bào)，2014（2）：108?112.

[4] 郭平，鄢文晉.基于TSP問(wèn)題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007（10）：181?184.

[5] 王勝訓(xùn)，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學(xué)學(xué)報(bào)，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場(chǎng)多任務(wù)多車型車輛調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學(xué)學(xué)報(bào)，2007（2）：211?214.

[8] 黃訓(xùn)誠(chéng)，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無(wú)網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛(ài)靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會(huì)穎.基于MapReduce的蟻群算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計(jì)與實(shí)現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實(shí)現(xiàn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問(wèn)題的并行蟻群算法[J].微電子學(xué)與計(jì)算機(jī)，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽(yáng)丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細(xì)粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲(chǔ)頻率：850 MHz

渲染頻率：1 700 MHz

SM個(gè)數(shù)：2個(gè)

SP個(gè)數(shù)：96個(gè)＼&；]

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

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時(shí)間

?；/s＼&；并行時(shí)間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當(dāng)城市數(shù)目及螞蟻數(shù)目較大時(shí)，對(duì)數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時(shí)間呈現(xiàn)線性增長(zhǎng)，而并行時(shí)間的增長(zhǎng)率小于線性，加速比越來(lái)越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時(shí)間增長(zhǎng)率比線性還小。但是此時(shí)并行時(shí)間并沒(méi)有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開(kāi)辟了[m]個(gè)，但是最終的物理執(zhí)行過(guò)程同時(shí)運(yùn)行的線程個(gè)數(shù)為96個(gè)（SP個(gè)數(shù)），又涉及到CPU?GPU異構(gòu)通信時(shí)間，從而使得整體并行時(shí)間沒(méi)有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負(fù)載相對(duì)越均衡，物理資源占用越充分，從而加速效果越來(lái)越明顯，直到達(dá)到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對(duì)比出，螞蟻數(shù)目[m]一定時(shí)，城市數(shù)目[n]對(duì)于串行、并行算法時(shí)間的影響。對(duì)比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對(duì)比6，8兩行可以看出，螞蟻數(shù)目一樣時(shí)，城市數(shù)目的改變對(duì)于整個(gè)算法的加速比影響并不是很大。這個(gè)也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時(shí)間以及算法本身所用時(shí)間方面進(jìn)行分析，這個(gè)加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計(jì)實(shí)現(xiàn)了并行蟻群算法，經(jīng)過(guò)數(shù)值實(shí)驗(yàn)分析，可以達(dá)到3倍的加速效果，對(duì)于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導(dǎo)致。

參考文獻(xiàn)

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進(jìn)的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學(xué)軍.基于蟻群算法的艦艇編隊(duì)海上補(bǔ)給路徑規(guī)劃方法[J].海軍工程大學(xué)學(xué)報(bào)，2014（2）：108?112.

[4] 郭平，鄢文晉.基于TSP問(wèn)題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007（10）：181?184.

[5] 王勝訓(xùn)，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學(xué)學(xué)報(bào)，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場(chǎng)多任務(wù)多車型車輛調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學(xué)學(xué)報(bào)，2007（2）：211?214.

[8] 黃訓(xùn)誠(chéng)，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無(wú)網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛(ài)靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會(huì)穎.基于MapReduce的蟻群算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計(jì)與實(shí)現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實(shí)現(xiàn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問(wèn)題的并行蟻群算法[J].微電子學(xué)與計(jì)算機(jī)，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽(yáng)丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細(xì)粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲(chǔ)頻率：850 MHz

渲染頻率：1 700 MHz

SM個(gè)數(shù)：2個(gè)

SP個(gè)數(shù)：96個(gè)＼&；]

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

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時(shí)間

?；/s＼&；并行時(shí)間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當(dāng)城市數(shù)目及螞蟻數(shù)目較大時(shí)，對(duì)數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時(shí)間呈現(xiàn)線性增長(zhǎng)，而并行時(shí)間的增長(zhǎng)率小于線性，加速比越來(lái)越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時(shí)間增長(zhǎng)率比線性還小。但是此時(shí)并行時(shí)間并沒(méi)有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開(kāi)辟了[m]個(gè)，但是最終的物理執(zhí)行過(guò)程同時(shí)運(yùn)行的線程個(gè)數(shù)為96個(gè)（SP個(gè)數(shù)），又涉及到CPU?GPU異構(gòu)通信時(shí)間，從而使得整體并行時(shí)間沒(méi)有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負(fù)載相對(duì)越均衡，物理資源占用越充分，從而加速效果越來(lái)越明顯，直到達(dá)到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對(duì)比出，螞蟻數(shù)目[m]一定時(shí)，城市數(shù)目[n]對(duì)于串行、并行算法時(shí)間的影響。對(duì)比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對(duì)比6，8兩行可以看出，螞蟻數(shù)目一樣時(shí)，城市數(shù)目的改變對(duì)于整個(gè)算法的加速比影響并不是很大。這個(gè)也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時(shí)間以及算法本身所用時(shí)間方面進(jìn)行分析，這個(gè)加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計(jì)實(shí)現(xiàn)了并行蟻群算法，經(jīng)過(guò)數(shù)值實(shí)驗(yàn)分析，可以達(dá)到3倍的加速效果，對(duì)于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導(dǎo)致。

參考文獻(xiàn)

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進(jìn)的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學(xué)軍.基于蟻群算法的艦艇編隊(duì)海上補(bǔ)給路徑規(guī)劃方法[J].海軍工程大學(xué)學(xué)報(bào)，2014（2）：108?112.

[4] 郭平，鄢文晉.基于TSP問(wèn)題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007（10）：181?184.

[5] 王勝訓(xùn)，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學(xué)學(xué)報(bào)，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場(chǎng)多任務(wù)多車型車輛調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學(xué)學(xué)報(bào)，2007（2）：211?214.

[8] 黃訓(xùn)誠(chéng)，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無(wú)網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛(ài)靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負(fù)載均衡問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會(huì)穎.基于MapReduce的蟻群算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計(jì)與實(shí)現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實(shí)現(xiàn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問(wèn)題的并行蟻群算法[J].微電子學(xué)與計(jì)算機(jī)，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽(yáng)丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細(xì)粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.