一種基于PDD算法的ADI-FDTD算法研究

吳建斌，李太全，田 茂

1.華中師范大學(xué) 信息技術(shù)系，武漢 430079

2.長(zhǎng)江大學(xué) 物理科學(xué)與技術(shù)學(xué)院，湖北 荊州 434002

3.武漢大學(xué) 電子信息學(xué)院，武漢 430079

一種基于PDD算法的ADI-FDTD算法研究

吳建斌1，李太全2，田 茂3

1.華中師范大學(xué) 信息技術(shù)系，武漢 430079

2.長(zhǎng)江大學(xué) 物理科學(xué)與技術(shù)學(xué)院，湖北 荊州 434002

3.武漢大學(xué) 電子信息學(xué)院，武漢 430079

時(shí)域有限差分算法（FDTD）[1]被廣泛用于電磁散射、輻射、微波電路以及電磁兼容等領(lǐng)域，但是，較長(zhǎng)的計(jì)算時(shí)間和較大的存儲(chǔ)空間是FDTD在PC系統(tǒng)上求解復(fù)雜電磁場(chǎng)問(wèn)題的瓶頸。采用分布運(yùn)算實(shí)現(xiàn)并行FDTD[2-3]是解決這一問(wèn)題的有效方法之一。

顯式FDTD的時(shí)間步長(zhǎng)受Courant條件限制，為打破該條件的限制，提高計(jì)算效率，學(xué)者們提出了隱含變向時(shí)域有限差分算法（ADI-FDTD）[4-5]。然而，ADI-FDTD算法需要求解一組三對(duì)角方程，這組方程導(dǎo)致了并行ADI-FDTD方法的復(fù)雜化。在多指令多數(shù)據(jù)流（MIMD）并行系統(tǒng)[6]中求解三對(duì)角方程，必然存在大量數(shù)據(jù)通信，這將導(dǎo)致運(yùn)算效率低下。考慮到ADI-FDTD算法中三對(duì)角方程的對(duì)角占優(yōu)特性，采用并行對(duì)角占優(yōu)（PDD）算法[7]求解三對(duì)角方程，可顯著減少處理器間的數(shù)據(jù)通信，提高計(jì)算效率；當(dāng)然，該算法的近似處理會(huì)帶來(lái)一定誤差，為保證計(jì)算精度，F(xiàn)DTD子區(qū)域網(wǎng)格數(shù)和Courant因子需要滿足適當(dāng)條件。

1 子區(qū)域劃分與虛擬拓?fù)?/h2>

ADI-FDTD的并行計(jì)算如傳統(tǒng)FDTD的并行計(jì)算一樣，也是將整個(gè)計(jì)算區(qū)域在權(quán)衡運(yùn)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)的前提下劃分為若干個(gè)子區(qū)域。一般采用圖1所示的方法[2]，將計(jì)算區(qū)域沿著三個(gè)方向進(jìn)行分解，每個(gè)子區(qū)域?qū)?yīng)一個(gè)進(jìn)程，而每個(gè)進(jìn)程對(duì)應(yīng)拓?fù)渲械囊粋€(gè)節(jié)點(diǎn)。

圖1 子區(qū)域劃分

2 ADI-FDTD中的三對(duì)角方程組

隱含變向時(shí)域有限差分算法將一個(gè)時(shí)間步的電磁場(chǎng)量遞推分解為兩個(gè)亞時(shí)間步[4]進(jìn)行，在每個(gè)亞時(shí)間步的遞推運(yùn)算中，六個(gè)電磁場(chǎng)分量需求解三個(gè)三對(duì)角方程，如在第一個(gè)亞時(shí)間步選定Ex、Ey、Ez應(yīng)用方程組求解，直接計(jì)算Hx、Hy、Hz。以Ex為例，對(duì)應(yīng)三對(duì)角方程如下[4]：

其中α、β、γ、p、q是與空間步長(zhǎng)、時(shí)間步長(zhǎng)和介質(zhì)電磁特性相關(guān)的系數(shù)。第二個(gè)亞時(shí)間步計(jì)算式與式（1）類(lèi)似。

