摘要：為降低粒子群優(yōu)化算法（PSO:Particle Swarm Optimization）時(shí)間和空間的復(fù)雜度隨問(wèn)題規(guī)模的增大而越來(lái)越高的問(wèn)題，對(duì)圖形處理器（GPU:Graphic Processing Unit）用于并行計(jì)算的方法進(jìn)行了分析，利用GPU的并行特性，實(shí)現(xiàn)了粒子群優(yōu)化算法路徑搜索過(guò)程的并行化.測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果證明，GPU平臺(tái)較CPU模式下的計(jì)算，其搜索速率有明顯提高.

　　O 引言

　　圖形處理芯片（GPU:Graphic Processing Unit）技術(shù)日漸成熟，當(dāng)前可編程圖像處理器已發(fā)展為計(jì)算技術(shù)領(lǐng)域的主力¨‘2 J,在計(jì)算技術(shù)方面其性能是CPU的數(shù)十倍甚至百倍，GPU已經(jīng)成為現(xiàn)在為強(qiáng)大的計(jì)算設(shè)備，沖擊并超越了CPU獨(dú)霸的地位，徹底改變當(dāng)今計(jì)算行業(yè)的面貌.GPU和其相關(guān)軟硬件的發(fā)展產(chǎn)生了強(qiáng)大的市場(chǎng)動(dòng)力，因此GPU得到了快速發(fā)展.日前GPU的發(fā)展速度已經(jīng)超過(guò)了計(jì)算機(jī)摩爾定律.

　　并行計(jì)算是-f]較為年輕的學(xué)科，隨著多開(kāi)發(fā)環(huán)境的日漸成熟，并行計(jì)算的優(yōu)勢(shì)得到開(kāi)發(fā)者的重視和認(rèn)同.筆者將粒子群優(yōu)化算法的路徑搜索過(guò)程在GPU平臺(tái)上實(shí)現(xiàn)并行化，利用開(kāi)發(fā)軟件的多線(xiàn)程.單指令的GPU架構(gòu)提高搜索速率，將GPU架構(gòu)應(yīng)用于并行計(jì)算，取得較好的加速比，從而提高了計(jì)算能力.

　　1 并行計(jì)算

　　并行處理是-f-j綜合性的計(jì)算機(jī)學(xué)科，包括硬件技術(shù).算法語(yǔ)言和程序設(shè)計(jì)等.而并行計(jì)算是相對(duì)于串行計(jì)算而言，同時(shí)利用多種計(jì)算資源解決計(jì)算問(wèn)題的過(guò)程.在時(shí)間上，并行是指流水線(xiàn)技術(shù)，空間上，并行則是指用多個(gè)處理器并發(fā)執(zhí)行計(jì)算.在并行計(jì)算的過(guò)程中，一個(gè)任務(wù)可能涉及到的問(wèn)題有：任務(wù)分解.任務(wù)依賴(lài)關(guān)系.任務(wù)粒度分配.任務(wù)交互和并發(fā)度等.由于并行計(jì)算是用多個(gè)處理器去共同完成一個(gè)計(jì)算任務(wù)，能地減少任務(wù)完成的實(shí)際物理時(shí)間，所以相對(duì)于串行算法，并行算法能高效解決大規(guī)模運(yùn)算量的問(wèn)題.筆者研究了如何在更好的平臺(tái)下進(jìn)行并行計(jì)算，從而加快求解問(wèn)題的速度，提高求解問(wèn)題的規(guī)模.

　　2 GPU架構(gòu)的計(jì)算方法

