一种基于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算法中三对角方程的对角占优特性，采用并行对角占优（PDD）算法[7]求解三对角方程，可显著减少处理器间的数据通信，提高计算效率；当然，该算法的近似处理会带来一定误差，为保证计算精度，FDTD子区域网格数和Courant因子需要满足适当条件。

1 子区域划分与虚拟拓扑

ADI-FDTD的并行计算如传统FDTD的并行计算一样，也是将整个计算区域在权衡运算开销和通信开销的前提下划分为若干个子区域。一般采用图1所示的方法[2]，将计算区域沿着三个方向进行分解，每个子区域对应一个进程，而每个进程对应拓扑中的一个节点。

图1 子区域划分

2 ADI-FDTD中的三对角方程组

隐含变向时域有限差分算法将一个时间步的电磁场量递推分解为两个亚时间步[4]进行，在每个亚时间步的递推运算中，六个电磁场分量需求解三个三对角方程，如在第一个亚时间步选定Ex、Ey、Ez应用方程组求解，直接计算Hx、Hy、Hz。以Ex为例，对应三对角方程如下[4]：

其中α、β、γ、p、q是与空间步长、时间步长和介质电磁特性相关的系数。第二个亚时间步计算式与式（1）类似。

在求解方程（1）时，注意到z轴方向上相邻子区域的Ex相互牵连，故可将图1中沿z轴位于同一直线的子区域合并求解。并行对角占优算法（PDD）通过近似处理，简化了子区域间的关联，实现了方程（1）的高效求解。

3 解三对角方程组的PDD算法

将式（1）表示为矩阵形式，对于确定的i、j，有：

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

其中I是单位矩阵，令Z=I+UTA~-1V，Z为五对角矩阵，且可以表示为：

（1）确定当前节点 p对应子区域中网格i、j对应的A(p)和d(p)。

（2）求解方程组：

得到方程的解：

与奇偶规约算法、递归耦合算法等比较，该算法的通信次数和传输信息量均有较大的下降。

4 误差分析

考虑简化情况，设介质相对导磁率μr=1、相对介电常数为 εr=1、导电率 σ=0，则系数

这里，v为电磁波波速，S是Courant因子。对于式（2）的解（11），采用文献[8]的方法，可以导出其解的相对误差：

其中a、b为方程组：

对于预定相对误差上限δ，m和S的选择应位于图2所示对应曲线的上部。

图2 相对误差δ的等值线图

5 MPI实现与效率分析

将子区域的上、下、前、后、左、右六个相邻单元，分别用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）循环；否则，MPI、ADI-FDTD结束。

在假设各个节点任务完全均衡的情况下，可用单个计算节点的效率表示ADI-FDTD算法的效率。对于处理网格数为nx×ny×nz子区域的节点，在一个亚时间步迭代中，运算时间其中te、th分别为一个场点的电场、磁场计算所需时间。设此次计算所需的通信时间开销为Tco，节点的效率可以由η=Tc/(Tc+Tco)表示。在集群系统中，一次通信时间可由tα+tβNB近似表示。这里tα为通信响应时间，tβ为一字节数据的传输时间，NB为传输的字节数，且tα＞＞tβ。可以看出，长消息通信具有更高的通信效率。故可在步骤（2.1）中，先对i、j循环，并存储相应中间结果，实现对的成批传送，获取更高的通信效率。这样，每个电场分量的计算只需要3次通信，共计9次通信，这里将一组发送和接收看作一次通信。在步骤（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所示的不连续带状线。带状线宽b=6 mm，不连续窄口宽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个子区域，则子区域在z方向的网格数m分别为600、150、100、75、50。子区域数为1时，不需用PDD算法，可作为检验PDD算法误差的基准。计算得到观测点的磁场Hz及其相对误差（其中δHz为计算结果相对于基准之差，HM为基准在计算时间内的最大值）如图4所示，从图中的结果看，随着子区域m的减小，误差逐渐增大。

图4 一组m值对应观测点磁场和误差比较

对于m为50、75、100、150，算例的相对误差与式（15）估计值比较如表1所示。在计算误差较小时，算例的误差大于式（15）的估计值是由于截断效应所导致。

表1 m为不同值算例的相对误差与由式（15）估计的相对误差比较（%）

为了检验PDD算法误差随S的变化情况，保持子区域网格数 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个节点的实验系统中完成（每个节点的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。由于算例的计算空间为扁长形，其虚拟拓扑为一维分布，除两端的计算节点外，中间节点均只同前后相邻节点通信，发生通信阻塞的几率很低，所以，表2中的迭代时间几乎与节点数成反比。

表2 不同区域划分的运算时间比较 s

7 结束语

本文将PDD算法引入到并行ADI-FDTD中，减少了基于MPI的MIMD并行系统的处理器间数据通信的开销，提高了计算效率。PDD算法的引入会带来误差，其误差大小与Courant因子S和分割方向的子区域网格数m相关，为保证计算的精度S、m应满足式（15）所限定的条件。对于空间网格数较少的系统，m的限制将会制约计算节点的充分利用，在此情况下，应采用其他方法求解三对角方程组。

与传统FDTD相比，ADI-FDTD的MPI实现，虽然节点间的通信增多，但增大了大时间步长，使迭代次数大为减少，提高了计算效率。

[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）的计算效率，鉴于并行对角占优算法（PDD）求解三对角方程的高效性，引入PDD算法实现了基于MPI的ADI-FDTD的并行计算。通过对运算时间、通信时间的分析，讨论了算法的效率。分析了由于PDD算法的近似处理所引入的计算误差，研究了误差估计与子区域网格数和Courant因子的关系，该研究工作有利于合理选择子区域网格数和Courant因子，进而减小计算误差。最后，通过算例验证了结论的正确性。

隐含变向时域有限差分算法；子区域划分；并行对角占优算法；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.

华中师范大学中央高校基本科研业务研究基金。

吴建斌（1972—），男，博士，副教授，硕士生导师，从事天线和计算电磁学方面的研究；李太全（1961—），男，博士，副教授，从事天线和计算电磁学方面的研究；田茂（1957—），男，博士，教授，博导，从事探地雷达和无线通信方面的研究。E-mail：wujianbin@mail.ccnu.edu.cn

2012-02-20

2012-06-08

1002-8331（2013）23-0195-04