FMM算法的并行化方法

详细分析快速多极算法FMM(Fast Multipole Method)的基本原理,并对引力场的势函数的多极展开和泰勒局部展开进行了详细的推导。给出了串行FMM算法的伪码描述,并对其进行并行化分析、处理,对FMM算法进行了并行化研究。最后,在基于MPI的群集并行计算环境下进行大量的实验并采集实验数据,对算法进行并行化性能分析,得到较好的并行加速比和较高的并行效率。

基于FMM的Krylov子空间IGMRES(m)新算法及其应用

研究了Krylov子空间GMRES(m)算法的基本理论,提出一种基于FMM的Krylov子空间截断型IGMRES(m)新算法.给出三物体弹性摩擦接触算例,计算结果表明,所提出算法在保证计算精度的前提下,可以大大减少迭代次数,显著提高计算效率.

压缩感知结合FMM分析目标宽角度电磁散射问题

应用快速多极子方法(FMM)直接计算宽角度电磁散射问题时,需要对每一个入射角度迭代求解,计算量较大,效率较低。基于快速多极子方法中聚合、转移和发散过程与电磁波入射方向的无关性,将压缩感知理论(CS)引入并构建富含空间信息的新型激励源,仅由远小于入射角度数目的几次快速多极子计算,即可获得感应电流的观测值,近而恢复出所有入射角度下的激励电流。与传统矩量法结合压缩感知理论方法相比,该方法的计算精度较高,并且计算时间大幅减少。

一种改进的方向可控FastMarching方法

由于Fast Marching方法所规划出来的路径比传统的搜索方法所得路径更加光滑,并且不会像其它势场方法一样陷入局部最小,从而在路径规划中获得广泛应用.这种全局最优的路径规划方法严格受规划空间中障碍代价分布影响,路径产生采用对时间距离图的最陡下降法反向跟踪,路径缺乏可控性.通过加入人工力场的方法,对Eikonal方程的代价项进行分解,提出一种改进的代价模型,并利用Gudunov一阶逆风近似实现了一种改进的FMM,实验结果表明,该模型能够改善路径的可控性,对于要求路径局部具有特定方向的应用情景具有良好的适用性.

基于快速多极子基本解方法(FMM-MFS)的弹性波二维散射模拟研究

针对弹性波二维散射问题,发展一种新的快速多极子基本解方法(FMM-MFS)。方法基于单层位势理论,通过在虚边界上设置膨胀波线源和剪切波线源以构造散射波场,从而避免了奇异性的处理和边界单元离散;结合快速多极子展开技术(FMM),大幅度降低了计算量和存储量,突破了传统方法难以处理大规模散射问题的瓶颈。以全空间孔洞对P、SV波的二维散射为例,给出了具体求解步骤,并在个人计算机上实现了上百万自由度问题的快速精确计算。在方法效率和精度检验基础上,分别以单孔洞和随机孔洞群对平面波(P、SV波)的散射为例进行计算模拟,揭示了孔洞(群)周围弹性波散射的若干重要规律。

多GPU混合结构下FMM近程算法的优化

近几年,在高性能计算领域,GPU+CPU混合结构成为许多高性能计算机的主要结构,得到了广泛的应用。由于混合结构的特殊性,分析了传统的阿姆达尔定律,将其推广到混合结构中。针对FMM算法中近程计算部分在multi-GPU+CPU混合结构中存在的任务均衡以及通信延时等问题,在混合结构阿姆达尔定律的指导下,提出了多GPU调度模型和两级流水模型。该调度模型能够有效地进行多个GPU之间负载的均衡,缓解近程计算的非均匀性所带来的问题;同时,两级流水模型使CPU和GPU可以并行工作,通过计算和访存的重叠,来隐藏访存带来的延时问题,提高运算部件的利用率。实验验证和数据的比较证明了上述优化的可行性,该优化方案进一步加速了算法的执行。

基于混合架构的FMM算法硬件加速

以高性能计算中的经典问题——多体问题的快速多极子(FMM)算法为例,分析FMM算法的各个步骤,根据计算、通信和存储特性将算法中的子过程归类。在CPU、GPU、FPGA和CELL上分别进行测试,提出执行FMM算法的混合可重构体系结构配置方案,并进一步优化算法,分解任务流。针对不同任务流的特点,提出可行的解决方案。结果证明,该方案可提高算法效率。

