FMM算法中问题规模与空间划分的关系分析

从编译优化和并行优化的角度出发;根据N-Body问题求解的FMM算法的原理;将算法分解为不同的子模块。详细分析了各子模块的计算特性;包括计算量分析、并行性分析、通信量分析和存储量分析。深入剖析问题规模与空间划分层数之间的关系;提出基于问题规模的空间划分策略。以实验验证了空间划分策略的可行性。
     

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

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

位运算在N皇后问题中的应用

利用位操作运算的快速性,将位运算应用到N皇后问题的解决中,并给出了位运算求解N皇后问题的算法。该算法较好地提高了问题求解的速度。通过VC++环境实现,该算法比普通的递归回溯算法的速度平均提高了40倍左右。     

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

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

一种新的树结构及其在植物形态建模中的应用

植物模拟是计算机图形学中的研究热点,而形态建模是植物模拟的关键。本文对传统的树结构进行扩展,建立一种新的树结构。这种新的树结构一方面与植物生长发育的过程相符,另一方面也容易实现。     

FMM算法中PP问题在GPU上的研究与实现

针对目前快速多极子算法中PP问题在图形处理器上实现的缺点,如负载不平衡和计算规模受显存大小的限制等,提出了一种新的基于统一计算设备架构平台的实现方法。采取以Box为并行单位、在内存中开辟缓冲区与多线程流水计算等方式,使其适合于CPU和GPU组成的异构体系结构,充分利用CUDA编程模型的高并行性加速PP问题。实验结果表明,采用CUDA加速后,PP问题的计算时间明显降低,提高了整个FMM模拟效率,适合于各种多体问题的实时模拟。     

N体问题的FPGA求解和设计方法

N体问题是一个经典动力学问题,在多个领域得到广泛的应用。但随着规模的增大,对求解计算性能的要求成为其研究的主要障碍。当前,FPGA可重构技术由于具有硬件可编程结构和高度并行处理能力而成为高性能计算关注的热点。现以FPGA加速求解N体问题为例,阐述一种新型的求解计算密集型任务的方法。     

N体问题解析函数近似计算

考虑粒子相互作用的Ⅳ体问题解析函数近似计算,当Ⅳ很大时,将粒子点置放于空间区域中,计算粒子密度函数,用多重积分表示粒子相互作用径向分布函数的解析表达式,获得园域和球域分析解,根据不同数值大小的Ⅳ值,比较了数值解与分析解,发现当Ⅳ〉276时,分析解计算误差小于0．01．     

Distribution-Independent Hierarchical Algorithms for the N-body Problem

The N-body problem is to simulate the motion of N particles under the influence of mutual force fields based on an inverse square law. Greengards algorithm claims to compute the cumulative force on each particle in O(N) time for a fixed precision irrespective of the distribution of the particles. In this paper, we show that Greengards algorithm is distribution dependent and has a lower bound of ­(N log 2 N) in two dimensions and ­(N log 4 N) in three dimensions. We analyze the Greengard and Barnes-Hut algorithms and show that they are unbounded for arbitrary distributions. We also present a truly distribution independent algorithm for the N-body problem that runs in O(N log N) time for any fixed dimension.     

若干并行计算模型上的N体问题求解算法

从在实际中广泛应用的N体问题入手,研究如何在几种实际的并行计算模型(PRAM、APRAM、BSP、LogP、NHBL)上设计具体的并行算法;给出了这些模型上的并行算法的设计模式,分析不同模型上算法的性能,比较各个模型上算法设计风格以及算法性能的差异,并对这些并行计算模型做一个综合的评价。     

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...     

多体问题在GPU上实现的讨论

多体问题(N-body)是力学的基本问题之一,研究N个质点互相作用的运动规律。结合分子动力学计算模拟软件LAMMPS和天体多体物理模拟软件Gadget-2这两个有广泛应用的多体并行计算软件,分析其基本算法和实现,讨论这两个有代表性的并行计算软件在GPU等加速部件上移植的基本思路。     

BH算法的几点注记

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

Improved genetic algorithm for generalized transportation problem

In this paper, we introduce the genetic algorithm approach to the generalized transportation problem (GTP) and GTP with a fixed charge (fc-GTP). We focus on the use of Prüfer number encoding based on a spanning tree, which is adopted because it is capable of equally and uniquely representing all possible trees. From this point, we also design the criteria by which chromosomes can always be converted to a GTP tree. The genetic crossover and mutation operators are designed to correspond to the genetic representations. With the spanning-tree-based genetic algorithm, less memory space will be used than in the matrix-based genetic algorithm for solving the problem; thereby computing time will also be saved. In order to improve the efficiency of the genetic algorithm, we use the reduced cost for the optimality of a solution and the genetic algorithm to avoid degeneration of the evolutionary process. A comparison of results of numerical experiments between the matrix-based genetic algorithm and the spanning-tree-based genetic algorithm for solving GTP and fc-GTP problems is given. This work was presented, in part, at the Fourth International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–22, 1999     

基于SIMD-SM模型的树的后根遍历并行算法

文章基于SIMD-SM模型研究树的遍历问题,运用遍历树的边的思维方法,实现了树的后根遍历的一种并行算法,并且对该并行算法的复杂性进行了分析。