论文部分内容阅读
摘要： 为了构建适合于时域有限差分法求解的离散几何模型，摆脱大量繁杂的手工操作，提出了一种高效的大规模并行时域有限差分法网格自动剖分技术.该并行剖分方法将三角面元计算机辅助设计模型文件作为输入数据，能够自动建立包含多种介质的任意三维实体网格模型，且其并行执行过程中无需过多的数据交换，并行效率可达99%.基于该离散模型自动生成技术，采用时域有限差分方法，计算了含微带板的简易计算机机箱耦合效应，其计算结果与商用电磁仿真软件的计算结果相吻合，表明该剖分方法的准确性.最后，通过250个处理器核，并行剖分了网格规模约6亿的某真实计算机机箱模型，其并行剖分时间仅为0.2 s，验证了该并行剖分方法的高效性，表明该网格剖分技术能有效地解决大规模并行时域有限差分法的离散几何建模问题.
关键词： 时域有限差分法；网格剖分；并行计算；计算机辅助设计
中图分类号： O441.4文献标志码： ACartesian Mesh Generator for Parallel
FiniteDifference TimeDomain MethodCHEN Linglu1，ZHOU Haijing2，LI Hanyu2，FU Haijun1，3，LIAO Cheng1
（1. Institute of Electromagnetics， Southwest Jiaotong University， Chengdu 610031， China； 2. Institute of Applied Physics and Computational Mathematics， Beijing 100094， China； 3. Beijing Institute of Electronic System Engineering， Beijing 100854， China）
Abstract：In order to generate discrete geometricmodel that can be solved by the finitedifference timedomain （FDTD） method， and avoid complicated manual operations， an efficient parallel mesh generation technique for massively parallel FDTD simulation was presented. The parallel mesh generator is capable of dissecting arbitrary 3D multimaterial models， with trianglefacet computer aided design files as input data. Without the need for excessive data communication between the processors， its parallel efficiency was close to 100% in the test. The coupling effect of a simple computer case with a microstrip board was simulated by the FDTD method， based on this mesh generator. The results by the FDTD coincided with the ones calculated by the commercial electromagnetic simulation software， demonstrating the correctness of this mesh dissection method. Finally， when dissecting a real computer case with 250 processors and the grid number of 0.6 billion， the CPU time was only about 0.2 s. This efficient mesh dissection indicates that the proposed parallel mesh generation technique can efficiently solve the modeling in massively parallel FDTD simulation.
Key words：finitedifference timedomain （FDTD）； mesh generation； parallelization； computer aided design （CAD）
时域有限差分法（finite difference time domain， FDTD）是一种简单、灵活的电磁仿真算法，且其易于并行，现已被各界广泛应用与发展[15].为了使FDTD仿真算法走向实用化，高效的自动几何建模方法是必不可少的，这在大规模并行FDTD方法的运用中尤为必要.近年来，越来越多的学者基于计算机辅助设计（computer aided design， CAD）研究FDTD离散几何建模方法.如文献[6]对AutoCAD软件进行二次开发，实现三维实体的FDTD网格自动剖分；本文作者又对这种方法提出了补充和改进[7].但这种方法的剖分过程是在AutoCAD软件环境下进行的，因此其剖分效果受到AutoCAD软件的限制，且不易并行化.Y. Srisukh等则提出了一种可以将三角面元数据转换为可用于FDTD方法计算的六面体网格模型的射线追踪方法[8]；之后Jeff T. MacGillivray利用该方法在一个单核工作站上完成了网格规模为1万亿的FDTD电磁目标建模，但其剖分时间长达10 h[9]；此外，与之类似的还有文献[10]提出的投影求交方法等.虽然上述方法都具有较好的鲁棒性，但需要花费较多的时间进行求交以及排序运算.为了进一步提高FDTD自动几何建模的效率，本文将原铸造业所采用的切片线扫描法[11]引入到电磁几何建模中，可最小化求交和排序运算.然后，基于并行自适应结构网格应用支撑软件框架（J parallel adaptive structured mesh applications infrastructure， JASMIN）实现了剖分算法的并行化，以解决单台计算机内存受限的问题，并加快网格剖分速度.该方法适合于处理结构复杂，网格规模大的大规模并行FDTD仿真计算问题.西南交通大学学报第48卷第4期陈伶璐等：并行时域有限差分法网格自动剖分技术1基于FDTD的网格自动剖分算法及其并行化实现1.1三角面元CAD数据文件及介质识别方法三角面元CAD数据文件所存储的模型信息类似于有限元网格划分，以三角面片来拟合逼近实体模型的表面轮廓特征.由于两个不同三角形的3个顶点坐标不可能完全相同，因此，只需给出各个三角形的顶点坐标，模型的形状也就可以完全确定了.STL （stereolithography）格式文件是一种标准的三角面元CAD数据文件[12]，几乎所有的CAD系统都提供了STL格式文件的输入、输出接口，如Solid Work、Pro/E、Auto CAD等，且当下一些主流的电磁仿真软件也都提供了它的输入、输出接口，如CST、HFSS等.根据数据储存形式的不同，STL格式文件可以分为二进制码和ASCII码两种形式.相较于二进制码存储形式，ASCII码形式具有更强的可读性.如图1所示，采用ASCII码存储形式的STL格式文件以“solid component”、“facet normal”、“outer loop”等关键词来区分各种数据的意义.各个实体的信息以“solid”为开头，以“endsolid”为结束；单个实体段中，每个三角形的信息以“facet”为开头，以“endfacet”为结束；法向矢量以“normal”为引导；顶点信息以“outerloop”为开头，以“endloop”为结束；每个顶点的坐标以“vertex”为引导，每个顶点有x、y、z 3个坐标值.本文所研究的网格自动剖分算法以这种ASCII码形式的STL格式文件作为输入数据，具有很好的通用性. solid component1：facet normal outer loopvertex vertex vertex endloopendfacet…endsolid component1：
图1STL格式文件的ASCII码存储形式
Fig.1An example of an ASCII STL file
由图1可知，STL格式文件只保存有实体的名称、每个三角形的法向矢量和顶点坐标这3类信息，并不包含实体模型的介质信息.因此，本文通过预先设定的命名规则对各实体进行命名，以实体名来识别不同实体的介质信息.例如，为“002_solid1”时，“002”为介质编号（如：“002”代表铜），“solid1”为自定义的实体名称.本文所有STL格式文件由商用软件CST导出，在CST几何建模平台中，即可对各实体按上述命名规则进行命名.1.2FDTD网格自动剖分算法本文研究的网格自动剖分算法先以切片的形式得到实体各切割平面的封闭轮廓，再利用线扫描的方法判断空间中各网格的具体属性.图2展示了一中空立方体的网格剖分过程，其中图2（b）为该中空立方体的三角面元形式.在剖分前，预先设X、Y、Z方向的剖分间距分别为Δx、 Δy 和 Δz，根据FDTD算法的要求，剖分间距应小于λ/12[13]，其中λ为FDTD仿真的最小波长.具体剖分步骤如下：
步骤1选取某个坐标平面（如XOY面）为基准面，再以平行于基准面的切割平面z=（k+1/2）Δz对实体进行切割，其中k为代表第k个切割平面的整数.描述实体表面轮廓的三角面元将与切割平面相交而产生交线.这样，在切割平面上就可得到一个由若干线段首尾相接而组成的封闭环，如图2（c）所示.
步骤2在切割平面上以直线y=（j+1/2）Δy（其中，j为整数，代表第j条扫描线）对该平面进行线扫描.这些扫描线将可能与封闭环相交，如图2（d）所示.
步骤3将扫描线与封闭环的交点按顺序编号为1，2，…，n，并按“奇数偶数”配对，如奇数交点1和偶数交点2为一组，奇数交点3和偶数交点4为一组，以此类推，如图2（e）中粗实线所示，则可以判断奇数交点与偶数交点之间的区域为实体内部区域.
步骤4以直线x=（i+1/2）Δx（其中，i为整数，代表第i条扫描线）扫描上述“奇偶”配对的直线，如图2（f）所示，其交点皆位于FDTD的六面体网格中心，判定这些网格的属性为实体.
（a） 中空立方体模型（b） 中空立方体的三角面元形式示例：z=3.5（c） 切割平面 z=（k+1/2）Δz（d） 扫描线y=（j+1/2）Δy（e） 交点编号和“奇偶”配对（f） 扫描线 x=（i+1/2）Δx图2网格剖分过程示意
Fig.2Mesh dissection process步骤5重复上述步骤，直到全计算空间被切割扫描完毕.
当剖分目标为多实体组成的多介质模型时，则需要对每个实体重复上述步骤.
在网格剖分过程中，需要注意对奇异点的处理.奇异点是指切割平面或扫描线与三角面元的特殊交点.这些奇异点大致可分为2类：第1类是在用切割平面对实体进行切割时，切割平面与三角面元位于同一平面或只过三角面元其中1个顶点而产生的，这种情况将导致切割平面与某三角面元有3个或1个交点，而非1段交线；第2类是在对切割平面进行线扫描时，扫描线只过封闭环某顶点而产生的，这种情况将导致扫描线与封闭环的交点为奇数，不利于程序对网格属性的判断.为使程序顺利执行，当出现上述情形时，本文将切割平面或扫描线略微偏移一个小量，以避开奇异点的产生.此外，须使切割平面的偏移方向与三角面元外法线方向相反，以确保切割平面偏移后仍与实体相交.1.3网格自动剖分算法的并行化实现本文所提出的FDTD网格自动剖分算法的并行化是在JASMIN框架下实现的.JASMIN框架是一个基于消息传递接口库 （message passing interface， MPI）的并行框架，可支持数万至数十万处理器核的大规模并行计算[14].
基于JASMIN框架下“块网格片层次结构网格层网格片”的并行区域分解策略，将全计算空间分解为若干个子计算空间，令每个网格片只负责处理其中一个子空间.各子计算空间在获得STL模型文件数据后，在该子空间内独立地执行网格自动剖分程序，并只对处于该子空间内的实体目标进行网格剖分.由于本文所提出的网格自动剖分算法在并行剖分过程中并不需要进行MPI通信，即无需数据交互，而是直接将剖分后的离散网格模型用于并行FDTD仿真，因此，这种网格自动剖分算法的并行效率是近乎100%的.
除网格自动剖分算法其本身的高效性外，如何使各进程快速获得STL模型文件数据也是影响网格剖分效率的关键因素.最简单易行的获取方式为“各处理器并行读取”，即所有处理器同时读取目标文件.然而，随着待剖分模型复杂程度的增加，STL模型文件的数据量也将增大，所用处理器核的数量也将增多.这将导致在程序运行的初始阶段，系统的I/O节点负载迅速增大，且在I/O的负载平衡方面也将难以控制，即，若采用上万处理器核并行读取一个25 MB大小的STL模型文件，仅读取文件的时间将长达十几分钟.因此，这种“各处理器并行读取”的方式并不适用于所有情况.另一种获取方式为仅由主进程读取目标文件，然后经关键词识别，保留有用信息，再广播给其他进程.本文所用的STL模型文件最大约25 MB，而其有用信息仅为KB量级，经关键词识别后广播有用信息可很大程度地减少系统的I/O节点负载，降低程序对硬件设备的要求.采用这种方式获取一个25 MB大小的STL模型文件数据，时间为秒级.因此，本文采用由主进程读取，再广播给其他进程的方式来实现STL模型文件的快速读取.2数值算例计算机机箱的电磁耦合效应研究一直是电磁兼容、干扰和防护等领域的重要课题[15]，而计算机机箱复杂结构的精确几何建模也是对其进行仿真分析的难点之一.本文将基于并行FDTD网格自动剖分技术对含微带板的简易计算机机箱模型和某真实计算机机箱进行建模仿真，用以验证所提出的并行网格自动剖分算法的准确性和高效性.2.1简易计算机机箱模型网格剖分简易计算机机箱模型如图3所示，在主板位置放置一个两端开路的微带板，该简易计算机模型尺寸为170 mm×420 mm×430 mm.为设置激励源和边界条件，所取计算空间将大于机箱模型尺寸，统一取260 mm×520 mm×520 mm.在一个4核4 GB 2.13 GHz Intel Xeon Linux工作站上计算该算例. 图3带微带板的简易计算机机箱模型
Fig.3Simple computer case with microstrip board
表1给出了不同网格规模和处理器核数量的简易计算机机箱模型剖分时间.需要指出的是，当空间步长取值为Δx=Δy=Δz=0.1 mm 时，所对应的网格规模约为700亿（2 600×5 200×5 200），已经超出了该工作站4 GB的内存限制，因此，这里的网格剖分数据并未被保存，只作观察并行效率用.并行效率[16]的定义为
E（q）=Ts/（Tqq），（1）
式中：Ts为串行执行时间；q为使用的处理器核数；Tq为使用q个处理器核并行执行的时间.
表1简易计算机机箱网格剖分CPU运行时间
Tab.1CPU time of the simple computer case mesh dissection
计算空间网格规模处理器核CPU运行时间/s260 mm×520 mm×520 mm130×260×26010.701 6092 600×5 200×5 20011 161.1292581.3064291.331
从表1可以看出，采用并行网格自动剖分算法可以大大缩减网格剖分所占用的CPU运行时间.对于网格量约700亿规模的计算机机箱模型，采用2个处理器核和4个处理器核剖分的并行效率分别为99.87%和99.64%.
由于该算例计算机机箱结构相对简单，当空间步长取值为Δx=Δy=Δz=2 mm时，即可满足FDTD程序[17]的仿真精度要求，此时网格规模约900万（130×260×260）.激励信号为一高斯脉冲，设脉宽为0.2 ns，时延为0.16 ns，幅值为1 kV/m.入射波为正面垂直入射的垂直极化平面波.以计算机正面细缝内侧中心（130 mm，312 mm，47 mm）、计算机机箱中心（130 mm，260 mm，260 mm）和主板中心（62 mm，262 mm，366 mm）为观察点，对比FDTD程序和CST微波工作室时域求解器的仿真结果.如图4～6所示，两者的计算结果几乎完全吻合，由此验证了该网格自动剖分算法能准确地将三角面元CAD模型文件数据转换为FDTD程序可用的六面体网格模型.
图4简易计算机机箱正面细缝中点
电场强度时域图
Fig.4Electric field in the middle of the silt located
on the front of simple computer case图5简易计算机机箱中心点电场强度时域图
Fig.5Electric field at the center of
simple computer case图6主板中心点电场强度时域图
Fig.6Electric field at the center of motherboard
2.2真实计算机机箱网格剖分某真实计算机机箱模型如图7所示，机箱物理尺寸为250 mm×500 mm×550 mm，箱体表面遍布各种形状的散热孔，机箱背部有三芯电源线，机箱内有复位线、主板（以介质敷铜板替代）.在曙光5 000高性能计算机上通过并行FDTD程序计算该真实计算机机箱的电磁耦合效应.空间步长取值为Δx=Δy=Δz=0.5 mm，所对应的网格规模约为6亿（520×1 020×1 120）.
（a） 实物图（b） FDTD网格模型图7某真实计算机机箱
Fig.7A real computer case表2给出了该真实计算机机箱模型的网格剖分时间，在250个处理器核并行剖分的条件下，CPU运行时间仅为0.2 s.FDTD程序的激励设置与2.1节相同.
表2某真实计算机机箱网格剖分CPU运行时间
Tab.2CPU time for the mesh dissection of the real computer case
计算空间网格规模处理器核/个CPU运行时间/s260 mm×510 mm×560 mm520×1 020×1 1202500.203 658
图8为该计算机机箱中心点处的时域电场强度曲线.该算例表明了本文提出的并行FDTD网格自动剖分方法的高效性.
图8某真实计算机机箱中心点电场强度时域图
Fig.8Electric field at the center point of
the real computer case3结论本文提出了一种基于大规模并行FDTD的网格自动剖分方法，可以将包含多种介质的任意三维实体快速、准确地离散为适用于FDTD计算的六面体网格结构.由于并行剖分过程不需要进行MPI通信，剖分算法的并行效率可达99%.简易计算机机箱模型的FDTD仿真结果和CST软件计算结果的对比，验证了该剖分方法的准确性.以250个处理器核耗时仅0.2 s完成约6亿网格规模的某真实计算机机箱网格剖分，表明了该并行剖分方法的高效性.这种以三角面元CAD数据文件作为输入数据的网格自动剖分算法对于大规模并行FDTD的离散化网格建模是十分有效的.参考文献：[1]YEE K S. Numerical solution of initial boundary value problems involving Maxwells equations in isotropic media[J]. IEEE Transactions on Antennas and Propagation， 1966， 14（3）： 302307.
[2]WATANABE Y， IGARASHI H. Accelerated FDTD analysis of antennas loaded by electric circuits[J]. IEEE Transactions on Antennas and Propagation， 2012， 60（2）： 958963. [3]杨丹，方剑，廖成，等. PML吸收边界条件在孔缝耦合模拟中的应用[J]. 西南交通大学学报，2005，40（1）： 108112.
YANG Dan， FANG Jian， LIAO Cheng， et al. Application of PML absorbing boundary condition in numerical simulation of pulses coupling into slot[J]. Journal of Southwest Jiaotong University， 2005， 40（1）： 108112.
[4]钟选明，廖成. 基于时间反演和单站天线的导体目标微波成像[J]. 西南交通大学学报，2011，46（3）： 451455.
ZHONG Xuanming， LIAO Cheng. Microwave imaging of perfectly conducting cylinder based on time reversal and single antenna[J]. Journal of Southwest Jiaotong University， 2011， 46（3）： 451455.
[5]廖成，卫涛，陈伟. 整数微分进化策略及其在微波成像中的应用[J]. 西南交通大学学报，2007，42（6）： 647652.
LIAO Cheng， WEI Tao， CHENG Wei. Integer coded differential evolution strategy and application to microwave imaging[J]. Journal of Southwest Jiaotong University， 2007， 42（6）： 647652.
[6]张秋菊，王秉中. 时域有限差分法电磁仿真的网格自动剖分[J]. 电子科技大学学报，2007，36（1）： 6669.
ZHANG Qiuju， WANG Bingzhong. Auto dissection of entity with grid for FDTD[J]. Electromagnetic Simulation Journal of University of Electronic Science and Technology of China， 2007， 36（1）： 6669.
[7]CHEN Linglu. Auto dissection of entity with threedimensional network based on FDTD[C]∥2010 AsiaPacific Symposium on Electromagnetic Compatibility. Beijing： IEEE Press， 2010： 920923.
[8]SRISUKH Y， NEHRBASS J， TEIXEIRA F L， et al. An approach for automatic grid generation in threedimensional FDTD simulations of complex geometries[J]. IEEE Transactions on Antennas and Propagation， 2002， 44（4）： 7580.
[9]MACGILLIVRAY J T. Trillion cell CADbased cartesian mesh generator for the finitedifference timedomain method on a singleprocessor 4GB workstation[J]. IEEE Transactions on Antennas and Propagation， 2008， 56（8）： 21872190.
[10]杨丽霞，葛德彪，白剑，等. 三角面元数据模型FDTD网格生成技术[J]. 西安电子科技大学学报，2007，34（2）： 208302.
YANG Lixia， GE Debiao， BAI Jian， et al. A novel FDTD modeling technique based on triangle meshunits of an object[J]. Journal of Xidian University， 2007， 34（2）： 208302.
[11]梁英业，戴挺，赵建新，等. 基于STL的切片线扫描法网格剖分技术[J]. 铸造，2005，54（10）： 10021005.
LIANG Yingye， DAI Ting， ZHAO Jianxin， et al. Mesh generation using a slice line scanning method based on STL files[J]. Foundry， 2005， 54（10）： 10021005.
[12]ITO Y， NAKAHASHI K. Surface triangulation for polygonal models based on CAD data[J]. International Journal for Numerical Methods in Fluids， 2002， 39（1）： 7596.
[13]葛德彪，闫玉波. 电磁波时域有限差分方法[M]. 2版. 西安：西安电子科技大学出版社，2005： 3839.
[14]莫则尧，张爱清. 并行自适应结构网格应用支撑软件框架[R]. 北京：北京应用物理与计算数学研究所，2009： 317.
[15]廖成，杨丹，方剑. 不同极化方向电磁脉冲作用于计算机机箱的效应分析[J]. 微波学报，2007，23（4）： 2831.
LIAO Cheng， YANG Dan， FANG Jian. Numerical analysis for EMP having different polarization direction coupling to a computer case[J]. Journal of Microwaves， 2007， 23（4）： 2831.
[16]喻炜，颜宏，金之雁. 并行效率的初步研究[J]. 应用气象学报，1996，7（1）： 6168.
YU Wei， YAN Hong， JIN Zhiyan. The preliminary study on the efficiency of parallel model computation[J]. Quarterly Journal of Applied Meteorology， 1996， 7（1）： 6168.
[17]CHANG Lei. Parallel FDTD analysis of largescale ridged TEM horn antenna array[C]∥2009 International Conference on Microwave Technology and Computational Electromagnetics. Chengdu： IEEE Press， 2009： 344347.
关键词： 时域有限差分法；网格剖分；并行计算；计算机辅助设计
中图分类号： O441.4文献标志码： ACartesian Mesh Generator for Parallel
FiniteDifference TimeDomain MethodCHEN Linglu1，ZHOU Haijing2，LI Hanyu2，FU Haijun1，3，LIAO Cheng1
（1. Institute of Electromagnetics， Southwest Jiaotong University， Chengdu 610031， China； 2. Institute of Applied Physics and Computational Mathematics， Beijing 100094， China； 3. Beijing Institute of Electronic System Engineering， Beijing 100854， China）
Abstract：In order to generate discrete geometricmodel that can be solved by the finitedifference timedomain （FDTD） method， and avoid complicated manual operations， an efficient parallel mesh generation technique for massively parallel FDTD simulation was presented. The parallel mesh generator is capable of dissecting arbitrary 3D multimaterial models， with trianglefacet computer aided design files as input data. Without the need for excessive data communication between the processors， its parallel efficiency was close to 100% in the test. The coupling effect of a simple computer case with a microstrip board was simulated by the FDTD method， based on this mesh generator. The results by the FDTD coincided with the ones calculated by the commercial electromagnetic simulation software， demonstrating the correctness of this mesh dissection method. Finally， when dissecting a real computer case with 250 processors and the grid number of 0.6 billion， the CPU time was only about 0.2 s. This efficient mesh dissection indicates that the proposed parallel mesh generation technique can efficiently solve the modeling in massively parallel FDTD simulation.
Key words：finitedifference timedomain （FDTD）； mesh generation； parallelization； computer aided design （CAD）
时域有限差分法（finite difference time domain， FDTD）是一种简单、灵活的电磁仿真算法，且其易于并行，现已被各界广泛应用与发展[15].为了使FDTD仿真算法走向实用化，高效的自动几何建模方法是必不可少的，这在大规模并行FDTD方法的运用中尤为必要.近年来，越来越多的学者基于计算机辅助设计（computer aided design， CAD）研究FDTD离散几何建模方法.如文献[6]对AutoCAD软件进行二次开发，实现三维实体的FDTD网格自动剖分；本文作者又对这种方法提出了补充和改进[7].但这种方法的剖分过程是在AutoCAD软件环境下进行的，因此其剖分效果受到AutoCAD软件的限制，且不易并行化.Y. Srisukh等则提出了一种可以将三角面元数据转换为可用于FDTD方法计算的六面体网格模型的射线追踪方法[8]；之后Jeff T. MacGillivray利用该方法在一个单核工作站上完成了网格规模为1万亿的FDTD电磁目标建模，但其剖分时间长达10 h[9]；此外，与之类似的还有文献[10]提出的投影求交方法等.虽然上述方法都具有较好的鲁棒性，但需要花费较多的时间进行求交以及排序运算.为了进一步提高FDTD自动几何建模的效率，本文将原铸造业所采用的切片线扫描法[11]引入到电磁几何建模中，可最小化求交和排序运算.然后，基于并行自适应结构网格应用支撑软件框架（J parallel adaptive structured mesh applications infrastructure， JASMIN）实现了剖分算法的并行化，以解决单台计算机内存受限的问题，并加快网格剖分速度.该方法适合于处理结构复杂，网格规模大的大规模并行FDTD仿真计算问题.西南交通大学学报第48卷第4期陈伶璐等：并行时域有限差分法网格自动剖分技术1基于FDTD的网格自动剖分算法及其并行化实现1.1三角面元CAD数据文件及介质识别方法三角面元CAD数据文件所存储的模型信息类似于有限元网格划分，以三角面片来拟合逼近实体模型的表面轮廓特征.由于两个不同三角形的3个顶点坐标不可能完全相同，因此，只需给出各个三角形的顶点坐标，模型的形状也就可以完全确定了.STL （stereolithography）格式文件是一种标准的三角面元CAD数据文件[12]，几乎所有的CAD系统都提供了STL格式文件的输入、输出接口，如Solid Work、Pro/E、Auto CAD等，且当下一些主流的电磁仿真软件也都提供了它的输入、输出接口，如CST、HFSS等.根据数据储存形式的不同，STL格式文件可以分为二进制码和ASCII码两种形式.相较于二进制码存储形式，ASCII码形式具有更强的可读性.如图1所示，采用ASCII码存储形式的STL格式文件以“solid component”、“facet normal”、“outer loop”等关键词来区分各种数据的意义.各个实体的信息以“solid”为开头，以“endsolid”为结束；单个实体段中，每个三角形的信息以“facet”为开头，以“endfacet”为结束；法向矢量以“normal”为引导；顶点信息以“outerloop”为开头，以“endloop”为结束；每个顶点的坐标以“vertex”为引导，每个顶点有x、y、z 3个坐标值.本文所研究的网格自动剖分算法以这种ASCII码形式的STL格式文件作为输入数据，具有很好的通用性. solid component1：
图1STL格式文件的ASCII码存储形式
Fig.1An example of an ASCII STL file
由图1可知，STL格式文件只保存有实体的名称、每个三角形的法向矢量和顶点坐标这3类信息，并不包含实体模型的介质信息.因此，本文通过预先设定的命名规则对各实体进行命名，以实体名
步骤1选取某个坐标平面（如XOY面）为基准面，再以平行于基准面的切割平面z=（k+1/2）Δz对实体进行切割，其中k为代表第k个切割平面的整数.描述实体表面轮廓的三角面元将与切割平面相交而产生交线.这样，在切割平面上就可得到一个由若干线段首尾相接而组成的封闭环，如图2（c）所示.
步骤2在切割平面上以直线y=（j+1/2）Δy（其中，j为整数，代表第j条扫描线）对该平面进行线扫描.这些扫描线将可能与封闭环相交，如图2（d）所示.
步骤3将扫描线与封闭环的交点按顺序编号为1，2，…，n，并按“奇数偶数”配对，如奇数交点1和偶数交点2为一组，奇数交点3和偶数交点4为一组，以此类推，如图2（e）中粗实线所示，则可以判断奇数交点与偶数交点之间的区域为实体内部区域.
步骤4以直线x=（i+1/2）Δx（其中，i为整数，代表第i条扫描线）扫描上述“奇偶”配对的直线，如图2（f）所示，其交点皆位于FDTD的六面体网格中心，判定这些网格的属性为实体.
（a） 中空立方体模型（b） 中空立方体的三角面元形式示例：z=3.5（c） 切割平面 z=（k+1/2）Δz（d） 扫描线y=（j+1/2）Δy（e） 交点编号和“奇偶”配对（f） 扫描线 x=（i+1/2）Δx图2网格剖分过程示意
Fig.2Mesh dissection process步骤5重复上述步骤，直到全计算空间被切割扫描完毕.
当剖分目标为多实体组成的多介质模型时，则需要对每个实体重复上述步骤.
在网格剖分过程中，需要注意对奇异点的处理.奇异点是指切割平面或扫描线与三角面元的特殊交点.这些奇异点大致可分为2类：第1类是在用切割平面对实体进行切割时，切割平面与三角面元位于同一平面或只过三角面元其中1个顶点而产生的，这种情况将导致切割平面与某三角面元有3个或1个交点，而非1段交线；第2类是在对切割平面进行线扫描时，扫描线只过封闭环某顶点而产生的，这种情况将导致扫描线与封闭环的交点为奇数，不利于程序对网格属性的判断.为使程序顺利执行，当出现上述情形时，本文将切割平面或扫描线略微偏移一个小量，以避开奇异点的产生.此外，须使切割平面的偏移方向与三角面元外法线方向相反，以确保切割平面偏移后仍与实体相交.1.3网格自动剖分算法的并行化实现本文所提出的FDTD网格自动剖分算法的并行化是在JASMIN框架下实现的.JASMIN框架是一个基于消息传递接口库 （message passing interface， MPI）的并行框架，可支持数万至数十万处理器核的大规模并行计算[14].
基于JASMIN框架下“块网格片层次结构网格层网格片”的并行区域分解策略，将全计算空间分解为若干个子计算空间，令每个网格片只负责处理其中一个子空间.各子计算空间在获得STL模型文件数据后，在该子空间内独立地执行网格自动剖分程序，并只对处于该子空间内的实体目标进行网格剖分.由于本文所提出的网格自动剖分算法在并行剖分过程中并不需要进行MPI通信，即无需数据交互，而是直接将剖分后的离散网格模型用于并行FDTD仿真，因此，这种网格自动剖分算法的并行效率是近乎100%的.
除网格自动剖分算法其本身的高效性外，如何使各进程快速获得STL模型文件数据也是影响网格剖分效率的关键因素.最简单易行的获取方式为“各处理器并行读取”，即所有处理器同时读取目标文件.然而，随着待剖分模型复杂程度的增加，STL模型文件的数据量也将增大，所用处理器核的数量也将增多.这将导致在程序运行的初始阶段，系统的I/O节点负载迅速增大，且在I/O的负载平衡方面也将难以控制，即，若采用上万处理器核并行读取一个25 MB大小的STL模型文件，仅读取文件的时间将长达十几分钟.因此，这种“各处理器并行读取”的方式并不适用于所有情况.另一种获取方式为仅由主进程读取目标文件，然后经关键词识别，保留有用信息，再广播给其他进程.本文所用的STL模型文件最大约25 MB，而其有用信息仅为KB量级，经关键词识别后广播有用信息可很大程度地减少系统的I/O节点负载，降低程序对硬件设备的要求.采用这种方式获取一个25 MB大小的STL模型文件数据，时间为秒级.因此，本文采用由主进程读取，再广播给其他进程的方式来实现STL模型文件的快速读取.2数值算例计算机机箱的电磁耦合效应研究一直是电磁兼容、干扰和防护等领域的重要课题[15]，而计算机机箱复杂结构的精确几何建模也是对其进行仿真分析的难点之一.本文将基于并行FDTD网格自动剖分技术对含微带板的简易计算机机箱模型和某真实计算机机箱进行建模仿真，用以验证所提出的并行网格自动剖分算法的准确性和高效性.2.1简易计算机机箱模型网格剖分简易计算机机箱模型如图3所示，在主板位置放置一个两端开路的微带板，该简易计算机模型尺寸为170 mm×420 mm×430 mm.为设置激励源和边界条件，所取计算空间将大于机箱模型尺寸，统一取260 mm×520 mm×520 mm.在一个4核4 GB 2.13 GHz Intel Xeon Linux工作站上计算该算例. 图3带微带板的简易计算机机箱模型
Fig.3Simple computer case with microstrip board
表1给出了不同网格规模和处理器核数量的简易计算机机箱模型剖分时间.需要指出的是，当空间步长取值为Δx=Δy=Δz=0.1 mm 时，所对应的网格规模约为700亿（2 600×5 200×5 200），已经超出了该工作站4 GB的内存限制，因此，这里的网格剖分数据并未被保存，只作观察并行效率用.并行效率[16]的定义为
E（q）=Ts/（Tqq），（1）
式中：Ts为串行执行时间；q为使用的处理器核数；Tq为使用q个处理器核并行执行的时间.
表1简易计算机机箱网格剖分CPU运行时间
Tab.1CPU time of the simple computer case mesh dissection
计算空间网格规模处理器核CPU运行时间/s260 mm×520 mm×520 mm130×260×26010.701 6092 600×5 200×5 20011 161.1292581.3064291.331
从表1可以看出，采用并行网格自动剖分算法可以大大缩减网格剖分所占用的CPU运行时间.对于网格量约700亿规模的计算机机箱模型，采用2个处理器核和4个处理器核剖分的并行效率分别为99.87%和99.64%.
由于该算例计算机机箱结构相对简单，当空间步长取值为Δx=Δy=Δz=2 mm时，即可满足FDTD程序[17]的仿真精度要求，此时网格规模约900万（130×260×260）.激励信号为一高斯脉冲，设脉宽为0.2 ns，时延为0.16 ns，幅值为1 kV/m.入射波为正面垂直入射的垂直极化平面波.以计算机正面细缝内侧中心（130 mm，312 mm，47 mm）、计算机机箱中心（130 mm，260 mm，260 mm）和主板中心（62 mm，262 mm，366 mm）为观察点，对比FDTD程序和CST微波工作室时域求解器的仿真结果.如图4～6所示，两者的计算结果几乎完全吻合，由此验证了该网格自动剖分算法能准确地将三角面元CAD模型文件数据转换为FDTD程序可用的六面体网格模型.
图4简易计算机机箱正面细缝中点
电场强度时域图
Fig.4Electric field in the middle of the silt located
on the front of simple computer case图5简易计算机机箱中心点电场强度时域图
Fig.5Electric field at the center of
simple computer case图6主板中心点电场强度时域图
Fig.6Electric field at the center of motherboard
2.2真实计算机机箱网格剖分某真实计算机机箱模型如图7所示，机箱物理尺寸为250 mm×500 mm×550 mm，箱体表面遍布各种形状的散热孔，机箱背部有三芯电源线，机箱内有复位线、主板（以介质敷铜板替代）.在曙光5 000高性能计算机上通过并行FDTD程序计算该真实计算机机箱的电磁耦合效应.空间步长取值为Δx=Δy=Δz=0.5 mm，所对应的网格规模约为6亿（520×1 020×1 120）.
（a） 实物图（b） FDTD网格模型图7某真实计算机机箱
Fig.7A real computer case表2给出了该真实计算机机箱模型的网格剖分时间，在250个处理器核并行剖分的条件下，CPU运行时间仅为0.2 s.FDTD程序的激励设置与2.1节相同.
表2某真实计算机机箱网格剖分CPU运行时间
Tab.2CPU time for the mesh dissection of the real computer case
计算空间网格规模处理器核/个CPU运行时间/s260 mm×510 mm×560 mm520×1 020×1 1202500.203 658
图8为该计算机机箱中心点处的时域电场强度曲线.该算例表明了本文提出的并行FDTD网格自动剖分方法的高效性.
图8某真实计算机机箱中心点电场强度时域图
Fig.8Electric field at the center point of
the real computer case3结论本文提出了一种基于大规模并行FDTD的网格自动剖分方法，可以将包含多种介质的任意三维实体快速、准确地离散为适用于FDTD计算的六面体网格结构.由于并行剖分过程不需要进行MPI通信，剖分算法的并行效率可达99%.简易计算机机箱模型的FDTD仿真结果和CST软件计算结果的对比，验证了该剖分方法的准确性.以250个处理器核耗时仅0.2 s完成约6亿网格规模的某真实计算机机箱网格剖分，表明了该并行剖分方法的高效性.这种以三角面元CAD数据文件作为输入数据的网格自动剖分算法对于大规模并行FDTD的离散化网格建模是十分有效的.参考文献：[1]YEE K S. Numerical solution of initial boundary value problems involving Maxwells equations in isotropic media[J]. IEEE Transactions on Antennas and Propagation， 1966， 14（3）： 302307.
[2]WATANABE Y， IGARASHI H. Accelerated FDTD analysis of antennas loaded by electric circuits[J]. IEEE Transactions on Antennas and Propagation， 2012， 60（2）： 958963. [3]杨丹，方剑，廖成，等. PML吸收边界条件在孔缝耦合模拟中的应用[J]. 西南交通大学学报，2005，40（1）： 108112.
YANG Dan， FANG Jian， LIAO Cheng， et al. Application of PML absorbing boundary condition in numerical simulation of pulses coupling into slot[J]. Journal of Southwest Jiaotong University， 2005， 40（1）： 108112.
[4]钟选明，廖成. 基于时间反演和单站天线的导体目标微波成像[J]. 西南交通大学学报，2011，46（3）： 451455.
ZHONG Xuanming， LIAO Cheng. Microwave imaging of perfectly conducting cylinder based on time reversal and single antenna[J]. Journal of Southwest Jiaotong University， 2011， 46（3）： 451455.
[5]廖成，卫涛，陈伟. 整数微分进化策略及其在微波成像中的应用[J]. 西南交通大学学报，2007，42（6）： 647652.
LIAO Cheng， WEI Tao， CHENG Wei. Integer coded differential evolution strategy and application to microwave imaging[J]. Journal of Southwest Jiaotong University， 2007， 42（6）： 647652.
[6]张秋菊，王秉中. 时域有限差分法电磁仿真的网格自动剖分[J]. 电子科技大学学报，2007，36（1）： 6669.
ZHANG Qiuju， WANG Bingzhong. Auto dissection of entity with grid for FDTD[J]. Electromagnetic Simulation Journal of University of Electronic Science and Technology of China， 2007， 36（1）： 6669.
[7]CHEN Linglu. Auto dissection of entity with threedimensional network based on FDTD[C]∥2010 AsiaPacific Symposium on Electromagnetic Compatibility. Beijing： IEEE Press， 2010： 920923.
[8]SRISUKH Y， NEHRBASS J， TEIXEIRA F L， et al. An approach for automatic grid generation in threedimensional FDTD simulations of complex geometries[J]. IEEE Transactions on Antennas and Propagation， 2002， 44（4）： 7580.
[9]MACGILLIVRAY J T. Trillion cell CADbased cartesian mesh generator for the finitedifference timedomain method on a singleprocessor 4GB workstation[J]. IEEE Transactions on Antennas and Propagation， 2008， 56（8）： 21872190.
[10]杨丽霞，葛德彪，白剑，等. 三角面元数据模型FDTD网格生成技术[J]. 西安电子科技大学学报，2007，34（2）： 208302.
YANG Lixia， GE Debiao， BAI Jian， et al. A novel FDTD modeling technique based on triangle meshunits of an object[J]. Journal of Xidian University， 2007， 34（2）： 208302.
[11]梁英业，戴挺，赵建新，等. 基于STL的切片线扫描法网格剖分技术[J]. 铸造，2005，54（10）： 10021005.
LIANG Yingye， DAI Ting， ZHAO Jianxin， et al. Mesh generation using a slice line scanning method based on STL files[J]. Foundry， 2005， 54（10）： 10021005.
[12]ITO Y， NAKAHASHI K. Surface triangulation for polygonal models based on CAD data[J]. International Journal for Numerical Methods in Fluids， 2002， 39（1）： 7596.
[13]葛德彪，闫玉波. 电磁波时域有限差分方法[M]. 2版. 西安：西安电子科技大学出版社，2005： 3839.
[14]莫则尧，张爱清. 并行自适应结构网格应用支撑软件框架[R]. 北京：北京应用物理与计算数学研究所，2009： 317.
[15]廖成，杨丹，方剑. 不同极化方向电磁脉冲作用于计算机机箱的效应分析[J]. 微波学报，2007，23（4）： 2831.
LIAO Cheng， YANG Dan， FANG Jian. Numerical analysis for EMP having different polarization direction coupling to a computer case[J]. Journal of Microwaves， 2007， 23（4）： 2831.
[16]喻炜，颜宏，金之雁. 并行效率的初步研究[J]. 应用气象学报，1996，7（1）： 6168.
YU Wei， YAN Hong， JIN Zhiyan. The preliminary study on the efficiency of parallel model computation[J]. Quarterly Journal of Applied Meteorology， 1996， 7（1）： 6168.
[17]CHANG Lei. Parallel FDTD analysis of largescale ridged TEM horn antenna array[C]∥2009 International Conference on Microwave Technology and Computational Electromagnetics. Chengdu： IEEE Press， 2009： 344347.