应用DWT-FMM计算二维电大导体目标RCS

文章基于快速多极子的远场近似思想,提出了应用小波变换区分远场作用组中的强作用单元和弱作用单元,并在计算中忽略弱作用单元的方法。该方法让聚集和解聚矩阵更为稀疏,从而加快了它们与向量的相乘过程,应用该方法和快速多极子分别对二维电大导体目标的雷达散射截面进行计算,并将得到的结果进行比较。实验结果表明该方法在不影响精度的同时,有效降低了计算复杂度,且在内存消耗上有了很大的改善。

IPO结合FMM,RPFMM,FaFFA方法快速计算电大腔体的RCS

迭代物理光学法结合快速多极子(IPO+FMM)方法,可以快速计算电大腔体的电磁散射特性。传统的快速多极子(FMM)方法需要计算两组的转移因子以及转移过程的全部角谱分量,计算开销是非常大的。随着组间距离的增大,转移过程可以用射线多极子(RPFMM)简化计算,为了充分利用射线多极子方法中参与计算的有效角谱分量随着组间距离增大而变少的特性,采用一种随着组间距离增大自适应调整参与计算的角谱分量的锥形区域的射线多极子方法(RPFMM),当两组距离足够大而位于远场时,用远场近似方法(FaFFA)进一步简化计算。结果表明该方法能在保持计算精度的同时并能较IPO+FMM方法进一步减少计算资源占用、提高计算速度。

FMM能效分析及其ASIC可行性评估

对快速多极方法(FMM)进行研究,分析其关键计算任务,并在CPU与DSP上进行验证,得出FMM在不同平台上性能和功耗的量化分析结果,给出基于FMM的多核DSP可重构ASIC结构模型。以可重构硬件FPGA为例,对该模型进行预测,结果证明其在涉及大规模浮点计算时具有一定的能效优势。

三维多步FMM射线追踪在正态分布速度地层模型中的应用

三维多步FMM(Fast Marching Method)是一种基于网格追踪多个反射和透射相位的数值算法,通过有限差分法解程函方程来获取地震波走时后,从接收器开始反向沿着射线路径对走时场进行积分来获取射线路径,以精度高、速度快、适应性强、无条件稳定等特点而被广泛应用和研究。三维多步FMM不仅可以解决复杂介质反射波和多次波的射线追踪问题,还可以实现三维各向异性层状介质的多次波射线追踪和波前模拟。为了验证三维多步FMM在复杂模型的稳定性和灵活性,设计了随机正态分布速度地层模型,结果表明,三维多步FMM在正态分布地层模型中进行射线追踪时不仅保留着速度快、精确性高、无条件性稳定的特点,还能在速度界面处进行P波和S波的相位转换,表明了三维多步FMM是一种研究地震波在复杂介质中传播规律的快速有效的方法。!

基于绕射场修正快速迭代物理光学法的海面舰船与角反阵列电磁散射分析

随着雷达技术的发展,雷达制导武器严重威胁着海面舰船目标的安全.为了保护海面航线的舰船,多面角反射器得到了广泛利用.本文以海上舰船与角反射器阵列组合为分析目标,针对其散射作用强、局部耦合明显的目标散射特征,提出了局部迭代物理光学(iterative physical optics,IPO)方法进行高效的电磁散射建模,并采用快速多极子技术与GPU并行技术实现了大场景海面复杂目标与角反干扰阵列的快速雷达散射截面积(radar cross section,RCS)仿真计算.该方法通过将电流迭代求解再辐射作用的区域截断在射线路径周围的局部区域内的操作,减少了IPO方法中分析复杂目标的电磁散射过程所产生相互作用的循环计算未知量.同时该方法考虑了边缘绕射场对目标RCS的影响,并利用绕射场对表面反射场进行修正.不同类型舰船的角反射器阵列的仿真结果表明,本文方法可为海战场反电子侦察提供有效的理论实现方案.

基于Kinect相机的深度图像空洞修复算法

