计算机工程与科学2011，Vol.33Issue(8)：79-83,5.DOI:10.3969/j.issn.1007-130X.2011.08.014
FMM算法在Cell/B.E.处理器上实现的分析与验证
Analysis and Verification of the FMM Algorithm Based on the Cell/B.E.Processor
摘要
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.关键词
FMM/N-Body/Cell/B.E./加速/分析和验证Key words
FMM/N-Body/Cell/B. E./speedup/analysis and verification分类
信息技术与安全科学引用本文复制引用
唐振,张倬,柴亚辉,徐炜民..FMM算法在Cell/B.E.处理器上实现的分析与验证[J].计算机工程与科学,2011,33(8):79-83,5.基金项目
上海市重点学科建设资助项目 (J50103) （J50103）
