曹亞群

摘? 要：該文介紹了GPU概念及發(fā)展、并行計(jì)算的概念以及與串行計(jì)算相比而具有的優(yōu)勢，指出智能優(yōu)化算法具有天然的并行性和分布性，在基礎(chǔ)理論和工程應(yīng)用中具有很高的研究價(jià)值，該文對智能優(yōu)化算法中的模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法及蟻群算法的原理和實(shí)際應(yīng)用進(jìn)行了深入研究，提出了基于GPU的并行優(yōu)化算法。

關(guān)鍵詞：GPU? 并行計(jì)算? 算法

中圖分類號：TP301 ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1672-3791（2019）07（c）-0007-02

Abstract： This paper introduces the concept and development of GPU， the concept of parallel computation and the advantage of the serial calculation， and points out that the intelligent optimization algorithm has the natural parallelism and the distribution， and has very high research value in the basic theory and engineering application. In this paper， the principle and practical application of the simulated annealing algorithm， the genetic algorithm， the tabu search algorithm， the artificial neural network algorithm and the ant colony algorithm in the intelligent optimization algorithm are deeply studied， and a parallel optimization algorithm based on the GPU is proposed.

Key Words： GPU; Parallel Computing; Algorithms

GPU并行計(jì)算是利用圖形處理器，充分利用GPU內(nèi)部結(jié)構(gòu)，提高運(yùn)算效率，目前，人們己經(jīng)提出了很多GPU并行計(jì)算的模型，大家對GPU的并行計(jì)算都有非常大的興趣，該文對GPU并行優(yōu)化算法進(jìn)行了研究。

1? CPU簡介

GPU是Graphic Processing Unit的英文縮寫，中文意思為圖形處理器。GPU計(jì)算就是利用圖形處理器進(jìn)行科學(xué)和工程計(jì)算，最早GPU出現(xiàn)是為了提高3D圖形處理速度，之后，GPU引入了編程和通用計(jì)算，目的是求解數(shù)學(xué)擴(kuò)散方程和矩陣乘法。GPU在并行計(jì)算上的優(yōu)勢非常明顯，矩陣運(yùn)算、生命科學(xué)等方面的應(yīng)用，有大量重復(fù)的數(shù)據(jù)運(yùn)算，所以都需要GPU強(qiáng)大的計(jì)算功能。但是GPU并行運(yùn)算的條件是它要解決的問題能夠分解并行執(zhí)行。所以，GPU要發(fā)展得更好必須有兩個(gè)方面能力：（1）分支能力。GPU只有具有更強(qiáng)的分支能力，復(fù)雜的計(jì)算程序才能進(jìn)行。（2）更大的共用存儲(chǔ)器和緩存空間。共享存儲(chǔ)器是共享數(shù)據(jù)、掛起線程，緩存空間越大，線程跳轉(zhuǎn)就越快，分支能力就越大。

GPU發(fā)展到如今，已經(jīng)突破了很多技術(shù)壁壘，由當(dāng)初圖形處理而誕生的硬件發(fā)展成大規(guī)模并行計(jì)算。智能終端對圖像顯示的要求逐漸提高，GPU的性能也會(huì)隨之更加優(yōu)化。

2? 并行計(jì)算

所謂并行計(jì)算[1]是指在單位時(shí)間內(nèi)，充分利用多個(gè)處理器單元，同時(shí)執(zhí)行多條數(shù)據(jù)及指令的計(jì)算，用傳統(tǒng)的串行計(jì)算處理大規(guī)模數(shù)據(jù)需要很長時(shí)間，于是，人們研究是否有途徑能同時(shí)處理不同的數(shù)據(jù)，并行計(jì)算就隨之出現(xiàn)了，在時(shí)間上，并行是指流水線技術(shù)，在空間上，并行是指多個(gè)處理器同時(shí)進(jìn)行計(jì)算。因?yàn)椴⑿杏?jì)算是用多個(gè)處理器共同完成一個(gè)計(jì)算任務(wù)，能最大程度地縮短完成任務(wù)的時(shí)間，所以與串行算法相比較，并行算法能有效解決大規(guī)模運(yùn)算問題。如圖1所示，所謂并行計(jì)算就是把要解決的問題劃分成一系列子任務(wù)，然后由多個(gè)不同功能的處理核完成各自的計(jì)算任務(wù)，這些處理核在計(jì)算數(shù)據(jù)時(shí)應(yīng)彼此配合，以求達(dá)到獲得最大計(jì)算性能[2]。

