求解二维随机多区域声波散射问题的快速多极边界元方法

快速多极算法(FMM)是求解大尺度边界元问题的一种很有效的快速算法.应用快速多极算法求解二维随机多区域声散射问题的边界积分方程.首先给出了求解该问题的边界积分方程,进而给出快速多极算法求解的算法实现过程以及积分算子的相应多极展开、局部展开和相应系数的转化关系式.最后通过对数值例子的计算表明快速多极算法在求解随机多区域声散射问题时的可行性及高效性,其求解存储量和计算量都是O(N).     

FMM算法在Cell/B.E.处理器上实现的分析与验证

FMM算法[1]是基于树结构的,用于解决多体问题(N-Body)的经典算法。它将N-Body问题的计算复杂度由O(N2)降为O(N),并且能达到任意精度。通用CPU在计算规模较大的N-Body问题时需要耗费大量的时间。为了加速算法的执行,本文对FMM算法在Cell/B.E.处理器上的实现进行了分析与验证。首先从功能上将FMM算法分解为八个核心过程,在此基础上根据计算特点的不同,对八个核心过程进行归类,最后选取其中有代表性的核心步骤,阐述了其在Cell/B.E.上实现的可行性问题,以及部分核心步骤的设计和实现过程。实验结果表明,选定的FMM算法核心步骤在Cell/B.E.上可以获得相对通用CPU较高的加速比。     

电场积分方程的快速求解

矩量法(MOM)离散电场积分方程(EFIE)得到稠密的线性方程组,它可以用迭代法(比如本文中的TFQMR方法)求解.每次迭代过程中,矩阵与向量的乘积的复杂度为O(N2).采用多层快速多极子方法(MLFMM),可将其降到O(N log N).采用基于球谐变换的快速傅立叶变换,可进一步加快MLFMM的层间插值计算.数值结果显示MLFMM求解EFIE是可行的.     

FMM算法的并行化方法

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

快速霍夫变换算法

二值图像的直线检测过程中,标准霍夫变换算法的计算量为O（N^3)。该文提出一种快速霍夫变换算法,其计算量仅为O（N^2log2N)。该快速算法可以并行实现;处理器阵列规模为O（N^2)时,计算量为O（log2N)。文中还分析得到快速算法的误差上界,并提出一种改进的快速霍夫变换算法以获得更高的计算精度。最后,给出算法的数值算例。理论分析及数值算例都表明,该文的快速霍夫变换算法在直线检测过程中有着更高的计算效率,并且具有良好的计算精度。     

多层快速多极子算法并行实现的数据划分策略

虽然多层快速多极子算法在解决大尺度电磁散射问题中表现出了很好的效率,但是,当未知量达到千万时,由于复杂的结构和计算该算法很难再保持高效的计算能力。为了解决负载均衡引起的性能瓶颈问题,提出多层快速多极子算法基于八叉树的多层结构并行数据划分策略。该方法包括根据树结构中分布层和共享层不同特征的单独处理,也包括解决数据冲突的转移层的处理方法和为了减少分布存储系统中的通信时间而在分布层引入的冗余技术。实验结果表明多层快速多极子算法并行计算的开销明显减少,并且能够获得比较高的并行效率。     

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

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

BH算法的几点注记

N-Body问题的直接计算方法的时间复杂度是O（n2）,BH算法的时间复杂度为O（nlogn）.BH算法利用质心近似计算降低了时间复杂度,但同时也降低了计算结果的准确度.为把与判断足够远的参数θ（θ=l/d）密切相关的计算结果的近似准确度控制在要求的范围内,应用多极扩展和Gauss数值积分方法给出了BH算法质心近似的数学解释以及误差ε与参数θ的关系,得出BH算法是FMM算法和Gauss数值积分的一个特例,并指出Gauss积分法中隐含的正交多项式较FMM中常用的chebyshev正交多项式更与求解的问题相关.     

位平面编码存储优化算法及FPGA设计

