摘 要：应用计算机局域网，采用基于消息传递（MPI）方式和区域分割技术，实现了FDTD的并行计算。以无限长线电流源在自由空间辐射为算例，对并行FDTD算法进行了验证。结果表明并行算法和串行算法计算结果一致，并有效提高了计算效率。最后通过减少通信数据量、优化数据交换方式及通信和计算重叠的方法，使并行算法的数据通信得到优化，并行计算效率明显提高。
关键词：时域有限差分； 区域分割； 并行计算； 数据传递
中图分类号：TN911-34； TP301.6文献标识码：A文章编号：1004-373X(2011)24-0137-04
Implementation for Parallel FDTD Algorithm and Optimization of Data Communication
LIU Zhen1, SONG Zu-xun2, ZHAO Yi-chi1
(1. college of Electronic Engineering, Northwestern Polytechnic University, Xi’an 710129, China;
2. No.365 Institute, Northwestern Polytechnic University, Xi’an 710072, China)
Abstract： The parallel FDTD computation based on message passing interface (MPI) and domain segmentation technology is achieved in a computer local area network. The parallel FDTD algorithm was validated through the example of the free space radiation of the infinite long current source. The result show that the results of serial and parallel algorithms are consistent, and the computing efficiency is improved effectively. The data communication of parallel algorithm was optimized and the parallel efficiency was improved by the reduction of communication data volume, optimization of data exchange mode, overlap of computation and communication.
Keywords： FDTD; domain segmentation; parallel computation; data transmission
0 引 言
1966年K S Yee首次提出了时域有限差分(Finite Difference Time Domain,FDTD)方法，用于电磁场数值计算问题。它的基本思想是将时域麦克斯韦方程的场分量微分式进行差分离散，用差分代替微分进行各场量的迭代。该方法已经在电磁辐射和散射、微波电路分析与设计，电磁兼容等广大领域获得非常成功的应用。
FDTD方法对计算资源的依赖性很强，而随着要求的不断提高，其对计算性能的要求也日益提高，较长的计算时间和较大的存储空间成为了时域有限差分方法在个人计算机系统上处理电大尺寸电磁目标仿真的瓶颈。电大尺寸电磁目标的仿真在通过计算机求解时会消耗非常大的计算机资源。目前，虽然单处理机的性能在飞速发展，计算速度和存储容量也在不断提高，但仍然不能很好地满足要求。本文采用并行FDTD算法来解决这一问题。
FDTD算法本身具有适合开展并行计算的优势。FDTD方法中每一个网格点上的电场(磁场)只与它本身上一时刻的场值和紧邻网格点的磁场(电场)值有关，而与计算区域内其他网格点的场量没有直接关系，因此可以将FDTD计算空间分割成若干个子区域分别进行计算，这一点和并行运算的思路是统一的。本文在典型的机群系统上，通过区域分割来实现了线电流源的自由空间辐射的并行计算，在此基础上，考虑了减少通信数据量，优化数据交换方式和采用计算与通信重叠的方式3种措施来优化通信效率。结果表明并行FDTD方法非常有效的提高了传统FDTD方法的计算效率，经过优化后可明显改善数据通信效率，获得并行效率和加速比进一步的提升。
1 MPI并行计算环境
1.1 并行硬件环境
本文的并行FDTD计算是在一个典型的PC集群（Cluster of PCs，COP）上进行的，这种可扩展并行PC机群是目前比较经济的一种方案，它主要有以下几个显著特点：系统开发周期短，系统价格低，节约系统资源，系统扩展性好。在计算资源成本有限的情况下，本文应用PC机群系统的主要参数为：4个节点，每个节点Intel Pentium4 3.20 GHz CPU,1 GB内存；10/100 Mb/s高速网卡；100 Mb/s交换机。
1.2 并行系统软件环境
实验室采用MPI作为并行开发环境。与PVM和OpenMP等众多并行开发编程环境相比，MPI具有很好的可移植性、强大的可扩展性、易用的信息传递系统以及完备的异步通信功能等许多优点，已经成为国际上的一种并行程序的标准，被越来越多的用户所接受。
其他并行系统软件环境沿用实验室原有的Windows XP操作系统和C++编程语言。
1.3 并行性能评测
并行程序性能的分析由并行算法的加速比以及并行效率来衡量。加速比是指采用多个处理器进行计算时计算速度所能得到加速的倍数。多处理机系统加速比被定义为:S=T1/T
(1)式中T1是使用单一计算机模拟整个问题时所花费的时间；T是使用具有几个处理器的多处理机的执行时间。
并行系统效率被定义为:E=S/n
(2)式中：n是并行计算机系统中参与并行计算的处理器个数。当加速比S接近n时，并行系统效率E接近于1。
2 FDTD并行算法设计
2.1 区域分割
下面以二维TM波为例介绍FDTD并行算法的实现。对于给定的二维计算区域，用（N,M）表示某一子区域，其中N,M分别表示x,y方向上的编号。假设计算区域划分成3×3块，则区域划分及相对应的虚拟进程拓扑如图1所示。
图1 FDTD区域划分及对应的进程4个角顶子区域（1，1），（1，3），（3，1），（3，3）都有2条边界为吸收边界，另外两条边界需要跟其相邻子区域进行数据交换；非角顶边界子区域为（2，1），（1，2），（3，2），（2，3）只有一条边为吸收边界，另外3条边界需要跟其相邻子区域进行数据交换；对于内部的子区域（2，2），则4个边界都需要跟相邻子区域进行数据交换。
2.2 数据交换
将FDTD计算区域划分成多个子区域后，各个子区域内部的场量，按照通常FDTD进行迭代。但在迭代过程中，边界上的电场（磁场）分量需要相邻子区域上前半个时刻的相应的磁场（电场）分量值。二维TM波有Ez，Hx，Hy三个场分量，如图2所示，区域划分时，相邻子域之间有半个网格的重叠区域，其中，灰色区域表示重叠部分。
图2 子区域边界电场和磁场的交换过程FDTD迭代时，沿x方向，子区域（N,M）需要将重叠区域上的切向磁场Hy传递给子区域（N+1,M），同时子区域（N+1,M）需要将重叠区域上的切向电场Ez传递给子区域（N,M）；沿y方向，子区域（N,M）需要将重叠区域上的切向磁场Hx传递给子区域（N,M+1），同时子区域（N,M+1）需要将重叠区域上的切向电场Ez传递给子区域（N,M）。对位于FDTD计算区域边界的子区域，有一个或两个边界为吸收边界，这些边界上没有数据交换。
3 并行FDTD性能测试与分析
以无限长线电流源在自由空间的辐射为仿真算例来对FDTD并行计算性能进行测试和分析，采用二维FDTD计算模式，均匀网格划分。计算条件：二维FDTD计算区域Δx×Δy为1 680×1 680，空间步长为：Δx=Δy=0.01 m,时间步长为：Δt=1.67×10-11 s，迭代步数为：6 000步，激励源为时谐源，电流源幅度为1 A，时谐场频率为0.25 GHz，计算了线电流源在自由空间的辐射电场随距离的衰减。沿x方向进行一维区域分割，分别对1～4个节点机情况下进行仿真测试。如图3所示。
从图3可以看出FDTD并行计算的结果跟串行FDTD的计算结果符合的很好，证明了并行FDTD计算的可行性和正确性。表1给出了并行计算的测试数据。
从表1中可以看出，FDTD的计算耗时随着节点机数量的增加而减少，计算耗时从单机串行的1 512.12 s降低至4台节点机的并行的463.06 s,节省了69%的时间。但同时，从图4中可以看出随着节点机数目的增加，并行计算效率在下降，并行加速因子上升，但上升缓慢。这是因为随着节点机的增多，通信耗时相对于计算耗时的比重逐渐增大，而计算的总量相对不变，因而并行效率逐渐下降。因此，要提高并行计算效率，减少通信耗时很重要。并行计算加速比如图5所示。
4 通信效率优化
并行FDTD各个子区域在每次时间步更新电场（磁场）后，需要将边界上的场量值传递给相邻的子区域，同时接受相邻子区域传送来的边界数据，为下一个时间步内场量的迭代准备。频繁的数据通信对并行计算效率有很大影响，因此必须采取措施来减少数据传送的通信耗时。
4.1 减少需传送数据量
以线电流源在自由空间辐射的FDTD并行计算为例，讨论二维FDTD并行计算中的数据传送量。根据FDTD计算区域的形状，合理的区域分割，可以使传送的数据量最小化。对于N×M的矩形计算区域，划分成4个子区域，若沿x(y)方向一维分割，在一个时间步，若某个子区域的一个边界的一边有相邻子区域，则这个子区域的这个边界在这个时间步内需发送一组数据量：N(M），接收一组数据量：N(M），共有6条这样的边界。这个时间步总共需发送数据量6N(6M)，接收数据量6N(6M)。
若同时沿x,y方向进行二维分割，同理，一个时间步内需要发送数据量为2N+2M，接收数据量为2N+2M。
通过计算比对，选择数据交换最少的一种区域分割方案来减少通信耗时。算例中，划分成4个子区域的情况，二维区域分割传送数据量比一维分割的传送数据量少。通过仿真测试,相对于一维分割方案的463.06 s，二维分割的计算耗时减少到了451.87 s。
4.2 优化数据传送方式
考虑图2和图6所示的两种子区域边界数据交换方式，以二维TM波为例，图2和图6两种数据交换方案每条边界上传递的数据量是一样的，但是需要交换电磁场量不同。图2中Ez，Hx，Hy都需要传递，即在一个时间步中电场递推完后需交换一次电场，然后磁场递推，再交换1次磁场，在一个时间步内，递推过程需中断2次。图6中只需传递Hx，Hy，子区域交界面上的电场切向分量需要在两个子区域中分别计算，虽然子区域交界面上的电场需要计算2次，但是递推过程只被中断1次。通过对两种数据传递方式的仿真，在4个节点的情况下，方式1（图2）耗时451.87 s，方式2（图6）耗时442.375 s。证明方式2的并行计算效率相对方式1要高。
4.3 通信与计算重叠
对于集群计算，有一个很重要的原则就是设法加大计算时间相对于通信时间的比重，减少通信时间。如果能够实现计算与通信的重叠将会更大地提高整个程序的执行效率。在以上优化措施的基础上，采用非阻塞通信的MPI程序设计，使得通信与计算重叠，提高并行效率。并行计算模式如图7所示。在4个节点的情况下，采用非阻塞通信的MPI程序设计，计算耗时为432.671 s。
4.4 优化结果
通过测试，经过以上优化措施，在4个节点的情况下，计算的运行时间由优化前的463.06 s减少到优化后的432.671 s，算法的通信效率得到提高，并行效率从之前的81.79%提升到87.54%，获得了5.75%的性能提升。本文的算例的二维模型，模型的复杂度和通信量都有限，可以预见，以上的优化方法在更复杂的通信模型中有更理想的性能提升。
5 结 语
通过Windows XP操作系统下PC集群的MPI构造了并行FDTD的计算环境，以无限长线电流源在自由空间辐射为算例，对并行FDTD算法进行了验证，计算结果表明了并行FDTD算法和串行计算结果的一致性，并对并行FDTD算法的数据通信进行讨论和优化，优化后并行算法的数据通信效率得到很好的改善，并行性能得到明显地提高。
参 考 文 献
［1］ 葛德彪,闫玉波.电磁波时域有限差分方法［M］.西安：西安电子科技大学出版社，2005.
［2］ 都志辉.高性能计算并行编程技术：MPI并行程序设计 ［M］.北京：清华大学出版社，2001.
［3］ KRAGALOTT M, KLUSKENS M S, PALA W P. Time-domain fields exterior to a two dimensional FDTD space [J ]. IEEE Trans. of Antennas Propagation, 1997, AP-45 (11): 1655-1663.
［4］ 余文华,苏涛,MITTRA R,等.并行时域有限差分 ［M］.北京：中国传媒大学出版社，2005.
［5］ SULLIVAN D M. Electromagnetic simulation using the FDTD method [M ]. New York: IEEE Press, 2000.
［6］ MAHDJOUBI G C K. A parallel FDTD algorithm using the MPI library [J ]. IEEE Antennas and Propagation Magazine, 2001, 43 (2): 94-103.
［7］ 张玉,李斌,梁昌洪.PC集群系统中MPI并行FDTD性能研究［J］.电子学报,2005,33(9):67-69.
［8］ 梁晓冰,田立松,毛均杰.MPI及其在FDTD中的应用［J］.现代电子技术,2005,28(1):94-99.
［9］ CHEW K, FUSCO V. A parallel implementation of the finite difference time domain algorithm [J ]. International journal of Modeling Electronic Networks, Devices and Fields, 1995, 8: 293-299.
［10］ 冯菊,陈星,黄卡玛.MPI环境下FDTD高效率网络并行计算研究［J］.淮阴师范学院学报,2005(1):57-61.
作者简介: 刘 真 男，1985年出生，湖北人，硕士研究生。主要研究方向为电磁场FDTD数值方法的并行计算。
宋祖勋 男，1964年出生，研究员。主要研究方向为电磁兼容和电磁仿真。
赵羿池 女，1985年出生，硕士研究生。主要研究方向为电磁兼容。