西电新技术讲座课程大作业-并行核外矩量法

1、新技术讲座课程大作业报告 并行核外矩量法学 院： 电子工程学院 专 业： 电磁场与无线技术 班 级： 1302061 学 号： 姓 名： 电子邮件： 日 期： 2016 年 06 月 21日成 绩： 指导教师： 张玉 摘要本文先简要介绍并行核外计算的发展现状与并行计算的核心思想及其评估方法中加速比的概念，再详写核内LU分解的推导过程并由此推广到并行核内LU分解，最后引出并行核外LU分解算法。并行核内矩量法与并行核外矩量法比较是本文核心，以求导体球的散射模型为例，比较并行核内矩量法与并行核外矩量法，发现并行核外矩量法比并行核内矩量法填充阶段时间消耗多2-3倍，并且二者的加速比均不理想。同时也发现

2、并行核外矩量法在填充阶段所消耗的时间比并行核内矩量法多了不到一倍，结合在大规模电磁计算中计算机内存的重要性，得出并行核外矩量法在大规模计算中以少量的的额外时间消耗换来计算机内存的合理利用的结论。总而言之，为了突破计算机内存大小的限制，并行核外矩量法为实际的工程电磁计算提供了一种综合效率较高的选择方案。关键词：并行核外矩量法 加速比 计算机内存 工程电磁计算 一、 并行核外计算发展现状计电磁学发展至今，应用范围越来越广，近些年来更是在电大尺寸平台中得到了快速发展。由于电大尺寸平台下所解决的问题复杂，研究目标不论是形状还是环境都很繁杂。在采用矩量法分析后，虽然可以得到很高的精度，但却面临着庞大的矩

3、阵规模。引入机群处理后，设计并行计算来处理需要很大的内存，种种原因的折衷结果就是引入核外空间存储该矩阵，然后分块读取和处理，最后计算出所需的各类参数，引出目标体相应的特性。二、并行计算2. 1并行计算简介并行计算（parallel computing）是将某一个运算任务进行分解，然后将分解后所得的子任务交给各个很多处理器进行运算处理。在运算过程中，每个处理器之间实时进行数据通信和协同运算，并完成了子任务。在这一基础上，整个运算的速度大大提高，求解计算速度效率显著增强，计算的规模可以成倍增加。通过并行计算的定义可以看出，并行计算至少需要两台以上的计算机同时运行，且每台计算机之间可以实时进行数据交

4、换；待处理的运算任务可以被划分成多个子任务，并且，每个子运算任务可以并行在各个计算机处理器上同时计算，还要有固定的程序对各个处理器上的数据编程处理，汇总运算结果，最终达到并行计算的目的。2.2并行算法评估评估手段有很多，这里重点介绍加速比的概念：在处理器资源独享的情况下，单个处理器进行计算所需的时间比多个处理器在相同环境下处理同一个任务时所需时间的比值，称为加速比公式定义为加速比（P个处理器）：（2-1）其中是指单个处理器完成真个运算任务所需的时间，是指P个处理器在并行算法下运算同一个任务所需要的时间。三、并行核内与核外LU分解3.1矩阵方程我们首先关注小型运算问题。并行计算的数值分析，包括设

5、计矩量法（MOM）时需要进行的矩阵填充和其后的矩阵分解，也涉及核内或者核外的问题。 在使用并行路两发程序进行电磁场积分方程的运算时，执行过程中会产生如下的矩阵方程： （3-1） 其中，A为M*M的矩阵，且M和未知量相关，当索要计算的目标模型和跑分的尺寸确定后，未知数是能够计算出来的，A表示阻抗矩阵；X为M*1的向量，时所需要求解的电流矩阵（向量）；B也是M*1的向量，表示在激励电磁波或者所加载激励源作用下模型表面产生的电压矩阵。 求解过程中如果A矩阵的规模太大，计算机内存RAM存储不下，也就处理不了，所以需要将硬盘的空间开辟出来用以存储这个巨大规模的矩阵，也就是之前提及的核外技术。这种和外处理

6、方式放在并行环境下结合矩量法处理电磁场计算问题，就是本论文所需要讨论的采用并行核外MOM方法求解电磁场积分方程的问题。存储问题依靠核外技术加以解决，求解矩阵方程的问题，由于所产生的矩阵是稠密矩阵，所以在这里选用直接求解的LU分解技术。因为LU方法起源于核内算法，所以下面将逐步介绍LU分解过程中矩阵的填充分布和求解方法。3.2核内LU分解 求解式（3-1）的方程，需要先将A矩阵进行LU分解。这是非常重要的矩阵求解方法之一，LU分解是将A矩阵分解为两个三角矩阵的乘积，这两个矩阵分别为上三角矩阵和下三角矩阵，如图所示。分解方法很多，最知己的方法是每次将下三角矩阵的某一行和上三角矩阵的某一列填充到内存

