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

摘要

The classical FMM algorithm (Fast Multipole Method) [1]is based on the tree structure. It can be used to solve the N-Body problem. FMM can reduce the calculation complexity of the N-Body problem from O(N2) to O(N) with an arbitrary precision. CPU takes a lot of time in calculating the large-scale N-Body problem. To accelerate the execution of the algorithm, this paper conducts a study on the implementation of FMM on the Cell/B. E. Processor. Firstly, we break FMM into eight core steps according to their functions. Secondly, we classify these eight steps in light of their calculation features. Finally, we choose several representative steps, explain the feasibility of their implementations on Cell/B. E. , and introduce their design and implementation methods on Cell/B. E.. The result shows that the implementation of the key steps that we selected in FMM obtain a high speedup ratio comparing with CPU.%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较高的加速比.