陳 風(fēng),田雨波,楊 敏
(江蘇科技大學(xué) 電子信息學(xué)院,江蘇 鎮(zhèn)江212003)
人工神經(jīng)網(wǎng)絡(luò) (artificial neural networks,ANN),簡稱神經(jīng)網(wǎng)絡(luò) (neural networks,NN),正在各個(gè)領(lǐng)域得到越來越廣泛的應(yīng)用。粒子群優(yōu)化 (particle swarm optimization,PSO)作為一種容易實(shí)現(xiàn)、收斂速度快的全局優(yōu)化算法[1],正在逐漸代替常用的誤差反向傳播 (back propagation,BP)算法應(yīng)用到NN 的訓(xùn)練中[2]。面對(duì)計(jì)算復(fù)雜度較高的問題時(shí),運(yùn)算時(shí)間長是粒子群神經(jīng)網(wǎng)絡(luò) (PSO-NN)的一大問題,并行化加速是解決該問題的有效思路。
除了NN 存儲(chǔ)結(jié)構(gòu)和樣本訓(xùn)練的并行性[3-5],PSO-NN還存在PSO 算法天然具備的群體中個(gè)體行為的并行性。相比用計(jì) 算 機(jī) 群[6,7]、多 核CPU[8]或FPGA 等 專 業(yè) 并 行 設(shè)備[9]加速PSO 算 法,利 用 圖 形 處 理 器 (graphic processing unit,GPU)并行加速PSO 算法[10-13]具備硬件成本低的最顯著優(yōu)勢。特別是2007年NVIDA 公司推出了統(tǒng)一計(jì)算設(shè)備架構(gòu) (compute unified device architecture,CUDA),不需要借助復(fù)雜的圖形學(xué)知識(shí),良好的可編程性使其迅速成為當(dāng)前最為流行的GPU 編程語言。
本文在GPU-PSO 的研究基礎(chǔ)上,設(shè)計(jì)并實(shí)現(xiàn)了一種基于CUDA 的并行PSO-NN 求解方法,并對(duì)一簡單測試函數(shù)逼近進(jìn)行了實(shí)驗(yàn)測試。本文創(chuàng)新之處在于,從GPU-PSO解決的問題看,將GPU-PSO 用來加速訓(xùn)練NN;從PSONN 的實(shí)現(xiàn)方式上,用GPU 并行加速訓(xùn)練PSO-NN。實(shí)驗(yàn)結(jié)果表明,該方法能加速NN 的訓(xùn)練,減少NN 的訓(xùn)練時(shí)間,相對(duì)于基于CPU 的串行PSO-NN,基于GPU 的并行PSO-NN 在保證訓(xùn)練誤差的前提下取得了超過500 倍的計(jì)算加速比。
PSO 算法是Kennedy和Eberhart于1995 年提出的一種基于群體智能的優(yōu)化算法,其簡單易實(shí)現(xiàn),具備較強(qiáng)的全局搜索和收斂能力,用于優(yōu)化NN 權(quán)閾值能比BP-NN 獲得更好的收斂精度和更強(qiáng)的預(yù)測能力[2]。PSO-NN 的核心思想在于粒子與NN 之間的4 個(gè)對(duì)應(yīng):粒子維數(shù)對(duì)應(yīng)NN權(quán)閾值的數(shù)目,粒子位置對(duì)應(yīng)NN 的權(quán)閾值,粒子速度對(duì)應(yīng)NN 權(quán)閾值的變化,粒子適應(yīng)度值對(duì)應(yīng)NN 的輸出誤差。
本文使用的PSO 算法版本為帶慣性權(quán)重、全局拓?fù)浣Y(jié)構(gòu)的PSO 算法。粒子群由N 個(gè)粒子組成,每個(gè)粒子的位置代表優(yōu)化問題在D 維搜索空間 (D 為NN 權(quán)閾值的數(shù)目)中的一個(gè)潛在的解。PSO-NN 中,采用粒子各維與NN 各權(quán)閾值一一對(duì)應(yīng)的原則,將每個(gè)粒子被編碼成一個(gè)向量,比如將圖1 (圖中已將權(quán)值和閾值合并表示為權(quán)閾值)所示的一個(gè)輸入層2 節(jié)點(diǎn)、隱層3 節(jié)點(diǎn)、輸出層1 節(jié)點(diǎn)的NN編碼成一個(gè)13維的粒子
式中:i——粒子數(shù),i=1,2,...,N。特別要指出的是,這里未采用矩陣編碼策略,而采用向量編碼策略,主要是考慮到1.3節(jié)中方便將粒子位置、速度等信息存儲(chǔ)在線性的GPU 全局內(nèi)存中。
算法的速度更新和位置更新公式如下
其中,i=1,2,...,N,d=1,2,...,D;c1和c2是學(xué)習(xí)因子,非負(fù)的常數(shù);r1和r2是介于 [0,1]的均勻分布的隨機(jī)數(shù);Vid(t)∈ [-Vmax,Vmax],Vmax限制了粒子飛行的最大速度,Xid(t)∈ [-Xmax,Xmax],Xmax限定了粒子搜索空間的范圍,可設(shè)定Vmax=kXmax,0≤k≤1;w 是慣性權(quán)重,介于 [0,1],用來平衡粒子的全局探索能力和局部開發(fā)能力。
標(biāo)準(zhǔn)PSO-NN 算法的流程如下:
(1)讀入訓(xùn)練樣本和測試樣本,數(shù)據(jù)預(yù)處理,設(shè)定最大迭代次數(shù)Tmax。
圖1 2-3-1結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)模型
(2)隨機(jī)初始化每個(gè)粒子的位置Vid(t)和速度Xid(t)。
(3)初始化個(gè)體最優(yōu)位置Pbestid(t)和全局最優(yōu)位置Gbestd(t)。
(4)更新每個(gè)粒子的速度Vid(t)和位置Xid(t)。
(5)計(jì)算每個(gè)粒子對(duì)應(yīng)的適應(yīng)度值 (即NN 的輸出誤差)F(Xi)。
(6)更新個(gè)體最優(yōu)位置Pbestid(t)和全局最優(yōu)位置Gbestd(t)。
(7)若達(dá)到最大迭代次數(shù)Tmax,則執(zhí)行步驟 (8),否則返回步驟 (4)。
(8)將訓(xùn)練樣本和測試樣本帶入訓(xùn)練好的NN,得到網(wǎng)絡(luò)輸出。
CUDA 采用CPU 和GPU 異構(gòu)協(xié)作的編程模式,CPU負(fù)責(zé)串行計(jì)算任務(wù)和控制GPU 計(jì)算,GPU 以單指令多線程 (single instruction multiple threads,SIMT)執(zhí)行方式負(fù)責(zé)并行計(jì)算任務(wù)。內(nèi)核函數(shù) (kernel)執(zhí)行GPU 上的并行計(jì)算任務(wù),是整個(gè)程序中的一個(gè)可以被并行執(zhí)行的步驟。CUDA 將線程組織成塊網(wǎng)格 (grid)、線程塊 (block)、線程 (thread)這3個(gè)不同的層次,并采用多層次的存儲(chǔ)器結(jié)構(gòu):只對(duì)單個(gè)線程可見的本地存儲(chǔ)器,對(duì)塊內(nèi)線程可見的共享存儲(chǔ)器,對(duì)所有線程可見的全局存儲(chǔ)器等。kernel函數(shù)中,Grid內(nèi)的Block之間不可通信,能以任意順序串行或并行地獨(dú)立執(zhí)行;Block內(nèi)的Thread之間可以通信,能通過存儲(chǔ)共享和柵欄同步有效協(xié)作執(zhí)行。CUDA 程序流程通常包括以下6個(gè)步驟:①分配CPU 內(nèi)存并初始化;②分配GPU 內(nèi)存;③CPU 到GPU 數(shù)據(jù)傳遞;④GPU 并行計(jì)算;⑤計(jì)算結(jié)果從GPU 傳回CPU;⑥處理傳回到CPU的數(shù)據(jù)。
常見的NN 神經(jīng)元節(jié)點(diǎn)和訓(xùn)練樣本數(shù)目往往只有十幾或幾十個(gè),利用NN 存儲(chǔ)結(jié)構(gòu)或樣本訓(xùn)練的并行性比較適合計(jì)算機(jī)集群等并行計(jì)算方式[3-5],對(duì)于GPU 來說其算法并行程度還是不夠,因?yàn)镚PU 線程數(shù)為十幾或幾十時(shí)難以充分發(fā)揮其強(qiáng)大的并行計(jì)算能力。對(duì)于較復(fù)雜的問題,PSO-NN 中的粒子數(shù)往往可以達(dá)到上百個(gè)乃至更多,利用群體中粒子行為的并行性可以比較充分發(fā)揮GPU 的并行計(jì)算能力。
2009年,Veronese和Krohling 首次應(yīng)用CUDA 實(shí)現(xiàn)了 對(duì)PSO 算 法 的 加 速[10],掀 起 了GPU 加 速PSO 算 法 的 研究熱潮,近幾年GPU-PSO 的研究趨勢集中在以下2 個(gè)方面:①有GPU 架構(gòu)特色的各種PSO 算法變種;②GPUPSO 解決實(shí)際問題。國內(nèi)文獻(xiàn)對(duì)GPU 加速PSO 算法的研究相對(duì)較少。張慶科等在文獻(xiàn) [12]中概述了CUDA 架構(gòu)下包括PSO 算法在內(nèi)的5種典型現(xiàn)代優(yōu)化算法的并行實(shí)現(xiàn)過程,在并行PSO 算法部分給出了文獻(xiàn) [14]中的實(shí)驗(yàn)結(jié)果。蔡勇等近期在文獻(xiàn) [13]中給出了并行PSO 算法較詳細(xì)的設(shè)計(jì)過程和優(yōu)化思路,取得了90倍的加速比。
本文所述的基于CUDA 的并行PSO-NN 算法屬于上文所述GPU-PSO 研究趨勢的第2個(gè)方面,解決的實(shí)際問題是NN 的加速訓(xùn)練。PSO-NN 算法非常適合CUDA 架構(gòu)的原因有2點(diǎn):一是可并行部分 (NN 的訓(xùn)練)的執(zhí)行時(shí)間占整個(gè)程序執(zhí)行時(shí)間的絕大部分;二是CPU 和GPU 之間無需頻繁通信,數(shù)據(jù)傳輸?shù)臅r(shí)間開銷只占整個(gè)程序執(zhí)行時(shí)間的極小部分。
為簡單起見,本文使用前述標(biāo)準(zhǔn)PSO-NN 算法,采用粒子與線程一一對(duì)應(yīng)的并行策略,利用PSO算法固有的三大并行性:速度更新和位置更新的并行性,計(jì)算粒子適應(yīng)度的并行性,更新Pbest適應(yīng)度值和位置的并行性,以及CUDA 架構(gòu)特有的并行性:更新Gbest時(shí)的并行規(guī)約 (reduction)算法,將GPU-PSO-NN的算法流程設(shè)計(jì)如圖2所示。
圖2 基于CUDA 架構(gòu)的并行PSO-NN 算法流程
GPU-PSO-NN 算法的步驟如下:
(1)CPU 端讀入訓(xùn)練樣本和測試樣本,數(shù)據(jù)預(yù)處理。
(2)CPU 端調(diào)用malloc ()函數(shù)和cudaMalloc ()函數(shù),分別在CPU 端和GPU 端分配變量空間。
(3)CPU 端初始化粒子的位置、速度等信息。
(4)CPU 端調(diào)用cudaMemcpy ()函數(shù),將CPU 端粒子信息傳至GPU 全局內(nèi)存;CPU 端調(diào)用cudaMemcpyTo-Symbol()函數(shù),將CPU 端訓(xùn)練樣本傳至GPU 常量內(nèi)存。
(5)CPU 端調(diào)用kernel函數(shù),執(zhí)行GPU 上的并行計(jì)算任務(wù),完成NN 的訓(xùn)練。
(6)CPU 端調(diào)用cudaMemcpy ()函數(shù),將GPU 端有用信息傳回至CPU 端。
(7)CPU 端將訓(xùn)練樣本和測試樣本帶入訓(xùn)練好的NN,查看結(jié)果。
(8)CPU 端 調(diào) 用free ()函 數(shù) 和cudaFree ()函 數(shù),釋放CPU 端和GPU 端已分配的變量空間。
以上步驟中,完成加速訓(xùn)練NN 的步驟 (5)是GPUPSO-NN 算法的核心,其偽代碼如下:
以上偽代碼中的kernel 4 需要找出適應(yīng)度值最小的粒子編號(hào),這對(duì)單線程算法來說非常簡單的任務(wù),在大規(guī)模并行架構(gòu)上實(shí)現(xiàn)時(shí)卻會(huì)變成一個(gè)復(fù)雜的問題。當(dāng)粒子數(shù)大于塊內(nèi)最大線程數(shù)1024 (計(jì)算能力2.0 及以上)或512(計(jì)算能力2.0 以下)時(shí),在CUDA 架構(gòu)上需用2 次并行Reduction實(shí)現(xiàn),程序具體實(shí)現(xiàn)時(shí)分為2個(gè)kernel。第1個(gè)kernel啟動(dòng)等于粒子數(shù)的線程數(shù),找到各個(gè)線程塊中的最小值;第2個(gè)kernel啟動(dòng)等于第1個(gè)kernel中線程塊數(shù)的線程數(shù),找到這些最小值的最小值,即當(dāng)前全局最優(yōu)值。當(dāng)前全局最優(yōu)值再與舊的全局最優(yōu)值對(duì)比,決定是否需要更新。不能只使用1個(gè)kernel的原因在于:CUDA 架構(gòu)能通過調(diào)用__syncthreads()使線程塊內(nèi)的線程同步,但不能使所有線程同步,所有線程的同步只能通過kernel的結(jié)束來保證。當(dāng)粒子數(shù)小于等于塊內(nèi)最大線程數(shù)1024 或512時(shí),在kernel函數(shù)中啟動(dòng)等于粒子數(shù)的線程數(shù)做1次并行Reduction即可。
一個(gè)線程束 (Warp)包含索引相鄰的32個(gè)線程,流多處理器 (stream multiprocessor,SM)以Warp為單位調(diào)度和執(zhí)行線程,因此將粒子數(shù)目和線程塊大小都設(shè)計(jì)成32的倍數(shù)值。具體實(shí)現(xiàn)時(shí),每個(gè)線程塊中的線程數(shù)目在kernel 1、kernel 2、kernel 3中盡量取128、192、256這樣的典型值,在kernel 4中為了充分利用共享內(nèi)存第1個(gè)Reduction時(shí)盡量取大 (計(jì)算能力2.0 及以上的塊內(nèi)最大線程數(shù)為1024,計(jì)算能力2.0以下的塊內(nèi)最大線程數(shù)為512),第2個(gè)Reduction時(shí)取第一個(gè)Reduction的線程塊數(shù)。
SIMT 執(zhí) 行 模 式 會(huì) 導(dǎo) 致 線 程 分 支 (thread divergence)特別耗時(shí),應(yīng)盡量減少Warp內(nèi)的分支數(shù)目。以kernel 4中的并行規(guī)約為例 (實(shí)驗(yàn)中至少有32個(gè)線程,這里簡單起見只列出8個(gè)線程),圖3的方案具有明顯的線程分支,在第一次求min中,只有那些索引為偶數(shù)的線程才執(zhí)行求min,相鄰線程行為不同。圖4的方案分支就較少,表現(xiàn)在相鄰線程行為相同,都求min或者都不求min。
圖3 大量線程分支的并行規(guī)約求極值方案
圖4 最小化線程分支的并行規(guī)約求極值方案
粒子位置、速度等信息在CPU 內(nèi)存中以二維形式存儲(chǔ),如圖5所示 (圖中d=D-1,n=N-1),而GPU 全局內(nèi)存是一維形式,將粒子位置、速度等信息在GPU 全局內(nèi)存中布局涉及到合并訪問 (coalesced access)的問題。簡單地說,相鄰的線程訪問相鄰的數(shù)據(jù),即可滿足合并訪問的要求。合并訪問能使傳輸數(shù)據(jù)時(shí)的速度接近全局存儲(chǔ)器帶寬的峰值。粒子位置信息在GPU 全局內(nèi)存中按粒子順序存儲(chǔ) (文獻(xiàn) [13,15]等就是采用的這種方式),如圖6所示,雖然簡單直觀但不符合合并訪問的要求,會(huì)造成訪存效率大幅下降。這里采用文獻(xiàn) [16]所述的存儲(chǔ)布局方法,如圖7所示,訪存時(shí)同時(shí)訪問各個(gè)粒子的同一維,滿足合并訪問的條件,提高了訪存效率。粒子速度信息的存儲(chǔ)布局與粒子位置信息類似。
圖5 粒子位置信息在CPU 內(nèi)存中的存儲(chǔ)
圖6 粒子位置信息在GPU 全局內(nèi)存中的存儲(chǔ)(沒有合并訪問)
圖7 粒子位置信息在GPU 全局內(nèi)存中的存儲(chǔ) (合并訪問)
每個(gè)SM 提供最多48KB 的共享存儲(chǔ)器,比全局存儲(chǔ)器的訪問速度快得多,但只對(duì)塊內(nèi)線程可見。應(yīng)盡量使用共享存儲(chǔ)器來保存全局存儲(chǔ)器中在kernel函數(shù)的執(zhí)行階段需要頻繁使用的那部分?jǐn)?shù)據(jù)。以kernel 4中的并行Reduction為例,每次規(guī)約時(shí)將先將全局內(nèi)存中的數(shù)據(jù)保存至共享內(nèi)存,規(guī)約時(shí)反復(fù)使用共享內(nèi)存上的數(shù)據(jù),規(guī)約完成后再將共享內(nèi)存上的結(jié)果保存至全局內(nèi)存。
GPU 上共有64KB對(duì)所有線程可見的常量存儲(chǔ)器,以數(shù)據(jù) “不可變”作為代價(jià)換取比全局存儲(chǔ)器更快的訪問速度。PSO-NN 用于訓(xùn)練的樣本數(shù)據(jù)量較多 (十幾、幾十乃至上百個(gè)數(shù)據(jù)),都是常量且重復(fù)利用。因此和粒子速度、位置等信息存儲(chǔ)在全局內(nèi)存中不同,將訓(xùn)練樣本數(shù)據(jù)存放在常量內(nèi)存中,加快訪存速度。
GPU 上執(zhí)行PSO 的粒子速度更新需要大量的隨機(jī)數(shù)。早期的GPU 上沒有自帶的隨機(jī)數(shù)生成庫,需要將CPU 產(chǎn)生的隨機(jī)數(shù)傳至GPU (傳輸時(shí)間降低計(jì)算性能)[14],或編寫GPU 隨機(jī)數(shù)生成函數(shù) (使用不方便)[17]。目前,可以使用CURAND 庫中的curand_uniform ()函數(shù)在GPU 上產(chǎn)生隨機(jī)數(shù),這樣使整個(gè)迭代過程都在GPU 上完成,避免在CPU 和GPU 之間頻繁傳輸數(shù)據(jù)帶來的時(shí)間損耗。
本文采用一個(gè)簡單測試函數(shù)逼近對(duì)GPU-PSO-NN 算法和CPU-PSO-NN 算法進(jìn)行加速性能測試。
該函數(shù)表達(dá)式如式 (4)所示,在定義域 [-4,4]內(nèi)有兩個(gè)峰值點(diǎn),如圖8所示。訓(xùn)練函數(shù)集和測試函數(shù)集分別有101和100組輸入,如式(5)和式(6)所示,帶入式(4)可得其理論輸出。NN訓(xùn)練樣本的輸出均方誤差(MSE),即粒子的適應(yīng)度值,反映NN對(duì)測試函數(shù)的逼近程度。
圖8 測試函數(shù)
仿真計(jì)算過程中,NN 結(jié)構(gòu)設(shè)定為1-10-1,即輸入層1節(jié)點(diǎn)、隱層10節(jié)點(diǎn)、輸出層1節(jié)點(diǎn),權(quán)閾值數(shù)目為31(粒子維數(shù)),如圖9所示。隱層激活函數(shù)為雙極性S型函數(shù),其表達(dá)式如式 (7)所示。輸出層激活函數(shù)為線性函數(shù),其表達(dá)式如式 (8)所示
慣性權(quán)重w 取值0.9 至0.4線性遞減。學(xué)習(xí)因子c1和c2均取2.05。k取值0.5。訓(xùn)練次數(shù)Tmax取值1000。實(shí)驗(yàn)所采用的計(jì)算平臺(tái)見表1。為保證結(jié)果的可靠性,實(shí)驗(yàn)數(shù)據(jù)為20次實(shí)驗(yàn)去掉最大值和最小值之后18次的平均值。
“加速比”Siteration是最常用的加速性能指標(biāo),定義為PSO-NN 算法在相同的粒子數(shù)和相同的迭代次數(shù) (1000)下CPU 程 序 運(yùn) 行 時(shí) 間Tcpu-iteration和GPU 程 序 運(yùn) 行 時(shí) 間Tgpu-iteration的比值
圖9 實(shí)驗(yàn)所用的1-10-1結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)模型
表1 計(jì)算平臺(tái)
實(shí)驗(yàn)結(jié)果見表2。
表2 PSO-NN 作簡單測試函數(shù)逼近取得的加速比
對(duì)表2中的數(shù)據(jù)做如下分析:
(1)PSO-NN 完成1000 次迭代的運(yùn)行時(shí)間,在CPU程序中隨著粒子數(shù)的翻倍大致呈翻倍趨勢;在GPU 程序中當(dāng)粒子數(shù)小于等于16384 時(shí)呈小幅增長趨勢,大于等于32768時(shí)呈大幅增長趨勢 (其原因見 (2))。
(2)該GPU 共13個(gè)SM,每個(gè)SM 的最大駐留線程數(shù)為2048,總最大駐留線程數(shù)為26624。當(dāng)粒子數(shù) (線程數(shù))小于等于16384時(shí),各個(gè)粒子執(zhí)行時(shí)間相似,但同步 (包括kernel函數(shù)結(jié)束對(duì)應(yīng)的所有線程的同步,以及__syncthreads()調(diào)用對(duì)應(yīng)的線程塊內(nèi)線程的同步)所消耗的時(shí)間隨著粒子數(shù)的增多而小幅增長,造成PSO-NN 的運(yùn)行時(shí)間呈小幅增長趨勢;當(dāng)粒子數(shù)大于等于32768 時(shí),線程總數(shù)已超過26624,PSO-NN 的運(yùn)行時(shí)間呈大幅增長趨勢(當(dāng)粒子數(shù)翻倍,運(yùn)行時(shí)間增加不到1倍是基于以下3個(gè)原因的共同作用:①粒子數(shù)翻倍對(duì)應(yīng)運(yùn)行時(shí)間翻倍;②粒子數(shù)增多對(duì)應(yīng)同步時(shí)間增加;③線程切換能掩蓋存儲(chǔ)器訪問延遲,顯著減少執(zhí)行時(shí)間)。
分析表2中的數(shù)據(jù)可得如下結(jié)論:
(3)粒子數(shù)越多,獲得的加速比越高,PSO-NN 最高獲得了566倍的加速比。隨著粒子數(shù)的翻倍,當(dāng)粒子數(shù)小于等于16384,加速比大致翻倍;當(dāng)粒子數(shù)大于等于32768,加速比仍能增加但增速放緩。
(4)GPU-PSO-NN 具 有 與CPU-PSO-NN 同 樣 的 尋 優(yōu)穩(wěn)定性。隨著粒子數(shù)的不斷增多,CPU 程序和GPU 程序的訓(xùn)練誤差 (即NN 的MSE)不斷減小;粒子數(shù)相同時(shí),CPU 程序和GPU 程序的訓(xùn)練誤差大致相同或相近。
(5)大幅增加粒子數(shù)是適應(yīng)GPU 計(jì)算架構(gòu)的特殊方法。若GPU 端使用比CPU 端多的多的粒子,則可以在運(yùn)行時(shí)間增加極為有限的情況下大幅降低訓(xùn)練誤差。
另外作如下推斷:
(6)使用相同實(shí)驗(yàn)設(shè)備,筆者曾在CUDA 架構(gòu)下對(duì)Sphere、Rosenbrock、Rastrigrin、Griewangk 這4個(gè)基準(zhǔn)測試函數(shù)進(jìn)行了數(shù)值測試,以比較GPU-PSO 算法相對(duì)CPUPSO 算法的加速性能,結(jié)果表明,當(dāng)粒子數(shù)目小于100時(shí),往往不能得到加速。文獻(xiàn) [13]也進(jìn)行了類似測試,使用的粒子數(shù)目最小也為400 (具體為400、1200、2000、2800、5000)。而本文的實(shí)驗(yàn)當(dāng)粒子數(shù)目為32和64時(shí),也得到了加速。PSO-NN 算法本質(zhì)上就是適應(yīng)度函數(shù)為NN輸出誤差的PSO 算法,問題維數(shù)很多 (1-10-1簡單結(jié)構(gòu)的NN 就已有31維)且計(jì)算時(shí)反復(fù)使用,比起一般的基準(zhǔn)測試函數(shù)計(jì)算復(fù)雜度高的多。
可以推斷,用GPU 作并行加速時(shí),PSO-NN 由于適應(yīng)度函數(shù)計(jì)算量大,比起一般的PSO 能獲得更好的加速比,更適應(yīng)CUDA 并行計(jì)算架構(gòu)。
(7)對(duì)于該測試函數(shù)的NN 逼近問題,當(dāng)NN 訓(xùn)練樣本的MSE小于0.001起,測試樣本輸出曲線與實(shí)際曲線基本擬合,肉眼尚能明顯分清差別;當(dāng)MSE 小于0.0002起,測試樣本輸出曲線與實(shí)際曲線基本重合,肉眼不易分清差別;當(dāng)MSE小于0.0001起,測試樣本輸出曲線與實(shí)際曲線幾乎完全重合,肉眼幾乎不能分清差別。
根據(jù)經(jīng)驗(yàn),一般而言CPU 端粒子數(shù)應(yīng)多于問題維數(shù),以保證種群的多樣性,但粒子數(shù)過多又會(huì)增加計(jì)算時(shí)間,降低尋優(yōu)效率,顯著惡化CPU 端PSO-NN 算法性能而造成加速比虛假現(xiàn)象。當(dāng)粒子數(shù)為128、256、512、1024 時(shí),其CPU 程序?qū)?yīng)的MSE大致在0.001至0.0001之間,不妨認(rèn)為這些CPU 程序是 “高效的CPU 程序” (粒子數(shù)過少則逼近精度較差,“不合格”;粒子數(shù)過多則浪費(fèi)計(jì)算時(shí)間,“不值得”),其對(duì)應(yīng)的GPU 程序取得了5.6至44.0的加速比。
注意到本實(shí)驗(yàn)的測試函數(shù)逼近問題所用NN只有1個(gè)輸入層節(jié)點(diǎn)、1個(gè)輸出層節(jié)點(diǎn),網(wǎng)絡(luò)結(jié)構(gòu)非常簡單,問題維數(shù)較少(31維),實(shí)際問題往往是多輸入、多輸出、更多的隱層節(jié)點(diǎn)數(shù)、更多的權(quán)閾值數(shù)目,帶來的直接好處是,“高效的CPU 程序”對(duì)應(yīng)的粒子數(shù)以及獲得的加速比也會(huì)相應(yīng)增加。
可以推斷,NN 解決的問題越復(fù)雜,獲得的加速比越高。
本文采用CUDA 架構(gòu)設(shè)計(jì)并實(shí)現(xiàn)了PSO-NN 的并行加速求解。通過粒子與線程一一對(duì)應(yīng)的并行策略,采用適應(yīng)GPU 計(jì)算的優(yōu)化設(shè)計(jì)方法,實(shí)現(xiàn)了對(duì)NN 訓(xùn)練這一占整個(gè)程序絕大部分執(zhí)行時(shí)間的可并行部分的加速計(jì)算,并對(duì)一簡單測試函數(shù)逼近進(jìn)行了數(shù)值仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,相對(duì)于傳統(tǒng)的基于CPU 的串行PSO-NN,基于GPU 的并行PSO-NN 在尋優(yōu)穩(wěn)定性一致的前提下取得了超過500倍的計(jì)算加速比。本文提出的基于GPU 的并行PSO-NN 設(shè)計(jì)方案和優(yōu)化思路可以推廣應(yīng)用到其它類似實(shí)際問題的分析和設(shè)計(jì)中。
[1]Poli R,Kennedy J,Blackwell T.Particle swarm optimization:An overview [J].Swarm Intelligence,2007,1 (1):33-57.
[2]TIAN Yubo,LI Zhengqiang,WANG Jianhua.Model resonant frequency of rectangular microstrip antenna based on particle swarm neural network [J].Journal of Microwaves,2009,25 (5):45-50 (in Chinese).[田雨波,李正強(qiáng),王建華.矩形微帶天線諧振頻率的粒子群神經(jīng)網(wǎng)絡(luò)建模 [J].微波學(xué)報(bào),2009,25 (5):45-50.]
[3]Ganeshamoorthy K,Ranasinghe D N.On the performance of parallel neural network implementations on distributed memory architectures [C]//8th IEEE International Symposium on Cluster Computing and the Grid,2008:90-97.
[4]GUO Wensheng,LI Guohe.On designing artificial neural networks on parallel computer cluster[J].Computer Applications and Software,2010,27 (5):12-14 (in Chinese).[郭文生,李國和.人工神經(jīng)網(wǎng)絡(luò)在并行計(jì)算機(jī)集群上的設(shè)計(jì)研究 [J].計(jì)算機(jī)應(yīng)用與軟件,2010,27 (5):12-14.]
[5]ZHANG Daiyuan.Training algorithm for neural networks based on distributed parallel calculation [J].Systems Engineering and Electronics,2010,32 (2):386-391 (in Chinese).[張代遠(yuǎn).基于分布式并行計(jì)算的神經(jīng)網(wǎng)絡(luò)算法 [J].系統(tǒng)工程與電子技術(shù),2010,32 (2):386-391.]
[6]Singhal G,Jain A,Patnaik A.Parallelization of particle swarm optimization using message passing interfaces(MPIs)[C]//IEEE World Congress on Nature &Biologically Inspired Computing,2009:67-71.
[7]Deep K,Sharma S,Pant M.Modified parallel particle swarm optimization for global optimization using message passing interface [C]//IEEE Fifth International Conference on Bio-Inspired Computing:Theories and Applications,2010:1451-1458.
[8]Wang D Z,Wu C H.Parallel multi-population particle swarm optimization algorithm for the uncapacitated facility location problem using OpenMP [C]//IEEE Congress on Evolutionary Computation,2008:1214-1218.
[9]Maeda Y,Matsushita N.Simultaneous perturbation particle swarm optimization using FPGA [C]//IEEE International Joint Conference on Neural Networks,2007:2695-2700.
[10]Veronese L,Krohling R.Swarm’s flight:Accelerating the particles using C-CUDA [C]//Proceedings of the IEEE Congress on Evolutionary Computation,2009:3264-3270.
[11]Calazan R M,Nedjah N,de Macedo Mourelle L.Parallel GPU-based implementation of high dimension particle swarm optimizations[C]//IEEE Fourth Latin American Symposium on Circuits and Systems,2013:1-4.
[12]ZHANG Qingke,YANG Bo,WANG Lin,et al.Research on parallel modern optimization algorithms using GPU [J].Computer Science,2012,39 (4):304-311 (in Chinese).[張慶科,楊波,王琳,等.基于GPU 的現(xiàn)代并行優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2012,39 (4):304-311.]
[13]CAI Yong,LI Guangyao,WANG Hu.Research and implementation of parallel particle swarm optimization based on CUDA [J].Application Research of Computers,2013,30 (8):2415-2418 (in Chinese). [蔡勇,李光耀,王琥.基于CUDA 的并行粒子群優(yōu)化算法的設(shè)計(jì)與實(shí)現(xiàn) [J].計(jì)算機(jī)應(yīng)用研究,2013,30 (8):2415-2418.]
[14]Zhou Y,Tan Y.GPU-based parallel particle swarm optimization [C]//Proceedings of the IEEE Congress on Evolutionary Computation,2009:1493-1500.
[15]Mussi L,Daolio F,Cagnoni S.Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture[J].Information Sciences,2010,181 (20):4642-4657.
[16]Roberge V,Tarbouchi M.Efficient parallel Particle Swarm Optimizers on GPU for real-time harmonic minimization in multilevel inverters [C]//38th Annual Conference on IEEE Industrial Electronics Society,2012:2275-2282.
[17]Bastos-Filho CJA,Oliveira MAC,Nascimento DNO,et al.Impact of the random number generator quality on particle swarm optimization algorithm running on graphic processor units[C]//IEEE 10th International Conference on Hybrid Intelligent Systems,2010:85-90.