基于圖形處理器的時(shí)域有限差分算法研究

張 波 薛正輝 任 武 李偉明 盛新慶

(北京理工大學(xué)信息與電子學(xué)院，北京 100081)

1.引 言

GPU是現(xiàn)代圖形處理器(Graphic Processing Units)的簡(jiǎn)稱，它將數(shù)據(jù)流并行處理的概念引入硬件結(jié)構(gòu)中，具有高性能的數(shù)據(jù)并行處理能力。在人們的通常概念中，GPU就是計(jì)算機(jī)顯卡上的圖像處理芯片，專事負(fù)責(zé)計(jì)算機(jī)顯示圖像的處理工作。在2002年，世界領(lǐng)先的顯卡公司英偉達(dá)(NVIDIA)在其NV30圖形處理器中引入了可編程流處理器(Programmable Stream Processor)的概念，其后,由于圖形圖像處理相關(guān)產(chǎn)業(yè)的推動(dòng)，GPU發(fā)展迅速，與中央處理器(CPU)相比GPU價(jià)格不高，針對(duì)某些問(wèn)題的專門(mén)運(yùn)算能力卻高出幾十到幾百倍。舉例而言，一塊型號(hào)為NVIDIA Tesla C1060的GPU具有240個(gè)流數(shù)據(jù)處理器，具有933GFLOPS單精度，78GFLOPS雙精度的浮點(diǎn)運(yùn)算能力，而最新Intel i5 CPU浮點(diǎn)運(yùn)算能力僅為42GFlops。圖1顯示了CPU、圖形GPU(使用開(kāi)放圖形庫(kù)(OpenGL))和直接計(jì)算 GPU(采用計(jì)算統(tǒng)一設(shè)備架構(gòu)(CUDA)編程環(huán)境)的掃描性能對(duì)比。其中GPU采用了NVIDIA GeForce 8800 GTX，而CPU采用的是Intel Core2Duo Extreme 2.93 GHz CPU.

從圖1中可以看出:應(yīng)用CUDA的GPU運(yùn)算比CPU運(yùn)算的加速比達(dá)到了20倍，而且元數(shù)目越多，其加速的優(yōu)勢(shì)越明顯?？梢?jiàn)GPU的性能遠(yuǎn)高于高端的CPU。正是由于GPU的這種超強(qiáng)的專門(mén)計(jì)算能力使得人們對(duì)它在通用計(jì)算方面的應(yīng)用潛力加以了關(guān)注?，F(xiàn)代的GPU具有一般意義的數(shù)據(jù)流并行計(jì)算能力，實(shí)現(xiàn)了從固定圖形管線向可編程圖形管線過(guò)渡，不僅為圖形領(lǐng)域的應(yīng)用提供強(qiáng)大而靈活的處理能力，同時(shí)也使得在圖形處理器上實(shí)現(xiàn)數(shù)據(jù)流并行計(jì)算成為可能。這種執(zhí)行通用計(jì)算的GPU一般稱之為通用計(jì)算圖形處理單元(GPGPU)，在GPGPU上執(zhí)行的運(yùn)算稱為GPGPU運(yùn)算。

圖1 CPU與GPU的計(jì)算性能對(duì)比

在2000年左右，即有研究者開(kāi)展了在GPU上執(zhí)行通用計(jì)算的嘗試，Hopf等人在GPU上實(shí)現(xiàn)了小波變換，2001年Larsen等人在GPU上實(shí)現(xiàn)了矩陣運(yùn)算，2002年Harris等人在GPU上實(shí)現(xiàn)了加速光線跟蹤算法。2003年堪稱GPGPU領(lǐng)域具有里程碑意義的一年，Krug等人在GPU上實(shí)現(xiàn)了線性代數(shù)操作等一大批成果。到2007年，J.D.Owens 等人發(fā)表了一篇關(guān)于GPGPU研究的總結(jié)報(bào)告:“A Survey of General-Purpose Computation on Graphics Hardware”，對(duì)GPGPU運(yùn)算進(jìn)行了非常好的總結(jié)[1]。2008年，J.D.Owens等人又發(fā)表了GPGPU運(yùn)算的技術(shù)總結(jié)文章：“GPU Computing”，標(biāo)志著GPGPU運(yùn)算技術(shù)逐步走向成熟和應(yīng)用階段[2]。