在求解方程（1）時(shí)，注意到z軸方向上相鄰子區(qū)域的Ex相互牽連，故可將圖1中沿z軸位于同一直線的子區(qū)域合并求解。并行對(duì)角占優(yōu)算法（PDD）通過(guò)近似處理，簡(jiǎn)化了子區(qū)域間的關(guān)聯(lián)，實(shí)現(xiàn)了方程（1）的高效求解。

3 解三對(duì)角方程組的PDD算法

將式（1）表示為矩陣形式，對(duì)于確定的i、j，有：

式（2）的解可以寫(xiě)成[7]：

其中I是單位矩陣，令Z=I+UTA~-1V，Z為五對(duì)角矩陣，且可以表示為：

（1）確定當(dāng)前節(jié)點(diǎn) p對(duì)應(yīng)子區(qū)域中網(wǎng)格i、j對(duì)應(yīng)的A(p)和d(p)。

（2）求解方程組：

得到方程的解：

與奇偶規(guī)約算法、遞歸耦合算法等比較，該算法的通信次數(shù)和傳輸信息量均有較大的下降。

4 誤差分析

考慮簡(jiǎn)化情況，設(shè)介質(zhì)相對(duì)導(dǎo)磁率μr=1、相對(duì)介電常數(shù)為 εr=1、導(dǎo)電率 σ=0，則系數(shù)

這里，v為電磁波波速，S是Courant因子。對(duì)于式（2）的解（11），采用文獻(xiàn)[8]的方法，可以導(dǎo)出其解的相對(duì)誤差：

其中a、b為方程組：

對(duì)于預(yù)定相對(duì)誤差上限δ，m和S的選擇應(yīng)位于圖2所示對(duì)應(yīng)曲線的上部。

圖2 相對(duì)誤差δ的等值線圖

5 MPI實(shí)現(xiàn)與效率分析

將子區(qū)域的上、下、前、后、左、右六個(gè)相鄰單元，分別用up、down、front、back、left和right標(biāo)示，ADI-FDTD算法的MPI實(shí)現(xiàn)步驟如下：

（1）MPI、FDTD初始化。

（2）第一亞時(shí)間步迭代。

（2.1）PDD算法計(jì)算電場(chǎng)分量。

（2.2）傳遞分界面上的電場(chǎng)分量：底層的Ex、Ez傳送到down，并接收來(lái)自u(píng)p的頂層Ex、Ez，頂層的Ey傳送到up，并接收來(lái)自down的底層Ey；left、right和back、front的通信類(lèi)似。

（2.3）計(jì)算磁場(chǎng)分量。

（2.4）傳遞分界面上的磁場(chǎng)分量：頂層的Hx、Hz傳送到up，并接收來(lái)自down的底層 Hx、Hz；left、right和back、front的通信類(lèi)似，分別傳遞Hy、Hz和Hx、Hy。

（3）第二亞時(shí)間步迭代：與第一亞時(shí)間步類(lèi)似。

（4）未達(dá)到預(yù)定迭代時(shí)間，到（2）循環(huán)；否則，MPI、ADI-FDTD結(jié)束。