　　GPU具有強(qiáng)大的計(jì)算能力，其架構(gòu)是專(zhuān)為大量并行運(yùn)算優(yōu)化設(shè)計(jì)的.在繪制圖像時(shí)，GPU首先接收宿主系統(tǒng)以三角頂點(diǎn)形式發(fā)送的幾何數(shù)據(jù)，再由一個(gè)可編程的頂點(diǎn)處理器對(duì)這些數(shù)據(jù)進(jìn)行處理，包括幾何變換和亮度計(jì)算等三角形計(jì)算等；然后，這些三角形由光柵器轉(zhuǎn)換成能顯示在屏幕上的單獨(dú)“碎片”,所有碎片都通過(guò)可編程碎片處理器計(jì)算終顏色值.GPU在處理大尺寸圖像時(shí)具有的優(yōu)勢(shì)，如在8 192×8 192像素圖像的直方圖生成中，排除內(nèi)存分配.讀回的時(shí)間和數(shù)據(jù)加載后，GPU的時(shí)間消耗僅為19 ms左右，計(jì)算效率是CPU的17倍之多.基于GPU的信息抽取算法，能使圖像的文本語(yǔ)義信息描述更加細(xì)致完整，系統(tǒng)的功能和性能獲得很大提升.

　　GPU計(jì)算一般采用Brook編譯，Brook支持所有帶附加流數(shù)據(jù)的c句法，流數(shù)據(jù)存儲(chǔ)于GPU的存儲(chǔ)器中，而核函數(shù)也在GPU上執(zhí)行.早期Brook編譯效率很低，只能使用像素著色器進(jìn)行運(yùn)算.同時(shí)Brook也缺乏有效的數(shù)據(jù)通信機(jī)制.AMD（Advanced Micro Devices）公司采用Brook的改進(jìn)版本Brook+作為開(kāi)發(fā)語(yǔ)言，提高了效率.由于GPU具有高效的并行性和靈活的可編程性等特點(diǎn)，越來(lái)越多的研究人員和商業(yè)組織開(kāi)始利用GPU完成一些非圖形繪制方面的計(jì)算，并開(kāi)創(chuàng)了新的研究領(lǐng)域.GPU在高性能計(jì)算方面所具有的優(yōu)勢(shì)體現(xiàn)在：高效的并行性.超長(zhǎng)的圖形流水線(xiàn).高密集的運(yùn)算.控制簡(jiǎn)單和分多個(gè)階段執(zhí)行等方面.早的GPU開(kāi)發(fā)直接使用圖形學(xué)的應(yīng)用程序編程接口（API:Application ProgrammingInterface）編程.這種開(kāi)發(fā)方式首先要求將數(shù)據(jù)打包成紋理，然后將計(jì)算任務(wù)映射為對(duì)紋理的渲染過(guò)程，用匯編或者著色語(yǔ)言編寫(xiě)shader程序，然后通過(guò)圖形學(xué)AP（Application Processor）執(zhí)行.

　　NVIDIA公司推出了統(tǒng)一的計(jì)算設(shè)備架構(gòu)（CUDA:Compute Unified Device Architecture），所以，當(dāng)前GPU“摒棄”傳統(tǒng)的圖形應(yīng)用處理器AP.這種框架使用并行計(jì)算內(nèi)核函數(shù)，使GPU能解決復(fù)雜的計(jì)算問(wèn)題.一個(gè)完整的CUDA程序是由一系列的設(shè)備端kernel函數(shù)的并行步驟和主機(jī)端的串行處理步驟共同組成的，每個(gè)kernel內(nèi)核函數(shù)在一個(gè)由多個(gè)大小相同.組織為一維或二維的線(xiàn)程塊網(wǎng)格中被執(zhí)行，線(xiàn)程的總數(shù)等于每個(gè)塊中的線(xiàn)程數(shù)與塊數(shù)的乘積.同一線(xiàn)程塊內(nèi)的線(xiàn)程可通過(guò)高帶寬的共享存儲(chǔ)器進(jìn)行協(xié)作，軟件開(kāi)發(fā)人員可以基于CUDA平臺(tái)開(kāi)發(fā)計(jì)算軟件，用戶(hù)可以用比以往少得多的時(shí)間完成多個(gè)計(jì)算任務(wù).

　　其顯著的優(yōu)點(diǎn)是提高計(jì)算的速率.現(xiàn)有多種軟件工具和語(yǔ)言可以簡(jiǎn)化GPU的編程工作，同時(shí)產(chǎn)生GPU開(kāi)發(fā)的計(jì)算工具包，能利用GPU平臺(tái)進(jìn)行排序及線(xiàn)性方程組的求解，實(shí)現(xiàn)并行的搜索算法.離散優(yōu)化算法等多種科學(xué)計(jì)算.