在電磁場(chǎng)數(shù)值計(jì)算領(lǐng)域，2004年Krakiwsky等人即實(shí)現(xiàn)了利用GPU加速電磁場(chǎng)FDTD運(yùn)算[3]，其他一些研究者也開(kāi)展了開(kāi)拓性的工作，美國(guó)斯坦福大學(xué)和萊斯大學(xué)，加拿大卡爾加里大學(xué)的研究者都已經(jīng)廣泛深入地開(kāi)展了利用GPU進(jìn)行電磁場(chǎng)數(shù)值計(jì)算的工作[4-5]。在國(guó)內(nèi)，2006年，南京理工大學(xué)的李蔚清、南京電子技術(shù)研究所的楊正龍等人即開(kāi)展了基于GPU的復(fù)雜目標(biāo)電磁散射快速算法研究[6-7]。2007年山東大學(xué)的韓林等人開(kāi)展了利用GPU結(jié)合網(wǎng)絡(luò)并行運(yùn)算技術(shù)的FDTD算法研究，針對(duì)光波導(dǎo)器件為分析對(duì)象進(jìn)行了非常有意義的探索[8]。2008年，電子科技大學(xué)聶在平教授的課題組開(kāi)展了GPU運(yùn)算在快速多極子算法方面的應(yīng)用研究[9]，西南交通大學(xué)的劉昆等人開(kāi)展了GPU加速時(shí)域有限元的二維輻射計(jì)算研究[10-11]。可見(jiàn)國(guó)內(nèi)的相關(guān)研究也正在逐步展開(kāi)，并且日漸活躍。至今，相關(guān)研究者已經(jīng)公認(rèn)，GPU運(yùn)算時(shí)代正在來(lái)臨，基于GPU運(yùn)算的相關(guān)技術(shù)研究和應(yīng)用必將獲得極大重視。

2. GPU加速FDTD運(yùn)算的實(shí)現(xiàn)原理

與傳統(tǒng)CPU運(yùn)算相比，GPU運(yùn)算的優(yōu)勢(shì)在于其強(qiáng)大的多流處理器并行能力，因此，運(yùn)用GPU運(yùn)算，就需要徹底改變?cè)谝酝茖W(xué)計(jì)算中對(duì)于CPU的黑盒操作方式，即將指令對(duì)象細(xì)化至單顆GPU中的各個(gè)流處理器與內(nèi)存控制器，同時(shí)，也正是各個(gè)流處理器的任務(wù)分配與數(shù)據(jù)傳遞效率，在極大程度上決定了GPU運(yùn)算的速度。以Fermi系列GPU為例，其內(nèi)部執(zhí)行單元結(jié)構(gòu)圖見(jiàn)圖2[12]。

圖2 Fermi 架構(gòu) GPU內(nèi)部執(zhí)行單元結(jié)構(gòu)

從圖2可以看出：與傳統(tǒng)CPU運(yùn)算的單線程運(yùn)行，獨(dú)占內(nèi)存(RAM)方式不同，GPU運(yùn)算采取多線程(Thread)，共享RAM的方式。在CUDA架構(gòu)下，程序執(zhí)行運(yùn)算指令時(shí)的最小單位是Thread，數(shù)個(gè)Thread 可以組成一個(gè)線程塊(Block)。一個(gè)Block 中的Thread 能存取同一塊共享的內(nèi)存，而且，可以快速進(jìn)行同步的動(dòng)作。每一個(gè)Block 所能包含的Thread 數(shù)目是有限的，不過(guò)執(zhí)行相同程序的Block，可以組成線程網(wǎng)絡(luò)(Grid)。不同Block中的Thread無(wú)法存取同一個(gè)共享的內(nèi)存，因此，無(wú)法直接互通或進(jìn)行同步。因此，不同Block中的Thread能合作的程度是比較低的。不過(guò)，利用這個(gè)模式，可以讓程序不用擔(dān)心顯示芯片實(shí)際上能同時(shí)執(zhí)行的Thread數(shù)目限制，同時(shí)也能很好地減少數(shù)據(jù)讀取的延時(shí)。

GPU的這種高度并行的多流水線架構(gòu)，使其非常適宜于FDTD加速運(yùn)算。與CPU運(yùn)算的多次循環(huán)逐網(wǎng)格迭代更新方式不同，GPU可以實(shí)現(xiàn)多網(wǎng)格的同時(shí)迭代更新，配合GPU的線程集(Warp)指令執(zhí)行機(jī)制，可以高效地利用流水線資源，隱藏流處理器與顯存間的場(chǎng)量讀寫(xiě)延時(shí)，從而實(shí)現(xiàn)FDTD運(yùn)算加速。

3. GPU加速與其他硬件加速方式比較

近年來(lái)，針對(duì)FDTD的硬件加速，已經(jīng)有現(xiàn)場(chǎng)可編程門(mén)序列(FPGA)及多計(jì)算機(jī)集群(Cluster)等加速方案[13]，為了分析GPU加速的特點(diǎn)，將GPU加速方案與這兩種方案進(jìn)行比較。