7、中：图3.1 核内LU分解步骤 式3-1可以表示为 （3-2）第一次填充时 （3-3） （3-4）进行到第r次时因为 (3-5)所以可以得出 （3-6）可以总结出：U矩阵的计算中，进行到第r行时，其第j个元素需要用该元素本值减去两个向量的乘积。它们的一个向量为U矩阵中第1行到第r行的第j列元素，另一个向量是L矩阵中第一列到第r列的第r行元素。 同样地，可以得出 （3-7）式（3-7）表示：L矩阵的第i行计算中，其第r个元素也需要用该元素本值减去两个向量的乘积，然后除以。其中的一个向量是L矩阵中第一行到第i行的第i列元素，另一个向量是U矩阵中第1列到第r列的第r列元素。 上述的LU分解完成后，式

8、（3-1）表示的矩阵方程变为： （3-8）其中： （3-9） (3-10) 上面两个矩阵方程（3-9）和（3-10）的求解过程比较简单，计算速度也很快。 如果计算（3-1）所示的矩阵方程时，A矩阵过于巨大，可以讲A矩阵分块，然后对分块后的A矩阵进行块LU分解。所以式（3-1）可以表示成 （3-11）其中，,都是K*K矩阵；0是空矩阵。于是可以得到下面的矩阵方程： （3-12） （3-13） （3-14） 其中，每一个分块矩阵的计算可以根据前面（3-3）到（3-10）所述的方法进行LU分解。当然A矩阵也可以分成很多块，而不止上面所讨论的4块，原理是相同的。LAPACK提供了求解式（3-1）矩阵方

9、程的连续算法，在对上面所讨论的核内LU算法进行并行扩展或，可以在并行计算机群众获得高性能，即为并行核内LU分解。如果对CPU之外的硬盘区加以利用，即可成为并行核外LU分解，下面将以并行核内LU分解为基础，简要介绍并行核外LU分解。3.3 并行核外LU 分解3.3.1核外算法 所谓核外技指的是将数据先放在硬盘上，等用的时候再读取出来，每次一点，分批进行，处理完后再写入硬盘，等用的时候重复前面的步骤。而核外算法就是基于核外技术设计的算法结构，其主要目的是处理一些超大规模矩阵方程，不论是直接求解（例如LU分解），或是间接求解（例如迭代解）都需要超大内存，甚至达到TB级别，给算法的设计和程序的编写调试

10、带来诸多不便。又由于硬盘相对比较廉价，因此使用硬盘代替内存来存储计算过程中所产生的超大规模矩阵显得十分必要，将开发成本降到可以接受的范围。 核外技术由于纯运算速度快，所以大部分时间都浪费在了数据存储和交换上。希望随着算法的不断优化，存储交换技术的不断进步，将来内存和硬盘之间数据的交换变的越来越快，促使看、核外算法进一步完善。 3.3.2 核外存储 核外存储是按照数据所占空间大小对矩阵分块完成的，如图3.2所示图3.2核外存储矩阵划分单核运行时，核外矩阵填充可以轻松地完成。然而，当多个核进行运算时，核外的填充是一块一块地进行分布式填充，这样矩阵的填充就被设计成上面的模式，以便避免多余的运算而得到

11、更好的并行效率。3.3.3核外LU分解假设核外矩阵的填充完成后，进而需要进行的操作及时和外LU分解，当前的理论普遍认为，矩阵相乘运算最有计算方法是通过矩阵分块形式来完成的。 参照式（3-1），通过LU所分解矩阵元素的分布形成和其相应的乘法法则将核外LU分解为两种形式，left-looking和right-looking。如图所示：图3.3 left-looking LU分解图3.4 right-looking LU分解图3.3和图3.4分别描绘两个3*3矩阵块运用LU算法是其数据是如何入到内存进行处理的，其中阴影部分代表将要读入内存进行计算的行或者列。图 中列的计算需要用不到之前的LU分解得到

12、的列：图 中行和列的计算后需要更新右下角.如此进行，使用两个LU分解形式，最终都将得到整个矩阵的分解结果，从而实现核外算法。 left-looking和right-looking两种形式得核外LU分解方法相比，从运算时读取和写入的数据来看，left-looking的相对较少。因此大多数情况下用left-looking形式的LU分解方法，而且在矩阵写入硬盘之前阻抗矩阵是经过主元确定处理的。 left-looking核外LU分解用到的有BLAS库中的GEMM函数和LAPACK库中的GETRF函数。如果要进行并行核外的LU分解，其函数得到ScaLAPACK库中的PxGETRF等，同时得调用LAREA