在假設(shè)各個(gè)節(jié)點(diǎn)任務(wù)完全均衡的情況下，可用單個(gè)計(jì)算節(jié)點(diǎn)的效率表示ADI-FDTD算法的效率。對(duì)于處理網(wǎng)格數(shù)為nx×ny×nz子區(qū)域的節(jié)點(diǎn)，在一個(gè)亞時(shí)間步迭代中，運(yùn)算時(shí)間其中te、th分別為一個(gè)場(chǎng)點(diǎn)的電場(chǎng)、磁場(chǎng)計(jì)算所需時(shí)間。設(shè)此次計(jì)算所需的通信時(shí)間開(kāi)銷(xiāo)為T(mén)co，節(jié)點(diǎn)的效率可以由η=Tc/(Tc+Tco)表示。在集群系統(tǒng)中，一次通信時(shí)間可由tα+tβNB近似表示。這里tα為通信響應(yīng)時(shí)間，tβ為一字節(jié)數(shù)據(jù)的傳輸時(shí)間，NB為傳輸?shù)淖止?jié)數(shù)，且tα＞＞tβ?？梢钥闯觯L(zhǎng)消息通信具有更高的通信效率。故可在步驟（2.1）中，先對(duì)i、j循環(huán)，并存儲(chǔ)相應(yīng)中間結(jié)果，實(shí)現(xiàn)對(duì)的成批傳送，獲取更高的通信效率。這樣，每個(gè)電場(chǎng)分量的計(jì)算只需要3次通信，共計(jì)9次通信，這里將一組發(fā)送和接收看作一次通信。在步驟（2.2），有9次通信，在步驟（2.4），有6次通信，共計(jì)24次通信。一個(gè)亞時(shí)間步迭代中的總通信時(shí)間約為

在阻塞通信方式下，算法的效率為：

采用非阻塞通信，步驟（2.2）、（2.4）中的通信可與場(chǎng)量計(jì)算并行，效率會(huì)提高。但在步驟（2.1）中的9次通信只能采用阻塞通信。

與傳統(tǒng)FDTD相比，增加了步驟（2.1）中的9次通信和步驟（2.2）中的3次通信，通信任務(wù)增加了一倍。但是，時(shí)間步長(zhǎng)的增大使迭代次數(shù)大幅減少，這就減少了ADI-FDTD的總通信時(shí)間，提高了其計(jì)算效率。

6 數(shù)值實(shí)驗(yàn)

為分析PDD算法的效率，并檢驗(yàn)其帶來(lái)的誤差，計(jì)算了如圖3所示的不連續(xù)帶狀線。帶狀線寬b=6 mm，不連續(xù)窄口寬d=0.5 mm，位于寬w=50 mm、高h(yuǎn)=10 mm、長(zhǎng)l=60 mm的矩形波導(dǎo)中心，內(nèi)部介質(zhì)相對(duì)介電常數(shù)εr=1，相對(duì)導(dǎo)磁率 μr=1，兩端為理想導(dǎo)體邊界。e為激勵(lì)電流源位于左端點(diǎn)。v為觀察點(diǎn)，距離右端點(diǎn)2.5 mm。

圖3 低通濾波器結(jié)構(gòu)

將整個(gè)空間劃分為 Nx×Ny×Nz=50×10×600網(wǎng)格，此時(shí) ?z=0.1 mm，?x=?y=1 mm。取時(shí)間步長(zhǎng) ?t=10×，則S=10，依次將空間沿 z軸等距分為1、4、6、8、12個(gè)子區(qū)域，則子區(qū)域在z方向的網(wǎng)格數(shù)m分別為600、150、100、75、50。子區(qū)域數(shù)為1時(shí)，不需用PDD算法，可作為檢驗(yàn)PDD算法誤差的基準(zhǔn)。計(jì)算得到觀測(cè)點(diǎn)的磁場(chǎng)Hz及其相對(duì)誤差（其中δHz為計(jì)算結(jié)果相對(duì)于基準(zhǔn)之差，HM為基準(zhǔn)在計(jì)算時(shí)間內(nèi)的最大值）如圖4所示，從圖中的結(jié)果看，隨著子區(qū)域m的減小，誤差逐漸增大。

圖4 一組m值對(duì)應(yīng)觀測(cè)點(diǎn)磁場(chǎng)和誤差比較

對(duì)于m為50、75、100、150，算例的相對(duì)誤差與式（15）估計(jì)值比較如表1所示。在計(jì)算誤差較小時(shí)，算例的誤差大于式（15）的估計(jì)值是由于截?cái)嘈?yīng)所導(dǎo)致。

表1 m為不同值算例的相對(duì)誤差與由式（15）估計(jì)的相對(duì)誤差比較（%）