3.1 與FPGA加速方案進(jìn)行比較

首先，在芯片運(yùn)算能力方面，同期GPU產(chǎn)品浮點(diǎn)運(yùn)算能力遠(yuǎn)高于FPGA。以NVIDIA Tesla C1060的GPU為例，其單精度浮點(diǎn)運(yùn)算能力為933GFLOPS，而同期Xilinx Virtex5 SXT-240T芯片的單精度浮點(diǎn)運(yùn)算能力僅為190GFLOPS.

在數(shù)據(jù)帶寬方面，同期GPU產(chǎn)品的顯存帶寬也遠(yuǎn)高于FPGA產(chǎn)品。再以NVIDIA Tesla C1060的GPU為例，其采用了512位DDR3顯存，帶寬高達(dá)102 GB/S，而同期Xilinx Virtex5 SXT-240T配合 DDR2 內(nèi)存，帶寬僅為2.128 GB/S/.

在程序開(kāi)發(fā)平臺(tái)方面，面向GPU開(kāi)發(fā)基于CUDA平臺(tái)及C語(yǔ)言環(huán)境，程序操作對(duì)象可以為一系列不同的GPU芯片，程序具有較好的可讀性與可移植性，而FPGA開(kāi)發(fā)基于ISE開(kāi)發(fā)環(huán)境和VHDL語(yǔ)言，程序設(shè)計(jì)是針對(duì)具體型號(hào)的FPGA芯片及其附屬電路，可讀性與可移植性相對(duì)較差。

3.2 與Cluster加速方案進(jìn)行比較

從前文可知，GPU加速的理念是運(yùn)用GPU加速單節(jié)點(diǎn)計(jì)算機(jī)的運(yùn)算速度，與Cluster加速方案所遵循的通過(guò)并行多個(gè)節(jié)點(diǎn)計(jì)算機(jī)以實(shí)現(xiàn)FDTD加速的理念并不沖突。因此，GPU加速并不會(huì)取代Cluster加速，相反，兩者可以進(jìn)行很好的結(jié)合，通過(guò)GPU加速來(lái)提高單節(jié)點(diǎn)的運(yùn)算速度，再通過(guò)多節(jié)點(diǎn)并行加速來(lái)實(shí)現(xiàn)在單節(jié)點(diǎn)加速基礎(chǔ)上的進(jìn)一步加速，同時(shí)，通過(guò)與Cluster加速方案的結(jié)合，基于GPU的FDTD運(yùn)算也可以克服顯存容量的瓶頸，實(shí)現(xiàn)對(duì)電大尺寸的計(jì)算。

4.GPU加速運(yùn)算的實(shí)驗(yàn)與分析

這里，基于Nvidia GT130M GPU與Intel Core2 T6500運(yùn)算平臺(tái)，對(duì)GPU加速的運(yùn)算能力及運(yùn)算精度進(jìn)行了初步的實(shí)驗(yàn)分析。

圖3是一個(gè)典型一維高斯脈沖垂直入射PEC板情況的CPU與GPU運(yùn)算結(jié)果對(duì)比，可見(jiàn)GPU運(yùn)算結(jié)果與CPU運(yùn)算結(jié)果吻合程度非常好。

圖4則是使用CPU與GPU計(jì)算同一FDTD問(wèn)題所消耗的時(shí)間，盡管商用GPU相對(duì)專用GPU，在浮點(diǎn)運(yùn)算能力上存在很大差距(C2050雙精度計(jì)算能力可以達(dá)到520 GFlops，而進(jìn)行原理實(shí)驗(yàn)的GT130M不支持雙精度計(jì)算，單精度計(jì)算能力也僅為144 GFlops)，但相對(duì)于主流CPU，已經(jīng)可以實(shí)現(xiàn)近5倍的加速。并且隨著FDTD程序針對(duì)GPU優(yōu)化的深入，性能提升的空間依然存在。

圖3 GPU運(yùn)算與傳統(tǒng)CPU運(yùn)算的結(jié)果對(duì)比

圖4 同一計(jì)算問(wèn)題的CPU與GPU計(jì)算時(shí)間對(duì)比(單位分別為S，Ms)

同時(shí)，在我們的研究過(guò)程中，發(fā)現(xiàn)現(xiàn)有GPU加速FDTD方式依然存在以下尚待解決的問(wèn)題：

1) GPU受限于自身的架構(gòu)與設(shè)計(jì)，在運(yùn)算精度方面存在限制。

2) 傳統(tǒng)FDTD算法的架構(gòu)流程尚不能最大化利用GPU運(yùn)算資源。

3) GPU加速FDTD運(yùn)算的加速能力受系統(tǒng)總線間數(shù)據(jù)交換速率影響較大。