13、D函数和LAWRITE函数进行读写。四、并行核外矩量法相比于并行核内矩量法的优越性 我们所研究的并行核外矩量法，顾名思义，包含并行与核外两个关键点，并行计算的速度要大于单核计算的速度，但是核外矩量法真的要优于核内矩量法吗？或者说它有多大的优越性，下面我们将用一个例子进行比较4.1 导体球体的散射 自由空间中有如图所示的半径1m的导体球，在600MHz的平面波激励下，计算其双站RCS。入社电磁平面波为，且该球面破分为9.812个三角形，未知数有14.718个。并行核外矩量法（OC）和并行核内矩量法（IC）的RCS结果与Mie级数的解析结果对比如图 和图 所示，可见三个结果几乎完全吻合，验证了两种

14、并行算法的正确性。图4.1 导体球模型及电磁平面波图4.2半径1m导体球核内外算法XOZ面散射场对比4.2不同块大小的测试在并行LU分解算法中，为了实现负载均衡，需要将矩阵采用快循环方式存储。块的大小（BlockSize）将影响矩阵读写速度，从而影响算法的计算速度。在核内算法中，块大小影响内存读写矩阵的速度；而在核外算法中，块大小影响文件读写矩阵的速度。对于导体球模型，在4*6=24核内进程网格情况下，测试不同块大小时的计算时间。根据图4.3和4.4所示，课件不论是核内的计算时间还是核外的计算时间都在块大小取128时达到最小值，因此本例后续计算中均将块大小设置为128进行测试图4.3 并行核内

15、块大小测试结果图4.4并行核外块大小测试结果4.3进程网格的测试 在并行LU分解算法中，将所有进程排列成二维的锦城网格（Process Grid）。不同的进程网格计算效率可能有很大差别。同样以导体球为例，将块大小设置为128，取总核数为24。将24个核分成不同的进程网格进行测试，如图4.5和4.6所示。可见当锦城网格接近正方形时，核内程序和核外程序的计算时间都是最少的。当进程网格偏离正方形时，核内和核外程序时间都会增大。因此本文后续的算例中，锦城网格都尽量趋于正方形。图4.5并行核内进程网格测试结果图4.6并行核外进程网格测试结果4.4不同核数的测试 除了块大小和进程两个因素之外，并行程序中需

16、要设置的最重要的参数就是核的总数。对于上述代替求模型，采用最优的分块大小和合适的而为进程网格进行测试，计算时间如下表4.1所示。 从表4.1中可以看出：（1）在矩阵填充阶段，并行核外矩量法的时间比并行核内矩量法多几倍。随着核数增加，两种方法消耗的时间都在减少。注意到核内算法的加速比达不到理想的加速比，而核外算法的加速比更低，这表明两种并行算法都还需要进一步优化。（2）在矩阵LU分解阶段，并行核外矩量法的时间仍然比并行核内矩量法所用时间长，但是前者最多比后者多0.9倍。核外算法的这种额外开销在工程实践中是可以接受的。表4.1导体球核内外时间对照表4.5内存的对比一般情况下并行核内矩量法所需内存较

17、大，并行核外矩量法的所使用内存较小。如表4.2所示，由于并行核内矩量法只是用内存，则可以算出计算导体球时其存储所需内存为3305.4MB，然后对参加计算的每个处理器评分：并行核外矩量法因为使用了硬盘替代内存故而对内存的需求较少。表4.2每个处理器/进程的内存需求 可以明显看出禀性和外巨量法中每个处理器所需的内存远远小于使用相同核数进行计算导体球时禀性和内巨量法所需的内存，这是因为并行核外矩量法使用了硬盘代替了内存来存储矩阵元素，而且每次填充或者求解时最多读取两列子块，相对应的并行核内矩量法则需要在内存中一次性存储所有的元素并进行求解。4.6 并行核外矩量法相比于并行核内矩量法的优越性本节通过对

18、导体球的并行核内矩量法和并行核外矩量法欲望不同矩阵规模下的测试结果和Mie级数对比验证了并行算法的正确性。然后通过相同核数下不同块大小的测试证实了分块的最优大小，在依照最优分块大小及相同的核数下采用不同的二维进程网格测试发现，最合适的进程网格应该接近于正方形。在对导体球在不同核数的测试下发现，大量的时间消耗在了矩阵填充阶段，矩阵LU分解阶段的时间消耗相比较少。最后还分析了并行核外矩量法相比并行核内矩量法在内存使用上的优点，因为算法设计不同，前者使用的内存大大少于后者。又因为实际的科学实践核工程应用中资源的限制，并行核外矩量法以少量的的额外时间消耗换来资源的合理利用是十分具有意义的。五、并行核外矩量法总结本文主要按照我对并行核外矩量法的认识的过程写来，先写并行核外计算的发展现状，并简要介绍并行计算，再详写核内LU分解的推导过程并由此推广到并行核内LU分解，并行核外LU分解算法。最后的并行核内矩量法与并行核外矩量法比较是本文核心，以求导体球的散射模型为例，比较并行核内矩量法与并行核外矩量法，发现并行核外矩量法比并行核内矩量法填充阶段时间消耗多2-3倍，随着核数的增加二者的填充时间都变小了，然而二者的