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

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

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

1.引 言

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

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

圖1 CPU與GPU的計算性能對比

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

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

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

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

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

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

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

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

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

3.1 與FPGA加速方案進行比較

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

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

3.2 與Cluster加速方案進行比較

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

4.GPU加速運算的實驗與分析

這里，基于Nvidia GT130M GPU與Intel Core2 T6500運算平臺，對GPU加速的運算能力及運算精度進行了初步的實驗分析。

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

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

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

圖4 同一計算問題的CPU與GPU計算時間對比(單位分別為S，Ms)

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

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

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

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

5.討論與結(jié)論

基于以上，采用GPU加速的FDTD運算技術(shù)，作為近幾年提出的一項新興硬件加速技術(shù)，具有優(yōu)秀的性能表現(xiàn)與可行性，該技術(shù)在與集群并行加速技術(shù)相結(jié)合方面的巨大潛力，尤其值得進一步的深入研究與開發(fā)。GPU加速FDTD運算技術(shù)依然存在不少需要解決的問題，只有解決了這些問題，才能使得GPU加速FDTD運算技術(shù)可以高效且便捷地投入工程應(yīng)用，而這也正是我們未來研究的目標(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é)報, 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]. 電子學(xué)報,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)加速時域有限元的二維輻射計算[J]. 電波科學(xué)學(xué)報, 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] 吳 霞,周樂柱. 時域有限元法在計算電磁問題上的發(fā)展[J]. 電波科學(xué)學(xué)報, 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 巨型計算機結(jié)合求解電大尺寸的電磁問題 [J]. 電波科學(xué)學(xué)報, 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)