5.討論與結(jié)論

基于以上，采用GPU加速的FDTD運(yùn)算技術(shù)，作為近幾年提出的一項(xiàng)新興硬件加速技術(shù)，具有優(yōu)秀的性能表現(xiàn)與可行性，該技術(shù)在與集群并行加速技術(shù)相結(jié)合方面的巨大潛力，尤其值得進(jìn)一步的深入研究與開(kāi)發(fā)。GPU加速FDTD運(yùn)算技術(shù)依然存在不少需要解決的問(wèn)題，只有解決了這些問(wèn)題，才能使得GPU加速FDTD運(yùn)算技術(shù)可以高效且便捷地投入工程應(yīng)用，而這也正是我們未來(lái)研究的目標(biāo)。

[1] OWENS J D, LUEBKE D, GOVINDARAJU N. A survey of general-purpose computation on graphics hardware[R]. Computer Graphics Forum, 2007, 26(1): 80-113.

[2] OWENS J D, HOUSTON M, LUEBKE D,et al. GPU Computing[J]. Proceedings of The IEEE, 2008, 96(5): 1-18.

[3] KRAKIWSKY S E, TUMER L E, OKONIEWSKI M M. Acceleration of Finite-Difference Time-Domain (FDTD) Using Graphics Processor Units (GPU)[J]. IEEE MTTS Digest, 2004:1033-1036.

[4] STEFANSKI,T P, DRYSDALE T D. Acceleration of the 3D ADI-FDTD method using graphics processor units[J]. IEEE MTT-S International Microwave Symposium Digest (MTT), 2009:241.

[5] PRICE D K, HUMPHREY J R , KELMELIS E J . GPU-Based accelerated 2D and 3D FDTD solvers[J]. Physics and Simulation of Optoelectronic Devices XV, San Jose, CA, 2007(1):22-25.

[6] 李蔚清, 蘇智勇, 楊正龍. 一種基于GPU的復(fù)雜目標(biāo)電磁散射快速算法[J]. 系統(tǒng)仿真學(xué)報(bào), 2006,18(8):2214-1128.

LI Weiqing, SU Zhiyong, YANG Zhenglong. Fast algorithm for RCS of complex objects on GPU[J]. Acta Simulata Systematica Sinica, 2006,18(8):2214-1128.(in Chinese)

[7] 楊正龍,金 林,李蔚清. 基于GPU的圖形電磁計(jì)算加速算法[J]. 電子學(xué)報(bào),2007,35(6):1056-1060.

YANG Zhenglong, JIN Lin, LI Weiqing. Accelerated GRECO based on GPU[J].Acta Electronica Sinica, 2007,35(6):1056-1060. (in Chinese)

[8] 韓 林. 基于GPU的光波導(dǎo)器件FDTD并行算法研究[D]. 山東大學(xué)碩士論文, 2007.

[9] PENG Shaoxin, NIE Zaiping. Acceleration of the method of moments calculations by using graphics processing units[J]. IEEE Transactions on Antennas and Propagation, 2008, 56(7): 2130-2133.

[10] 劉 昆,王曉斌,廖 成. 圖形處理器(GPU)加速時(shí)域有限元的二維輻射計(jì)算[J]. 電波科學(xué)學(xué)報(bào), 2008,23(1):111-114.

LIU Kun, WANG Xiaobing, LIAO Cheng. Acceleration of time-domain finite element 2-D radiation using graphics processor units(GPU)[J]. Chinese Journal of Radio Science, 2008,23(1):111-114.(in Chinese)

[11] 吳 霞,周樂(lè)柱. 時(shí)域有限元法在計(jì)算電磁問(wèn)題上的發(fā)展[J]. 電波科學(xué)學(xué)報(bào), 2008, 23(6):1208-1216.

WU Xia,ZHOU Lezhu. Application and development of time-domain finite element method on EM analysis[J]. Chinese Journal of Radio Science, 2008,23(1):111-114.(in Chinese)

[12] NVIDIA Company. NVIDIA Fermi Compute Architecture Whitepaper Version 1.1[S].2009.5

[13] 余文華,楊小玲,劉永俊. 并行 FDTD和IBM BlueGene/L 巨型計(jì)算機(jī)結(jié)合求解電大尺寸的電磁問(wèn)題 [J]. 電波科學(xué)學(xué)報(bào), 2006, 21(4):562-566.

YU Wenhua, YANG Xiaoling, LIU Yongjun. Solving electrically large EM problems using parallel FDTD and IBM BlueGene/L supercomputer[J]. Chinese Journal of Radio Science, 2006, 21(4):562-566.(in Chinese)