针对Kinect相机采集的原始深度图存在大面积空洞,采用快速进行法(FMM)修复算法存在图像边缘失真等问题,提出一种改进FMM的深度图像空洞修复算法。首先,对原始深度图像进行阈值处理,生成掩码图像以确定待修复区域;然后,采用改进FMM算法,引入置信度因子并使用固定尺度的目标块替换原先修复邻域,根据非零像素点占比选择不同的修复算法;当置信度较低时,根据图像特征连续性确定候选块搜索邻域,通过相似性度量函数获取最佳匹配块;最后,将最佳匹配块的中心像素值替换至待修复点,迭代至空洞完全修复。实验结果表明:与传统FMM算法相比,改进FMM算法的峰值信噪比提升了11.79%,避免了图像边缘失真等问题,可以有效地对Kinect相机采集深度图像过程中产生的空洞完成修复。

树结构在N体问题中的应用

N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2)。采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分。Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法。BHA可快速计算各点受到的场力,计算复杂度为O(NlogN),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度。数值结果表明,树结构的并行效果也很好。

变电站接地网雷电电磁场的快速算法

提出了一种计算大型变电站接地网电磁场的快速算法。首先,该算法使用修正镜像法(modified image method,MIM)将待求模型所处的半无限有损空间化为均匀空间,从而避免了原电场积分方程中出现的索末菲积分计算。其次,借助快速多极子方法(fast multipole method,FMM)求解该电场积分方程,最后,利用共轭梯度法求解线性代数方程。在选取基函数及权函数时充分考虑了阻抗矩阵对称性和区组元素相互作用的平移不变性。与其他文献及CDEGS软件的计算对比结果,验证了该算法的正确性、适用性及有效性。

大型目标RCS的快速计算及分析

阐述了近年来发展的用于分析电磁散射问题的快速多极子算法(FMM)和多层快速多极子算法(MLFMA).为了能够有效快速地分析大型复杂结构目标的散射特性,利用了混合积分方程(CFIE),并在上述快速算法迭代过程中采用不完全分解LU方法(ILU)的加速收敛技术,极大地提高了计算速度.同时重点研究了某特殊结构飞行目标的雷达散射截面(RCS),其结果对分析该飞行目标的散射特性有很好的指导意义.

二维问题快速多极虚边界元法

将快速多极展开算法和广义极小残值法应用于虚边界元法的方程求解中.以二维弹性力学问题为研究背景,提出了二维问题快速多极虚边界元法的思想.该方法利用二维复平面上的基本解,并将其展开为适合于快速多极算法的格式,即变革计算结构(或模式),使解方程的计算量和储存量与所求问题的自由度数成线性比例.此点充分体现出该方法数值模拟大规模自由度问题的能力.数值算例说明了该方法的可行性,计算效率和计算精度,同时,该方法的思想具有一般性,应用上具有扩展性.

快速多极子边界元法在吸声材料声场计算中的应用

对快速多极子边界元法中多极子展开式的数值计算进行了研究,建立四点单级传递关系与多级传递关系模型。通过与格林函数及其法向导数理论值的比较,考察两种传递情况下,多极子展开式在吸声材料介质及空气介质中的计算精度。结果表明,复波数展开式的求解精度与截断项数的大小相关,而且当复波数虚部值与展开点间距离乘积过大时,展开式值开始与真值相背离。最后提出了解决此问题的两种方法。此外,以膨胀腔阻性消声器传递损失计算为例,验证了该方法的有效性与可行性。

组合导体目标电磁特性的快速多极算法计算

用快速多极算法分析具有任意线、面、体组合的电大尺寸理想导体目标的电磁散射和辐射特性。统一采用RWG基函数对线、面、体导体上的电流进行展开;使用了新的设置基函数和未知量的方法来处理任意的线-面,面-面连接问题;并使用多层快速多极算法结合ILUT预处理算法加速求解过程。数值结果验证了本文方法的准确性和高效性。

快速多极子方法在申威众核处理器上的实现和优化

快速多极子方法(FMM)是一种求解N体问题的快速高效数值算法,在宇宙学和分子动力学等模拟中具有广泛的应用。申威SW26010是一款国产众核异构处理器,含260核心(4核组)。基于申威SW26010的众核架构设计和实现了快速多极子方法,并对核心函数(尤其是最耗时的粒子对相互作用)系统地进行了性能优化,包括异步DMA、SIMD向量化、循环展开、内联汇编指令调整等。以粒子对相互作用为例,优化后代码的计算速度约为主核上运行的原始代码的400倍,每个核组上的浮点性能达到250GFLOPS,即理论峰值性能的32.5%。