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

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

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

唐振，张倬，柴亚辉,徐炜民

（上海大学计算机工程与科学学院，上海 200072）

收稿日期:2010-06-23 修回日期:2010-11-20 出版日期:2011-08-25 发布日期:2011-08-25
作者简介:唐振(1985),男,安徽凤阳人，硕士，研究方向为系统结构和并行处理。张倬(1983),男,上海人,硕士,研究方向为系统结构和并行处理。
基金资助:
上海市重点学科建设资助项目(J50103)

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

摘要：

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., 加速, 分析和验证

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

唐振，张倬，柴亚辉,徐炜民. FMM算法在Cell/B.E.处理器上实现的分析与验证[J]. J4, 2011, 33(8): 79-83.

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.

[1]	陈杰, 李程, 刘仲. 面向多核向量加速器的卷积神经网络推理和训练向量化方法[J]. 计算机工程与科学, 2024, 46(04): 580-589.
[2]	郭宸良, 阎少宏, 宗晨琪. 线云隐私攻击算法的并行加速研究[J]. 计算机工程与科学, 2024, 46(04): 615-625.
[3]	秦文强, 吴仲城, 张俊, 李芳, . 基于异构平台的卷积神经网络加速系统设计[J]. 计算机工程与科学, 2024, 46(01): 12-20.
[4]	周理, 赵祉乔, 潘国腾, 铁俊波, 赵王. 基于RISC-V的图卷积神经网络加速器设计[J]. 计算机工程与科学, 2023, 45(12): 2113-2120.
[5]	周小华, 王学志, 周园春, 孟珍, . 面向大区域碳卫星数据的分布式Kriging插值算法优化[J]. 计算机工程与科学, 2023, 45(11): 1911-1921.
[6]	易啸, 马胜, 肖侬. 深度学习加速器在不同剪枝策略下的运行优化[J]. 计算机工程与科学, 2023, 45(07): 1141-1148.
[7]	康宇晗, 时洋, 陈照云, 文梅. 面向迈创+MatrixZone异构系统的深度学习编程框架[J]. 计算机工程与科学, 2023, 45(07): 1149-1158.
[8]	吴付坤, 曹轶, 董庆利, . 基于CAD几何模型的曲面流线可视分析方法[J]. 计算机工程与科学, 2023, 45(06): 961-969.
[9]	刘晓航, 姜晶菲, 许金伟. 基于脉动阵列的层融合注意力模型加速器结构[J]. 计算机工程与科学, 2023, 45(05): 802-809.
[10]	王玉雷, 谢凯亮, 陈思贇, 胡杰, 常胜. 卷积神经网络硬件加速的通用性设计[J]. 计算机工程与科学, 2023, 45(04): 577-581.
[11]	鞠鑫, 曹亚松, 文梅, 汪志, 冯静. 一种矩阵块间提前切换的脉动阵列优化策略[J]. 计算机工程与科学, 2023, 45(01): 1-9.
[12]	马现, 王勇献, 朱小谦, 屠厚旺, 李朋, 颜恺壮. 谱方法求解水声传播问题的优化与并行[J]. 计算机工程与科学, 2022, 44(03): 381-389.
[13]	吕高锋, 王玉鹏, 杨鎔嘉, 唐竹. 基于聚合的FlowRadar网络数据采集加速模型设计[J]. 计算机工程与科学, 2022, 44(02): 220-226.
[14]	陈浩敏, 姚森敬, 席禹, 张凡, 辛文成, 王龙海, 任超. YOLOv3-tiny的硬件加速设计及FPGA实现[J]. 计算机工程与科学, 2021, 43(12): 2139-2149.
[15]	程玉胜, 曹天成, 王一宾, 郑伟杰. 基于负相关性增强的不平衡多标签学习算法[J]. 计算机工程与科学, 2021, 43(09): 1700-1710.