Analysis and Verification of the FMM Algorithm Based on the Cell/B.E. Processor

J4 ›› 2011, Vol. 33 ›› Issue (8): 79-83.

• 论文 • Previous Articles Next Articles

Analysis and Verification of the FMM Algorithm Based on the Cell/B.E. Processor

TANG Zhen,ZHANG Zhuo,CHAI Yahui,XU Weimin

(School of Computer Engineering and Science,Shanghai University,Shanghai 200072,China)

Received:2010-06-23 Revised:2010-11-20 Online:2011-08-25 Published:2011-08-25

Abstract

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

TANG Zhen,ZHANG Zhuo,CHAI Yahui,XU Weimin. Analysis and Verification of the FMM Algorithm Based on the Cell/B.E. Processor[J]. J4, 2011, 33(8): 79-83.

Analysis and Verification of the FMM Algorithm Based on the Cell/B.E. Processor

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments