共享內(nèi)存系統(tǒng)中高效并行FDTD計(jì)算方案

賴生建，王秉中，黃廷祝

(1. 電子科技大學(xué)物理電子學(xué)院 成都 610054; 2. 電子科技大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 成都 610054)

目前，基于多核多處理器(CPU)和大容量?jī)?nèi)存的計(jì)算機(jī)已成為進(jìn)行工程計(jì)算仿真的主流配置，許多商業(yè)電磁仿真軟件都提供了支持在多核系統(tǒng)上的并行計(jì)算功能。在計(jì)算電大的電磁問題時(shí)，計(jì)算效率比單處理器系統(tǒng)有顯著的提高。

在電磁仿真的各種數(shù)值算法中，時(shí)域有限差分(FDTD)法[1]由于Yee元胞上的場(chǎng)只與相鄰元胞上的場(chǎng)有關(guān)系，因此具有天然的并行性，F(xiàn)DTD是最具并行計(jì)算效率的電磁場(chǎng)數(shù)值方法。傳統(tǒng)的FDTD并行算法首先對(duì)計(jì)算區(qū)域進(jìn)行并行區(qū)域劃分，然后在各區(qū)域上單獨(dú)進(jìn)行FDTD計(jì)算，通過(guò)同步并交換并行邊界面上的場(chǎng)量實(shí)現(xiàn)并行FDTD計(jì)算。并行邊界數(shù)據(jù)交換技術(shù)一般有3種[2]：(1) 各并行邊界面上的場(chǎng)量只計(jì)算一次的方式，再交換相鄰區(qū)域的切向電場(chǎng)和切向磁場(chǎng)，但該方式要通過(guò)兩次數(shù)據(jù)交換操作，并行效率低。(2) 采用只中斷一次的方式，只交換一次相鄰區(qū)域切向磁場(chǎng)數(shù)據(jù)，并行計(jì)算效率高，但交界面上的場(chǎng)分量要計(jì)算兩次。(3) 各并行區(qū)域的交界面上重疊一個(gè)網(wǎng)格的方式，雖多消耗了一層網(wǎng)格占用的資源，但便于處理交界面的材料、共性網(wǎng)格等信息，該處理方式更具有通用性。

電磁場(chǎng)并行數(shù)值計(jì)算的編程實(shí)現(xiàn)通常采用消息傳遞方式(MPI)庫(kù)進(jìn)行開發(fā)[3-4]，也有基于共享內(nèi)存方式的OpenMP庫(kù)開發(fā)[5]。并行FDTD計(jì)算也采用這些開發(fā)技術(shù)，通過(guò)MPI創(chuàng)建的每個(gè)并行區(qū)域計(jì)算任務(wù)(進(jìn)程)[6-7]，在計(jì)算進(jìn)程中分配各區(qū)域的FDTD計(jì)算資源，進(jìn)行當(dāng)前區(qū)域的FDTD步進(jìn)計(jì)算。通過(guò)MPI庫(kù)的傳送和接收函數(shù)實(shí)現(xiàn)并行邊界上數(shù)據(jù)交換，再調(diào)用MPI的等待函數(shù)同步所有并行區(qū)域的計(jì)算任務(wù)，協(xié)調(diào)FDTD的并行計(jì)算。

傳統(tǒng)并行FDTD計(jì)算通過(guò)并行邊界上的數(shù)據(jù)交換方式實(shí)現(xiàn)，如果取消數(shù)據(jù)交換的過(guò)程，節(jié)省該過(guò)程的處理時(shí)間，可能會(huì)進(jìn)一步提高并行FDTD的計(jì)算效率?；谶@種思想，本文提出一種在共享內(nèi)存系統(tǒng)中進(jìn)行高效并行FDTD計(jì)算的方案，對(duì)方案所涉及的算法思路、并行區(qū)域劃分方式及編程實(shí)現(xiàn)技術(shù)進(jìn)行分析和討論，最后進(jìn)行數(shù)值仿真測(cè)試。

1 基于共享內(nèi)存系統(tǒng)的并行FDTD計(jì)算方案

共享內(nèi)存系統(tǒng)的應(yīng)用程序開發(fā)有多進(jìn)程和多線程兩種方式。多進(jìn)程程序中的各進(jìn)程管理各自的計(jì)算資源，進(jìn)程間的數(shù)據(jù)共享通過(guò)消息方式數(shù)據(jù)傳遞實(shí)現(xiàn)[8]；而多線程程序中的各線程可以分享主進(jìn)程程序分配的所有計(jì)算資源，直接共享程序中的數(shù)據(jù)，如圖1所示。利用多線程程序開發(fā)的該特點(diǎn)，并行FDTD計(jì)算可以選擇直接讀取內(nèi)存數(shù)據(jù)的方式實(shí)現(xiàn)并行計(jì)算。

圖1 應(yīng)用程序共享數(shù)據(jù)資源示意圖

為實(shí)現(xiàn)共享內(nèi)存系統(tǒng)下的并行FDTD計(jì)算，本文提出多線程下的并行FDTD計(jì)算思路：首先根據(jù)仿真實(shí)例統(tǒng)一分配和計(jì)算FDTD仿真所需的資源，即統(tǒng)一剖分Yee元胞、激勵(lì)源、材料、后處理和邊界條件等一系列FDTD仿真前處理所涉及的各物理量的分配和計(jì)算，完成FDTD循環(huán)步進(jìn)計(jì)算前的準(zhǔn)備；然后根據(jù)FDTD并行計(jì)算設(shè)置，對(duì)仿真區(qū)域進(jìn)行區(qū)域劃分；再采用多線程技術(shù)分配和管理各區(qū)域的FDTD計(jì)算；最后通過(guò)直接讀取各區(qū)域間的并行邊界上場(chǎng)量數(shù)據(jù)，實(shí)現(xiàn)整個(gè)仿真區(qū)域的FDTD并行計(jì)算。該實(shí)現(xiàn)思路針對(duì)整個(gè)FDTD計(jì)算資源離散化，對(duì)各區(qū)域資源進(jìn)行并行計(jì)算控制。對(duì)任意復(fù)雜模型都可以采用相同的處理過(guò)程，因此它具有很強(qiáng)的實(shí)踐性和通用性。

圖2 基于共享內(nèi)存系統(tǒng)的FDTD并行計(jì)算區(qū)域劃分示意圖

基于本文提出的并行FDTD計(jì)算思路，進(jìn)行區(qū)域劃分，其劃分方式與傳統(tǒng)并行FDTD計(jì)算一樣，并行區(qū)域邊界面與Yee電場(chǎng)網(wǎng)格重合，如圖2所示。為了自然地共享并行邊界上的場(chǎng)量，本文提出一種巧妙而又簡(jiǎn)潔的對(duì)并行邊界上場(chǎng)量的分配策略：區(qū)域中坐標(biāo)軸正方向上的并行邊界，包含在該區(qū)域進(jìn)行FDTD計(jì)算；坐標(biāo)軸負(fù)方向上的并行邊界，就排除該區(qū)域范圍，并入緊鄰區(qū)域進(jìn)行FDTD計(jì)算。該種排列方式可以避免在并行邊界上計(jì)算兩次場(chǎng)量的情況發(fā)生，也不會(huì)有因兩個(gè)區(qū)域共用并行邊界造成的數(shù)據(jù)交換操作。圖2中，虛線包含的區(qū)域?yàn)椴⑿袇^(qū)域的FDTD計(jì)算范圍，如圖中所標(biāo)識(shí)的(I,J,K)并行區(qū)域，在x軸負(fù)方向上的并行邊界(左邊界)上，場(chǎng)量在該區(qū)域不計(jì)算，而是由(I?1,J,K)區(qū)域的FDTD計(jì)算；右并行邊界面上場(chǎng)量由本區(qū)域的FDTD計(jì)算，其他方向類推。

并行計(jì)算的編程實(shí)現(xiàn)大都采用MPI庫(kù)，該庫(kù)是一個(gè)功能齊全、可移植性強(qiáng)的并行計(jì)算控制庫(kù)[9]。然而所提出的并行FDTD計(jì)算策略，因其并行計(jì)算的資源控制比較簡(jiǎn)潔，只需要同步計(jì)算控制等少數(shù)操作，并不需要很復(fù)雜控制的龐大MPI函數(shù)庫(kù)。另外，采用MPI庫(kù)編寫的程序要受MPI程序控制，并行計(jì)算的開發(fā)和調(diào)試不方便。另一個(gè)廣泛使用的并行控制庫(kù)OpenMP也有相似的特點(diǎn)。因此，利用多線程開發(fā)技術(shù)共享內(nèi)存資源的特點(diǎn)，本文采用自主開發(fā)多線程編程技術(shù)[10]實(shí)現(xiàn)并行FDTD計(jì)算，即各并行區(qū)域的FDTD計(jì)算由各計(jì)算線程控制并協(xié)調(diào)并行FDTD計(jì)算。并行邊界上的場(chǎng)量數(shù)據(jù)采用直接讀取共享內(nèi)存中數(shù)據(jù)的方式，實(shí)現(xiàn)“數(shù)據(jù)交換”。

圖3 共享內(nèi)存方式的并行FDTD計(jì)算流程圖

基于共享內(nèi)存方式并行FDTD計(jì)算的流程圖如圖3所示。首先分配FDTD在整個(gè)仿真區(qū)域上的計(jì)算資源，在內(nèi)存中這些計(jì)算資源按整個(gè)仿真區(qū)域分配FDTD仿真所需的三維數(shù)組變量。若采用并行計(jì)算，在并行方向上以均衡方式自動(dòng)劃分各并行區(qū)域網(wǎng)格數(shù)目和計(jì)算并行FDTD計(jì)算的全局參數(shù)。然后創(chuàng)建各區(qū)域的FDTD計(jì)算線程；啟動(dòng)各計(jì)算線程進(jìn)入各區(qū)域的FDTD計(jì)算；各區(qū)域計(jì)算完磁場(chǎng)后，判斷其他區(qū)域是否完成磁場(chǎng)計(jì)算，若沒有，則當(dāng)前計(jì)算線程進(jìn)入判斷全局并行標(biāo)志的空循環(huán)中，等到為真時(shí)退出；若其他線程都完成了磁場(chǎng)計(jì)算，則設(shè)置全局并行標(biāo)志為真，各計(jì)算線程退出循環(huán)，進(jìn)入電場(chǎng)及邊界計(jì)算。各計(jì)算線程完成電場(chǎng)及邊界計(jì)算后，各計(jì)算線程等待一次，其處理方式與前面磁場(chǎng)計(jì)算相同。計(jì)算完電場(chǎng)后，全域FDTD仿真中的場(chǎng)源激勵(lì)計(jì)算和觀測(cè)數(shù)據(jù)保存等處理部分單獨(dú)計(jì)算，由最后計(jì)算完電場(chǎng)的計(jì)算線程來(lái)完成，然后判斷FDTD仿真是否完成，若沒有完成，所有計(jì)算線程進(jìn)入下一步進(jìn)的計(jì)算。

因采用并行邊界上只計(jì)算一次場(chǎng)量的區(qū)域劃分策略，并行邊界相鄰一個(gè)網(wǎng)格上場(chǎng)量的計(jì)算都需要相鄰區(qū)域的場(chǎng)量，各并行區(qū)域FDTD的電場(chǎng)和磁場(chǎng)單獨(dú)計(jì)算后，要求等待其他并行區(qū)域的FDTD計(jì)算完成后，才能繼續(xù)計(jì)算，即每次FDTD步進(jìn)計(jì)算需等待兩次。