提出一种基于子块的存储优化算法,可用于解决现有JPEG2000位平面编码器中存在的访问编码块存储器模式失配问题.采用将编码块划分成4×4的子块独立进行编码的策略,将访问同一小波系数的时间间隔从3N2Δt减少至48Δt,同时将访问编码块存储器的次数从(3K-2)N2降低至N2W.该算法不仅兼容现有各种加速技术,而且增加了子块并行的机会.基于FPGA平台实现了一种子块并行合并样本并行的位平面编码器结构,能够将编码时间复杂度从O(N2)降低至O(N),同时节省状态信息存储39%以上.实验结果表明,与目前最快的三层并行结构相比,文中设计的加速比达到了1.3.     

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

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

Parallel implementation of fast multipole method based on JASMIN

Fast multipole method (FMM) may reduce the complexity of N-body problems from O(N 2 ) to O(N log N) or O(N).It was applied in problems ranging from electromagnetic scattering to dislocation dynamics.FMM can be divided into two parts: commonness and individuality.A parallel solver of FMM commonly used in various applications has been designed and implemented in JASMIN infrastructure.The solver encapsulates the commonness.Furthermore,it supplies users with abstract interfaces required to implement the individ...     

PGAS‐FMM: Implementing a distributed fast multipole method using the X10 programming language

The fast multipole method (FMM) is a complex, multi‐stage algorithm over a distributed tree data structure, with multiple levels of parallelism and inherent data locality. X10 is a modern partitioned global address space language with support for asynchronous activities. The parallel tasks comprising FMM may be expressed in X10 by using a scalable pattern of activities. This paper demonstrates the use of X10 to implement FMM for simulation of electrostatic interactions between ions in a cyclotron resonance mass spectrometer. X10's task‐parallel model is used to express parallelism by using a pattern of activities mapping directly onto the tree. X10's work stealing runtime handles load balancing fine‐grained parallel activities, avoiding the need for explicit work sharing. The use of global references and active messages to create and synchronize parallel activities over a distributed tree structure is also demonstrated. In contrast to previous simulations of ion trajectories in cyclotron resonance mass spectrometers, our code enables both simulation of realistic particle numbers and guaranteed error bounds. Single‐node performance is comparable with the fastest published FMM implementations, and critical expansion operators are faster for high accuracy calculations. A comparison of parallel and sequential codes shows the overhead of activity management and work stealing in this application is low. Scalability is evaluated for 8k cores on a Blue Gene/Q system and 512 cores on a Nehalem/InfiniBand cluster. Copyright © 2013 John Wiley & Sons, Ltd.     

Comparing the treecode with FMM on GPUs for vortex particle simulations of a leapfrogging vortex ring

We compare the performance of the treecode and the fast multipole method (FMM) on GPUs. These fast algorithms are used to accelerate a vortex particle simulation of two leapfrogging vortex rings. The performance of the treecode and FMM depends strongly on the number of particles, type of hardware, distribution of particles, and the required accuracy. Our results demonstrate that for the accuracy that is required in vortex method simulations the crossover point between the treecode and FMM is around N = 3000 on the CPU. On the GPU, the treecode is able to achieve more acceleration than the FMM, and no clear crossover point is observed.     

多体问题FMM算法在加速部件FPGA研究与实现

针对FPGA能较好满足高性能计算的异构多核、并行、低成本、低能耗要求,研究了高性能计算的重要的应用之一——多体问题。分析了多体问题应用广泛的FMM算法以及FMM算法的各个算粒,并在FPGA器件实现算粒,与多核CPU上实现这些算粒进行比较,FPGA都获得了不错的加速比。分析了FPGA应用高性能计算的一些优势和当前面临的问题,对FPGA广泛应用高性能计算进行了初步探索。     

Automatic dynamics simplification in Fast Multipole Method: application to large flocking systems

This paper introduces a novel framework with the ability to adjust simulation’s accuracy level dynamically for simplifying the dynamics computation of large particle systems to improve simulation speed. Our new approach follows the overall structure of the well-known Fast Multipole Method (FMM) coming from computational physics. The main difference is that another level of simplification has been introduced by combining the concept of motion levels of detail from computer graphics with the FMM. This enables us to have more control on the FMM execution time and thus to trade accuracy for efficiency whenever possible. At each simulation cycle, the motion levels of detail are updated and the appropriate ones are chosen adaptively to reduce computational costs. The proposed framework has been tested on the simulation of a large dynamical flocking system. The preliminary results show a significant complexity reduction without any remarkable loss in the visual appearance of the simulation, indicating the potential use of the proposed model in more realistic situations such as crowd simulation.