FMM算法中问题规模与空间划分的关系分析  

Analysis on relation between question scale and expansion in FMM

作　　者：曹旻[1] 杨彩霞[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机工程与应用》2011年第25期39-43,共5页Computer Engineering and Applications

基　　金：国家高技术研究发展计划(863)(No.2009AA012201-CFA2009SHDX02);上海市重点学科建设项目(No.J50103)~~

摘　　要：从编译优化和并行优化的角度出发,根据N-Body问题求解的FMM算法的原理,将算法分解为不同的子模块。详细分析了各子模块的计算特性,包括计算量分析、并行性分析、通信量分析和存储量分析。深入剖析问题规模与空间划分层数之间的关系,提出基于问题规模的空间划分策略。以实验验证了空间划分策略的可行性。According to the calculation theory of FMM algorithm,and considering its parallel optimization and compiler optimization,this paper divides this algorithm into different sub-modules.The computing characteristics of every sub-modules,including calculation load,parallelism,communication and storage,are analyzed in detail.Based on the deep analysis of relationship between the N-Body question scale and octree level,a strategy of hierarchical space decomposition associating with question scale is presented.The experiments validate the correctness and feasibility of the presented strategy.

关 键 词：编译优化 N体(N-Body)问题求解 快速多极子方法(FMM) 空间划分树 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]