Abstract:

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.

Key words: FMM；NBody；Cell/B.E.；speedup；analysis and verification