3? 智能優(yōu)化算法

智能優(yōu)化算法[3]是仿照自然界智能優(yōu)化原理而設(shè)計(jì)產(chǎn)生的算法，智能優(yōu)化算法具有天然的并行性和分布性，此特性十分適合在并行計(jì)算設(shè)備上實(shí)現(xiàn)并行算法。智能優(yōu)化算法在理論研究上和工程應(yīng)用上都具有很高的價(jià)值，在圖像處理、信號處理、任務(wù)分配、生產(chǎn)調(diào)度、模式識(shí)別、機(jī)械設(shè)計(jì)和自動(dòng)控制等眾多領(lǐng)域得到了成功應(yīng)用。其主要包括模擬退火算法、遺傳算法、禁忌搜索算法和人工神經(jīng)網(wǎng)絡(luò)等。

（1）模擬退火算法。

模擬退火算法是依照固態(tài)物質(zhì)的退火原理而產(chǎn)生的，主要應(yīng)用于解決組合優(yōu)化問題。當(dāng)被加熱的固態(tài)物質(zhì)的溫度到某定值時(shí)，其里面微粒的布朗運(yùn)動(dòng)逐漸加劇，直至到達(dá)一定的運(yùn)動(dòng)強(qiáng)度時(shí)，固態(tài)就變成了液態(tài)，此時(shí)再退火，固態(tài)物質(zhì)內(nèi)的朗運(yùn)動(dòng)會(huì)慢慢變?nèi)?，最終穩(wěn)定下來。

用模擬退火算法不會(huì)出現(xiàn)局部最優(yōu)解，在模擬退火算法中設(shè)定某個(gè)理想概率P，若新解的目標(biāo)函數(shù)的數(shù)值更優(yōu)，就取P=1，也就是選擇更加優(yōu)化的解。否則，讓理想概率P取當(dāng)下解的目標(biāo)函數(shù)、新解的目標(biāo)函數(shù)及參數(shù)T的函數(shù)?？梢钥闯?，在求解最優(yōu)解時(shí)該算法既考慮最優(yōu)的解，同時(shí)還考慮目標(biāo)函數(shù)不理想的解。算法中的參數(shù)T在運(yùn)行該算法時(shí)會(huì)逐漸減小，直到小于某個(gè)數(shù)值時(shí)該算法結(jié)束。

（2）遺傳算法。

遺傳算法是來自于大自然中適者生存、優(yōu)勝劣汰的遺傳變異的生物進(jìn)化而設(shè)計(jì)產(chǎn)生一種算法。該算法是開始于一個(gè)種群，該種群代表要優(yōu)化問題的可能解集，包含標(biāo)有基因編碼的一定數(shù)目的個(gè)體，把基因編碼為染色體，所有個(gè)體都具有染色體的特點(diǎn)，算法過程中引入一些隨機(jī)參數(shù)高效搜索解空間。遺傳算法首先編碼生成初代種群，然后檢查否滿足收斂準(zhǔn)則，若不滿足，則繼續(xù)，若滿足，則結(jié)束算法，接著評價(jià)檢測適應(yīng)性及選出最優(yōu)個(gè)體，最后交叉配種和基因突變產(chǎn)生新的種群。遺傳算法過程類似于自然進(jìn)化過程，產(chǎn)生的后代種群比前代種群有更好的適應(yīng)性，算法結(jié)束后，把末代種群內(nèi)最優(yōu)個(gè)體解碼，就是問題的最優(yōu)解[4]。