快速多极子方法的并行技术优秀PPT.ppt

快速多极子方法的并行技术纲要纲要FMMinComputationalElectromagnetics积分方程的离散线性系统：FastMultipoleMethods(FMM)FMM:ApplicationFMM:FundamentFastMultipoleBasicsFMM形式的矩阵向量乘积FMMFMMFMMAlgorithmStep2M2LStep3L2LMLFMMAlgorithmL2LMLFMMAlgorithm—UpwardPassMLFMMAlgorithm—DownwardPassKeyWordsGroupingGrouping纲要DataStructure构造树确定层数L
—根据读入模型的最大几何尺寸确定计算区域D,根据问题的参数确定最小盒子尺寸d,树结构的层数为L=log2(D/d)
第l-1层立方体等分为八个子立方体,形成第l层更小的立方体,l-1是l层的父层,l层是l-1层的子层.
形成相邻组、次相邻组、远场组
第l层的节点数不超过2dl个

构造树—八叉树〔2）构造树—八叉树〔3）Morton键Morton次序Morton编码空间编码尺度转换二进制编码位交错解交错寻找给定点所在的盒子查找盒子中心父盒子编码子盒子编码查找邻居盒子〔1）比如编号为#26的
2维盒子,其邻居
查询过程如下:
2610=(011010)2
解交错形式为
(011,100)2=(3,4)10
其相邻盒子为
(2,3),(2,4),(2,5);
(3,3),(3,5);
(4,3),(4,4),(4,5);
8个点的二进制:
(010,011)2,
(010,100)2,…
(100,101)2纲要并行实施技术(parallelimplementation)并行计算步骤树结构的并行划分〔1）二维计算区域对应的分布式四叉树构造分布式压缩八叉树(1)procedureOctree_Build
八叉树中可能有很多空的叶节点,但它们的兄弟节点非空
在2d—叉树中可以得到某盒子对应的2d进制编号:
(100,101)2
FinalSummation
在2d—叉树中可以得到某盒子对应的2d进制编号:
使用MPI_Allgather获得每一处理机的第一个和最后一个叶节点的键值.
(2,3),(2,4),(2,5);
由于不同基函数可包含于同一叶节点，因此这样的叶节点会同时存储在不同处理机上
(010,011)2,
FMMAlgorithm
三维是189，二维是27，一维是3。
SurfaceisDiscretizedintoPatches(BasisFunctions)
3912)在第3层盒子的号
MLFMMAlgorithm—UpwardPass
MLFMM基于后序周游的压缩八叉树数据结构
hl(2)—第二类球面Hankel函数近场计算远场计算树结构代码在2d—叉树中可以得到某盒子对应的2d进制编号:
树结构的并行划分〔2）
procedureOctree_Build
d维盒子在第l层的Morton键值为
MultilevelMultipoleOperators
但在内存分布式并行环境中，一个计算节点不能直接访问另一个计算节点上的存储空间，因此用于联系树结构拓扑结构的指针只能在其所在的计算节点上才有意义，如果要让指针所指向的树节点能够存储在其他节点上，就必须小心处理指针的变换关系。
(2,3),(2,4),(2,5);
FMMinComputationalElectromagnetics
在串行程序，指针可以在全局存储空间中寻址，效率很高也很准确。
各处理机从下而上构造本地树的复杂度为O((N/p)log(N/p))
右图为每一层编号,前三层分别有1,4,16个点.
——聚集过程，将基函数聚集成平面波函数，其结果表示K个平面波
Parallelization
Morton键技术是实现并行多层快速多极子的关键技术之一！
MolecularandStellardynamics聚集转移发散计算流程
THANKS谢谢