基于GPU的并行優(yōu)化算法研究

曹亞群

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

關鍵詞：GPU? 并行計算? 算法

中圖分類號：TP301 ? ?文獻標識碼：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并行計算是利用圖形處理器，充分利用GPU內部結構，提高運算效率，目前，人們己經(jīng)提出了很多GPU并行計算的模型，大家對GPU的并行計算都有非常大的興趣，該文對GPU并行優(yōu)化算法進行了研究。

1? CPU簡介

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

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

2? 并行計算

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

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

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

（1）模擬退火算法。

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

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

（2）遺傳算法。

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