快速多极子方法的并行技术.ppt
《快速多极子方法的并行技术.ppt》由会员分享,可在线阅读,更多相关《快速多极子方法的并行技术.ppt(60页珍藏版)》请在三一文库上搜索。
1、快速多极子方法的并行技术,冯仰德 王武 迟学斌 中科院计算机网络信息中心 超级计算中心 2007年2月5日,国家973项目高性能科学计算研究 大规模并行计算研究,纲要,FMM Data Structures Parallelization,纲要,FMM Data Structures Parallelization,FMM in Computational Electromagnetics,EFIE MFIE CFIE Green函数,积分方程的离散,RWG矢量基函数 MOM 离散,Rao-Wilson-Glisson,Method of Moments,Surface is Discret
2、ized into Patches (Basis Functions),Basis Functions Interact through the Greens Function,Generates a Dense Method of Moments Matrix,线性系统:,Mx=s M是NN矩阵,x、s是N矢量 Direct solution (Gauss elimination,LU Decomposition,SVD,) 空间复杂度为O(N2) ,需要O(N3)次运算; Iterative methods,空间复杂度仍为O(N2),如果K(k largest N =32,768 Find
3、ing:快速矩阵乘向量的算法(NlogN); 并行实施。,Fast Multipole Methods(FMM),Introduced by Rokhlin &Greengard in 1987 Called one of the 10 most significant advances in computing of 20th century Speeds up matix-vector products (sums) of a particular type 以上求和要求O(MN)运算复杂度 对给定的精度,FMM可以获得O(M+N)运算复杂度 可以加速matix-vector produc
4、ts ,使O(N2)变为O(NlogN) 加速线性系统求解,如果用迭代方法,k步收敛,每步用矩阵矢量相乘,使计算复杂度由O(N3)变为O(kNlogN),FMM:Application,Molecular and Stellar dynamics computation of force fields and dynamics Solution of acoustical scattering problems Helmholtz Equation Electromagnetic Wave Scattering Maxwells Equations Fluid Mechanics:Potent
5、ial flow,vertex flow Laplace/Poisson Equations,FMM: Fundament,格林函数的加法定理 jlpl平面波展开,jl_第一类球面Bessel函数 hl(2) 第二类球面Hankel函数 Pl Legendre多项式,注意到lz时,函数jl(z)衰减非常快,而hl(2)(z)递增非常快。当dr时,上式在保证精度的情况下截断。则上式可以写为:,Kd-源点到观察点的最大半径 c-是一个依赖希望精度的常数 =1 最小的相对误差小于0.1 =5 相对误差小于10-6 =10 准确到双精度,Fast Multipole Basics,直接求解:,分解:,
6、复杂度:O(MN),复杂度:O(pN+pM),cm,FMM形式的矩阵向量乘积,近场部分,远场部分,电磁场积分方程的多极子展开,FMM, 聚集过程,将基函数聚集成平面波函数,其结果表示K个平面波,转移过程,将得到的x1 平移到另一个盒子的中心,其结果表示该盒子中心的K个平面波,发散过程,将得到的x2发散到盒子中的基函数。,M2M , M2L , L2L: 聚集 转移 发散 M: 多极子展开 L: 局部展开,FMM,由于E2(n)和E3(n)是互补的,因此对任意的n,FMM Algorithm,Step1 M2M,Step2 M2L,Step3 L2L,Summation,MLFMM Algori
7、thm,Upward Pass: merge scattering matrices Downward Pass: construct splitting and exchange matrices Final Summation,Based On: Hierarchical Grouping Data Structure,L2L,M2M,M2M,M2L,M2L,M2L,Multilevel Multipole Operators,Finest Level,Finest - 1 Level,L2L,Up Tree,Across Tree,Down Tree,MLFMM Algorithm Up
8、ward Pass,Step1: 在最细的层盒子求解远场展开系数,xiE1(n,l),得到C(n,l)或 ,这也可以用于xiE3(n,l) Step2:对于l=L-1,2,从step1得到值进行递归得到。同样适合xiE3(n,l) 结果:得到分层组聚集系数,MLFMM Algorithm Downward Pass,Step1:l=2,L递归进行E4 Step2:,任意一个非空组自身加上其邻接组最多可有3d个,其父组及父组的邻接组最多可形成3d2d,因此次相邻数目最多为p=3d(2d-1);三维是189,二维是27,一维是3。,局部到局部的转移,E3(n,l)和E4(n,l+1)产生E3(n,
9、l+1),结果:可以得到各分层组的转移系数,Key Words,空间多层组划分 Morton编号 相邻组的作用 远场组的上聚 次相邻组中心 的转移 远场组的下推,Grouping, 每个盒子在第l层的指标号数为n,那么任意盒子的指标为(n,l); 需要构建的函数,如Parent(n), ChildrenAll(n), Children(X;n,l), NeighborsAll(n,l), Neighbors(X;n,l),Grouping,每个盒子在l=0,L层的指标n=Number=0,1,2ld-1.,由于E2(n,l)和E3(n,l)是互补的,因此对任意的n,l,纲要,FMM Data
10、Structures Parallelization,Data Structure,构造树 压缩八叉树 建立连接 morton键 排序,构造树,离散点的空间层次划分,对应的四叉树及其压缩四叉树,确定层数L 根据读入模型的最大几何尺寸确定计算区域D,根据问题的参数确定最小盒子 尺寸d ,树结构的层数为L=log2(D/d) 第l-1层立方体等分为八个子立方体,形成第l层更小的立方体,l-1是l层的父层,l层是l-1层的子层. 形成相邻组、次相邻组、远场组 第l层的节点数不超过2dl个,构造树八叉树(1),构造树八叉树(2),procedure Octree_Build Octree = empt
11、y For i = 1 to n . 对所有的点做循环 Octree_Insert(i, root) . 将点i插入八叉树相应的位置 end For . 八叉树中可能有很多空的叶节点, 但它们的兄弟节点非空 Traverse the tree (via, say, breadth first search) . 宽度周游 Eliminating empty leaves . 去掉空的叶节点 Compress Octree . 压缩八叉树 . 如果某中间节点仅包含一个子节点,则被其替换 每个节点用两个键值描述: 包含相同数据的最小单元和最大单元,构造树八叉树(3),包含N个叶节点的压缩八叉树节点
12、总数不超过2N-1 因此可以采用数组而不是链表来存储压缩八叉树 MLFMM基于后序周游的压缩八叉树数据结构 从键值最小的叶节点开始周游 每个节点都存储在其子节点之后,且紧挨其子节点存储 节点排序时,使用的是其所表示的最小单元键值 对于兄弟节点,按键值从小到大排序 各节点所表示的单元指的是它所包含的最小单元 后序周游存储方式是实现与分布无关的自动负载平衡并行MLFMM的关键 分布无关自适应树(Distribution-Independent Adaptive Tree, DIAT) 构造2d维DIAT的复杂度为O(dnlogn),树 节 点 存 储,Morton键,为什么不用指针? 用指针指向C
13、hildren的指针可以很方便的建立父子节点之间的关系,从而构成树结构的拓扑结构。在串行程序,指针可以在全局存储空间中寻址,效率很高也很准确。但在内存分布式并行环境中,一个计算节点不能直接访问另一个计算节点上的存储空间,因此用于联系树结构拓扑结构的指针只能在其所在的计算节点上才有意义,如果要让指针所指向的树节点能够存储在其他节点上,就必须小心处理指针的变换关系。以便将指针的指向正确地映射到其他计算节点上的内存空间。这种转换,使得基于指针的树拓扑方法在分布式并行环境中实现起来不仅很复杂,而且效率也不高。 Morton键技术是实现并行多层快速多极子的关键技术之一! 原理:将空间坐标的二进制序列按位
14、交叉,把空间中某一点在x、y、z方向的坐标/序号映射为一个值,这个值就是morton键值。,Morton次序,位于第m层,在该层中编号为n的盒子, 一般采用Morton次序编号为(n, m). 左图为第三层的Morton次序 , 右图为每一层编号,前三层分别有1, 4, 16个点.,Morton编码,小的灰盒子在第3层,本层编号为11, 于是其Morton编号为(11,3); (023)4=(11)10 采用四进制编号为(0,2,3); Morton编号(Num,l), 在2d叉树中可以得到某盒子对应的 2d进制编号: (N1, N2,Nl)2d,再按照下面的公式计算其Morton编号:,算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 多极 方法 并行 技术
链接地址:https://www.31doc.com/p-2135614.html