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

摘要：

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较高的加速比.

关键词：FMM、N-Body、Cell/B.E.、加速、分析和验证

所属期刊栏目：33

分类号：TP302(计算技术、计算机技术)

资助基金：上海市重点学科建设资助项目 J50103

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：79-83