與傳統(tǒng)并行FDTD計(jì)算相比，本文提出基于共享內(nèi)存方式的并行FDTD計(jì)算方案沒有數(shù)據(jù)交換過(guò)程，采用沒有計(jì)算線程的掛起和恢復(fù)等并行控制操作，減少了影響并行計(jì)算的因素，提高了并行FDTD計(jì)算效率。下面通過(guò)數(shù)值仿真實(shí)驗(yàn)，測(cè)試所提出的基于共享內(nèi)存系統(tǒng)并行FDTD計(jì)算方案的計(jì)算效率，并與傳統(tǒng)并行計(jì)算方式進(jìn)行比較。

2 并行FDTD計(jì)算方案測(cè)試

加速比是衡量并行系統(tǒng)計(jì)算性能的參數(shù)，定義多核計(jì)算機(jī)系統(tǒng)中并行FDTD計(jì)算的加速比為：

式中tseq為用單線程計(jì)算全區(qū)域FDTD所需的時(shí)間；tp為用p個(gè)線程控制p個(gè)并行區(qū)域的FDTD計(jì)算相同問題所需的時(shí)間，p個(gè)并行區(qū)域構(gòu)成整個(gè)FDTD仿真區(qū)域。

采用雙Xeon E5310 CPU服務(wù)器測(cè)試并行FDTD計(jì)算方案的計(jì)算性能。E5310 CPU是主頻為1.6 GHz、266 MHz的前端總線、系統(tǒng)總線為1 066 MHz、二級(jí)緩存為4MB×2的4核處理器，共有8個(gè)計(jì)算內(nèi)核。測(cè)試的計(jì)算實(shí)例是大小為100×100×100標(biāo)準(zhǔn)Yee元胞測(cè)試盒，總仿真步長(zhǎng)設(shè)為1 000步。

在不同方向上采用不同并行區(qū)域劃分方式，所提出的并行方案與傳統(tǒng)數(shù)據(jù)交換方式并行方案的加速比對(duì)比表如表1所示。表中，NX、NY、NZ分別表示仿真區(qū)域在x、y、z坐標(biāo)方向上的并行區(qū)域數(shù)目。從表中可看出，前8行是單獨(dú)在x方向劃分并行區(qū)域方式，基于共享內(nèi)存方式加速比比傳統(tǒng)數(shù)據(jù)交換方式高，并且隨著并行區(qū)域的劃分越多，加速比越高。主要原因是傳統(tǒng)數(shù)據(jù)交換方式的并行FDTD仿真中，每次步進(jìn)計(jì)算都要交換一次并行邊界數(shù)據(jù)，并行區(qū)域越多，要交換數(shù)據(jù)量也越大，而不交換數(shù)據(jù)的共享內(nèi)存并行FDTD計(jì)算沒有這部分過(guò)程，提高了并行計(jì)算效率。即使不交換數(shù)據(jù)的共享內(nèi)存方式有兩次線程等待過(guò)程，多等待一次的時(shí)間比通過(guò)數(shù)據(jù)交換時(shí)間要少得多。

表1 Xeon E5310服務(wù)器上并行FDTD計(jì)算性能

從表中還可看出，在兩個(gè)計(jì)算線程下，基于不交換數(shù)據(jù)的共享內(nèi)存方式的并行FDTD計(jì)算，其加速比達(dá)1.85，而文獻(xiàn)[11]采用MPI編程技術(shù)，對(duì)同樣的問題進(jìn)行計(jì)算，雙核時(shí)的加速比只能達(dá)到1.3左右。本文采用傳統(tǒng)的數(shù)據(jù)交換方式，其加速比也達(dá)到1.84，說(shuō)明采用不同的并行計(jì)算策略對(duì)并行效率有很大的影響。另外，本文又在雙核Intel E6550個(gè)人計(jì)算機(jī)上對(duì)以上相同的問題進(jìn)行測(cè)試，所提出的方案其加速比也達(dá)1.90。雖然基于共享內(nèi)存系統(tǒng)的并行FDTD計(jì)算因爭(zhēng)搶計(jì)算機(jī)的系統(tǒng)總線、內(nèi)存等資源，降低了加速效率，但本文的方案充分挖掘了并行FDTD的計(jì)算潛力和利用了多核計(jì)算系統(tǒng)的計(jì)算能力，具有很高的加速比。

