吳建斌，李太全，田 茂

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

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

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

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

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

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

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

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

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

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

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

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

圖1 子區(qū)域劃分

2 ADI-FDTD中的三對角方程組

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

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

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

3 解三對角方程組的PDD算法

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

式（2）的解可以寫成[7]：

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

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

（2）求解方程組：

得到方程的解：

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

4 誤差分析

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

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

其中a、b為方程組：

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

圖2 相對誤差δ的等值線圖

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

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

（1）MPI、FDTD初始化。

（2）第一亞時間步迭代。

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

（2.2）傳遞分界面上的電場分量：底層的Ex、Ez傳送到down，并接收來自up的頂層Ex、Ez，頂層的Ey傳送到up，并接收來自down的底層Ey；left、right和back、front的通信類似。

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

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

（3）第二亞時間步迭代：與第一亞時間步類似。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

[1]葛德彪，閆玉波.電磁波時域有限差分方法[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

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

隱含變向時域有限差分算法；子區(qū)域劃分；并行對角占優(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á)和無線通信方面的研究。E-mail：wujianbin@mail.ccnu.edu.cn

2012-02-20

2012-06-08

1002-8331（2013）23-0195-04