　　3 GPU架構(gòu)下的并行算法

　　粒子群優(yōu)化算法（PSO:Particle Swarm Optimization）是處理連續(xù)優(yōu)化問(wèn)題的算法.

　　PSO算法的計(jì)算公式如下：

　　但該算法仍存在下述問(wèn)題：隨著問(wèn)題規(guī)模的增大，計(jì)算時(shí)間和空間的復(fù)雜度越來(lái)越高.為減小計(jì)算的復(fù)雜度可讓多只螞蟻在GPU的核處理器上進(jìn)行并行搜索，即將路徑搜索的過(guò)程在GPU上實(shí)現(xiàn)并行化，在基于CUDA平臺(tái)開(kāi)發(fā)軟件的多線(xiàn)程.單指令的架構(gòu)上提高搜索速率.從而降低算法在時(shí)間和空間上的復(fù)雜度.筆者采用如圖1所示的流程對(duì)不同粒子數(shù)的運(yùn)行時(shí)間進(jìn)行實(shí)驗(yàn)，利用Windows XP操作系統(tǒng)，Pentium 2.66 GHz CPU環(huán)境，對(duì)實(shí)驗(yàn)測(cè)試函數(shù)：

　　進(jìn)行實(shí)驗(yàn)運(yùn)算，其中d表示搜索范圍（一100-100）.采用不同的處理器進(jìn)行運(yùn)算時(shí)，若速度提高S倍，則稱(chēng)該任務(wù)的加速比為S,定義為：

　　其中咒表示用GPU處理器所需要的物理時(shí)間，k表示用CPU處理器所需要的物理時(shí)間.實(shí)驗(yàn)結(jié)果如表1所示.

　　由表l可看出，PSO算法在GPU與CPU不同平臺(tái)的加速比與粒子數(shù)有關(guān)，當(dāng)粒子數(shù)大于820時(shí)，GPU架構(gòu)算法的速度開(kāi)始大于CPU算法速度，并隨著粒子數(shù)的增大，其加速比也明顯增大.實(shí)驗(yàn)結(jié)果證明，當(dāng)粒子數(shù)為某個(gè)固定數(shù)值時(shí)，基于GPU架構(gòu)的高浮點(diǎn)數(shù)計(jì)算的并行特性，GPU模式相比CPU模式下的計(jì)算，可提高算法的速度，降低算法的復(fù)雜度.

　　4 結(jié)語(yǔ)

　　筆者利用GPU提供的平臺(tái)進(jìn)行并行計(jì)算，通過(guò)提高速度縮短計(jì)算任務(wù)的完成時(shí)間，這是利用并行處理器的強(qiáng)大能力實(shí)現(xiàn)的創(chuàng)新.隨著GPU芯片集成技術(shù)的優(yōu)化改進(jìn).目前在信息檢索.生物基因技術(shù)領(lǐng)域.人工神經(jīng)網(wǎng)絡(luò)并行分布性處理.數(shù)據(jù)挖掘等方面，GPU已經(jīng)突破了很多技術(shù)屏障.GPU這種為強(qiáng)大的計(jì)算設(shè)備，正在改變計(jì)算行業(yè)面貌，如在圖片和視頻的處理，分類(lèi).解析幾何等方面的應(yīng)用.支持CUDA的GPU可以成為由若干個(gè)向量處理器組成的超級(jí)計(jì)算機(jī).GPU的架構(gòu)還會(huì)不斷優(yōu)化，CPU和GPU各有所長(zhǎng).CPU的資源多用于緩存，GPU的資源多用于數(shù)據(jù)計(jì)算.如果將二者組合，相互取長(zhǎng)補(bǔ)短，將融合得情況來(lái)提高電腦的運(yùn)行效率，提高性?xún)r(jià)比，為人們帶來(lái)新的選擇.CPU在GPU的影響下也逐漸找回自己的優(yōu)勢(shì).未來(lái)算法執(zhí)行的架構(gòu)會(huì)越來(lái)越傾向CPU/GPU集群的協(xié)作模式.整合后的模式較傳統(tǒng)的CPU將有更為突出的優(yōu)勢(shì).