3 結(jié) 論

在科學(xué)計(jì)算中，如何充分利用計(jì)算資源提高計(jì)算效率是高性能數(shù)值計(jì)算中的研究?jī)?nèi)容。本文提出一種不交換并行邊界數(shù)據(jù)的并行FDTD計(jì)算方案，并采用自主開發(fā)的多線程編程技術(shù)控制各區(qū)域并行FDTD計(jì)算。通過(guò)數(shù)值仿真測(cè)試表明，只在x方向并行區(qū)域劃分方式下，不交換數(shù)據(jù)的并行計(jì)算方案比傳統(tǒng)數(shù)據(jù)交換方案有更高的加速比，是一種理想的共享內(nèi)存系統(tǒng)的并行FDTD計(jì)算方式。

[1] YEE K S. Numerical solution of initial boundary value problems involving Maxwell’s equations in isotropic media[J]. IEEE Transaction Antennas and Propagation, 1966,14(1): 302-307.

[2] YU W H, SU T, MITTRA R, et al. Parallel finite difference time domain method[M]. London: Artech House, 2006.

[3] YU W H, MITTRA R, SU T, et al. A robust parallelized conformal finite difference time domain field solver package using the MPI library[J]. IEEE Transaction Antennas and Propagation, 2005, 47(3): 39-59.

[4] GUIFFAUT C, MAHDJOUBI K. A parallel FDTD algorithm using the MPI library[J]. IEEE Transaction Antennas and Propagation, 2001, 43(2): 94-103.

[5] BUCHAU A, HAFLA S M W, RUCKER W M.Parallelization of a fast multipole boundary element method with cluster OpenMP[J]. IEEE Transaction Magnetics, 2008,44(6): 1338-1341.

[6] 張 玉, 李 斌, 梁昌洪. PC集群系統(tǒng)中MPI并行FDTD性能研究[J]. 電子學(xué)報(bào), 2005, 33(9): 1694-1697.ZHANG Yu, LI Bin, LIANG Chang-hong. Study on performance of MPI based parallel FDTD on PC clusters[J].Acta Electonic Sinica, 2005, 33(9):1694-1697.

[7] 梁 丹, 馮 菊, 陳 星. 高效率FDTD網(wǎng)絡(luò)并行計(jì)算研究[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 43(3): 549-555.LIANG Dan, FENG Ju, CHEN Xing. A study of efficient parallel FDTD methods on cluster systems[J]. Journal of Sichuan University (Natural Science Edition), 2006, 43(3):549-555.

[8] 何元清, 孫世新, 傅 彥. 并行編程模式及分析[J]. 電子科技大學(xué)學(xué)報(bào), 2002, 31(2): 173-175.HE Yuan-qing, SUN Shi-xin, FU Yan. Parallel programming mode and analysis[J]. Journal of University of Electronic Science and Technology of China, 2002, 31(2):173-175.

[9] GROPP W, EWING L, ANTHONY S. Using MPI: portable parallel programming with the message-passing interface[M]. 2th Ed. Cambridge: MIT Press, 1999: 10-35.

[10] DAVID J K, SCOT W, GEORGE S. Programming microsoft visual C++[M]. 5th ed. USA: Microsoft Press,1999.

[11] CIAMULSKI T, HJELM M, SYPNIEWSKI M. Parallel FDTD calculation efficiency on computers with shared memory architecture[C]//CEM-TD 2007 Workshop. Italy:Perugia, 2007.