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

吳建斌，李太全，田 茂

1.華中師范大學 信息技術系，武漢 430079

2.長江大學 物理科學與技術學院，湖北 荊州 434002

3.武漢大學 電子信息學院，武漢 430079

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

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

1.華中師范大學 信息技術系，武漢 430079

2.長江大學 物理科學與技術學院，湖北 荊州 434002

3.武漢大學 電子信息學院，武漢 430079

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

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

1 子區(qū)域劃分與虛擬拓撲

ADI-FDTD的并行計算如傳統FDTD的并行計算一樣，也是將整個計算區(qū)域在權衡運算開銷和通信開銷的前提下劃分為若干個子區(qū)域。一般采用圖1所示的方法[2]，將計算區(qū)域沿著三個方向進行分解，每個子區(qū)域對應一個進程，而每個進程對應拓撲中的一個節(jié)點。

圖1 子區(qū)域劃分

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

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

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

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

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

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

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

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

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

（2）求解方程組：

得到方程的解：

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

4 誤差分析

考慮簡化情況，設介質相對導磁率μr=1、相對介電常數為 εr=1、導電率 σ=0，則系數

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

其中a、b為方程組：

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

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

5 MPI實現與效率分析

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

（1）MPI、FDTD初始化。

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

（2.1）PDD算法計算電場分量。

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

（2.3）計算磁場分量。

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

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

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

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

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

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

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

6 數值實驗

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

圖3 低通濾波器結構

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

圖4 一組m值對應觀測點磁場和誤差比較

對于m為50、75、100、150，算例的相對誤差與式（15）估計值比較如表1所示。在計算誤差較小時，算例的誤差大于式（15）的估計值是由于截斷效應所導致。

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

為了檢驗PDD算法誤差隨S的變化情況，保持子區(qū)域網格數 m=50不變，當 S逐漸減?。?t減小）時，在S=10、S=8、S=6、S=4情況下計算得到的觀測點磁場Hz的一組數據如圖4所示。由于ADI-FDTD的截斷誤差也會因為?t增大而增大[9-10]，故將其與非PDD算法的計算結果進行比較，相對誤差δHz/HM如圖5所示?？梢钥闯?，隨著S逐漸減小，其誤差越來越小，當S=4時，最大誤差僅為0.005%，與式（15）估計接近。

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

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

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

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

7 結束語

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

與傳統FDTD相比，ADI-FDTD的MPI實現，雖然節(jié)點間的通信增多，但增大了大時間步長，使迭代次數大為減少，提高了計算效率。

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

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

[3]楊利霞，葛德彪，鄭奎松，等.電各向異性介質FDTD并行算法的研究[J].電波科學學報，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]都志輝.高性能計算并行編程技術[M].北京：清華大學出版社，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）的計算效率，鑒于并行對角占優(yōu)算法（PDD）求解三對角方程的高效性，引入PDD算法實現了基于MPI的ADI-FDTD的并行計算。通過對運算時間、通信時間的分析，討論了算法的效率。分析了由于PDD算法的近似處理所引入的計算誤差，研究了誤差估計與子區(qū)域網格數和Courant因子的關系，該研究工作有利于合理選擇子區(qū)域網格數和Courant因子，進而減小計算誤差。最后，通過算例驗證了結論的正確性。

隱含變向時域有限差分算法；子區(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.

華中師范大學中央高校基本科研業(yè)務研究基金。

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

2012-02-20

2012-06-08

1002-8331（2013）23-0195-04