為了檢驗(yàn)PDD算法誤差隨S的變化情況，保持子區(qū)域網(wǎng)格數(shù) m=50不變，當(dāng) S逐漸減小（即?t減小）時(shí)，在S=10、S=8、S=6、S=4情況下計(jì)算得到的觀測(cè)點(diǎn)磁場(chǎng)Hz的一組數(shù)據(jù)如圖4所示。由于ADI-FDTD的截?cái)嗾`差也會(huì)因?yàn)?t增大而增大[9-10]，故將其與非PDD算法的計(jì)算結(jié)果進(jìn)行比較，相對(duì)誤差δHz/HM如圖5所示。可以看出，隨著S逐漸減小，其誤差越來(lái)越小，當(dāng)S=4時(shí)，最大誤差僅為0.005%，與式（15）估計(jì)接近。

圖5 在S為10、8、6、4時(shí)，觀測(cè)點(diǎn)的誤差比較

上述算例在由個(gè)人計(jì)算機(jī)組成10個(gè)節(jié)點(diǎn)的實(shí)驗(yàn)系統(tǒng)中完成（每個(gè)節(jié)點(diǎn)的CPU主頻3 GHz，內(nèi)存1 GB，100 Mb/s網(wǎng)卡，100 Mb/s交換機(jī)），測(cè)得te=0.219 1 μs，th=0.025 67 μs，tα=26.3 μs，tβ=0.143 μs。

為比較傳統(tǒng)的FDTD算法和PDD算法的計(jì)算效率，分別測(cè)試完成450次迭代的時(shí)間，統(tǒng)計(jì)數(shù)據(jù)如表2。由于算例的計(jì)算空間為扁長(zhǎng)形，其虛擬拓?fù)錇橐痪S分布，除兩端的計(jì)算節(jié)點(diǎn)外，中間節(jié)點(diǎn)均只同前后相鄰節(jié)點(diǎn)通信，發(fā)生通信阻塞的幾率很低，所以，表2中的迭代時(shí)間幾乎與節(jié)點(diǎn)數(shù)成反比。

表2 不同區(qū)域劃分的運(yùn)算時(shí)間比較 s

7 結(jié)束語(yǔ)

本文將PDD算法引入到并行ADI-FDTD中，減少了基于MPI的MIMD并行系統(tǒng)的處理器間數(shù)據(jù)通信的開(kāi)銷(xiāo)，提高了計(jì)算效率。PDD算法的引入會(huì)帶來(lái)誤差，其誤差大小與Courant因子S和分割方向的子區(qū)域網(wǎng)格數(shù)m相關(guān)，為保證計(jì)算的精度S、m應(yīng)滿足式（15）所限定的條件。對(duì)于空間網(wǎng)格數(shù)較少的系統(tǒng)，m的限制將會(huì)制約計(jì)算節(jié)點(diǎn)的充分利用，在此情況下，應(yīng)采用其他方法求解三對(duì)角方程組。

與傳統(tǒng)FDTD相比，ADI-FDTD的MPI實(shí)現(xiàn)，雖然節(jié)點(diǎn)間的通信增多，但增大了大時(shí)間步長(zhǎng)，使迭代次數(shù)大為減少，提高了計(jì)算效率。

[1]葛德彪，閆玉波.電磁波時(shí)域有限差分方法[M].西安：西安電子科技大學(xué)出版社，2002：2-3.

[2]張玉，李斌，梁昌洪.PC集群系統(tǒng)中MPI并行FDTD性能研究[J].電子學(xué)報(bào)，2005，33（9）：1694-1697.

[3]楊利霞，葛德彪，鄭奎松，等.電各向異性介質(zhì)FDTD并行算法的研究[J].電波科學(xué)學(xué)報(bào)，2006，21（1）：43-48.

[4]Namiki T.3-D ADI-FDTD method unconditionally stable time-domain algorithm forsolving fullvectormaxwells equations[J].IEEE TransactionsonMicrowave Theoryand Techniques，2000，48（10）：1743-1747.

[5]Namiki T.A new FDTD algorithm based on alternatingdirection implicitmethod[J].IEEE Transactionson Microwave Theory and Techniques，1999，47（10）：2003-2007.

[6]都志輝.高性能計(jì)算并行編程技術(shù)[M].北京：清華大學(xué)出版社，2001.

[7]Sun Xianhe，Zhang Hong，Ni L.Efficient tridiagonal solvers on multicomputers[J].IEEE Transactions on Computers，1992，41（3）：286-296.

[8]Sun Xianhe.Application and accuracy of the parallel diagonal dominant algorithm[J].Parallel Computing，1995，21（8）：1241-1268.

[9]Zheng Fenghua，Chen Zhizhang.Numerical dispersion analysis of the unconditionally stable 3-D ADI-FDTD method[J]. IEEE Transactions on Microwave Theory and Techniques，2001，49（5）：1006-1009.

[10]Garcia S G，Lee T W，Hagness S C.On the accuracy of theADI-FDTD method[J].IEEE Antennasand Wireless Propagation Letters，2002，1（1）：31-34.

WU Jianbin1,LI Taiquan2,TIAN Mao3

1.Department of Information Technology,Huazhong Normal University,Wuhan 430079 China
2.School of Physical Science and Technology,Yangtze University,Jingzhou,Hubei 434002,China
3.School of Electronic Information,Wuhan University,Wuhan 430079,China

In order to improve calculation efficiency of the Alternating-Direction Implicit FDTD（ADI-FDTD）,the paper realizes the ADI-FDTD parallel calculation by introducing the Parallel Diagonal Dominant algorithm（PDD）,taking into account the PDD is an efficacious method in solution of tri-diagonal liner equations.By comparing the calculation and communication time spent,the efficiency of calculation is discussed in the paper.The error is introduced with the approximate treatment of PDD.The estimate of the error is researched which correlates with the number of grid in sub region and Courant factor.It can help to select suitable number of grid in sub region and Courant factor for decreasing the estimate of the error.The conclusions are confirmed in numerical emulation experiment.

Alternating-Direction Implicit Finite Difference Time Domain（ADI-FDTD）;division of sub region;Parallel Diagonal Dominant（PDD）algorithm;Courant factor

為提高隱含變向時(shí)域有限差分算法（ADI-FDTD）的計(jì)算效率，鑒于并行對(duì)角占優(yōu)算法（PDD）求解三對(duì)角方程的高效性，引入PDD算法實(shí)現(xiàn)了基于MPI的ADI-FDTD的并行計(jì)算。通過(guò)對(duì)運(yùn)算時(shí)間、通信時(shí)間的分析，討論了算法的效率。分析了由于PDD算法的近似處理所引入的計(jì)算誤差，研究了誤差估計(jì)與子區(qū)域網(wǎng)格數(shù)和Courant因子的關(guān)系，該研究工作有利于合理選擇子區(qū)域網(wǎng)格數(shù)和Courant因子，進(jìn)而減小計(jì)算誤差。最后，通過(guò)算例驗(yàn)證了結(jié)論的正確性。

隱含變向時(shí)域有限差分算法；子區(qū)域劃分；并行對(duì)角占優(yōu)算法；Courant因子

A

TN01

10.3778/j.issn.1002-8331.1202-0358

WU Jianbin,LI Taiquan,TIAN Mao.Research of ADI-FDTD algorithm based on parallel diagonal dominant algorithm. Computer Engineering and Applications,2013,49（23）：195-198.

華中師范大學(xué)中央高?；究蒲袠I(yè)務(wù)研究基金。

吳建斌（1972—），男，博士，副教授，碩士生導(dǎo)師，從事天線和計(jì)算電磁學(xué)方面的研究；李太全（1961—），男，博士，副教授，從事天線和計(jì)算電磁學(xué)方面的研究；田茂（1957—），男，博士，教授，博導(dǎo)，從事探地雷達(dá)和無(wú)線通信方面的研究。E-mail：wujianbin@mail.ccnu.edu.cn

2012-02-20

2012-06-08

1002-8331（2013）23-0195-04