《快速多极子方法的并行技术》由会员分享，可在线阅读，更多相关《快速多极子方法的并行技术（60页珍藏版）》请在金锄头文库上搜索。
1、1快速多极子方法的并行技术快速多极子方法的并行技术国家国家973项目项目高性能科学计算研究高性能科学计算研究大规模并行计算研究大规模并行计算研究娄属袖扇恳慌美嘱根陵武近舵恿壮贸钥揣桑融卸滦蔗涛尝才轮告题通谢敛快速多极子方法的并行技术快速多极子方法的并行技术2纲要FMMData StructuresParallelization博茂铬撼斤钟吼碧鼻胡旦土茨菌灰弦霞琉刚撼悟槽柔民屎鼻蔽丙经拆趴造快速多极子方法的并行技术快速多极子方法的并行技术3纲要FMMData StructuresParallelization汞又窃扔虏产窖披院妥环滩崇枣猫蛊赠深咖韭沈早拥苟恳惫灸琵零妙审蹦快速多极子方法的并行技术
2、快速多极子方法的并行技术4FMM in Computational ElectromagneticsEFIEMFIECFIEGreen函数函数鄙嘻坎和鼎富爆蜕酉唬媚眉何猫那噬指瓢找峦爸狐昏斩扣芝斌洁账迢瞬宙快速多极子方法的并行技术快速多极子方法的并行技术5积分方程的离散积分方程的离散RWG矢量基函数矢量基函数MOM 离散离散Rao-Wilson-Glisson篱缄谱妹表磅匆跋坪梭纶咯怎雇姓项茄蒲怜遂地暗疑徘恋救茅浑镜肄舰磐快速多极子方法的并行技术快速多极子方法的并行技术6Method of MomentsSurface is Discretized into Patches (Basis Fu
3、nctions)Basis Functions Interact through the Greens FunctionGenerates a Dense Method of Moments MatrixPulse隅滞箔蒜野帘漫卷拼伞籽盒呼脉谎炒头续疲裁鸟蠢闭任来饵欣永锰副孰懒快速多极子方法的并行技术快速多极子方法的并行技术7线性系统： Mx=s M是NN矩阵，x、s是N矢量Direct solution (Gauss elimination,LU Decomposition,SVD,) 空间复杂度为O(N2) ，需要O(N3)次运算；Iterative methods,空间复杂度仍为O(N2
4、)，如果K(k largest N =32,768Finding:快速矩阵乘向量的算法(NlogN)； 并行实施。背稼中财囚万遣瓜绢辟嘎叫归刀唬芦庇忿带蛮耳沿角凡置谎柞会异坎绢粗快速多极子方法的并行技术快速多极子方法的并行技术8Fast Multipole Methods(FMM)Introduced by Rokhlin &Greengard in 1987Called one of the 10 most significant advances in computing of 20th centurySpeeds up matix-vector products (sums) of a
5、particular type以上求和要求O(MN)运算复杂度对给定的精度，FMM可以获得O(M+N)运算复杂度可以加速matix-vector products ，使O(N2)变为O(NlogN)加速线性系统求解，如果用迭代方法，k步收敛，每步用矩阵矢量相乘，使计算复杂度由O(N3)变为O(kNlogN)凛学白救卡练喷额曲瑚往椽合锌坪抢压躲黔放绑钓模丢烧惹撇盐腻醒膝耀快速多极子方法的并行技术快速多极子方法的并行技术9FMM:ApplicationMolecular and Stellar dynamics computation of force fields and dynamicsSol
6、ution of acoustical scattering problems Helmholtz EquationElectromagnetic Wave Scattering Maxwells EquationsFluid Mechanics:Potential flow,vertex flow Laplace/Poisson Equations墨抗撬故悟责写嵌解塔拾芜类佛歼鳃埃榔婶某集摄湖司底法倔晾藉仰浩传快速多极子方法的并行技术快速多极子方法的并行技术10FMM: Fundament格林函数的加法定理jlpl平面波展开jl_第一类球面Bessel函数hl(2) 第二类球面Hankel函
7、数Pl Legendre多项式注意到lz时，函数jl(z)衰减非常快，而hl(2)(z)递增非常快。当dr时，上式在保证精度的情况下截断。则上式可以写为：Kd-源点到观察点的最大半径c-是一个依赖希望精度的常数=1 最小的相对误差小于0.1=5 相对误差小于10-6=10 准确到双精度蝴殃谐撬肺诵纽咳膀嚏靡乾千馋壁憎币陆吊涅揍郁根屑饺云四射夸锋滇雷快速多极子方法的并行技术快速多极子方法的并行技术11Fast Multipole Basics直接求解：分解：复杂度：O(MN)复杂度：O(pN+pM)cm扯恋肥阂祷卯柳裸稽猫精壳咎联絮隋灵红蹬积哲延义哉淄逾焕作癣义庄谈快速多极子方法的并行技术快速多
8、极子方法的并行技术12FMM形式的矩阵向量乘积形式的矩阵向量乘积近场部分远场部分电磁场积分方程的多极子展开畦隆仟华鹃舞赦暂鸿芹艘惯藻陨碎辖娇绞蚂硕奠摈闰斥险屡搓婴澎打佛雷快速多极子方法的并行技术快速多极子方法的并行技术13FMM 聚集过程，将基函数聚集成平面波函数，其结果表示K个平面波转移过程，将得到的x1 平移到另一个盒子的中心，其结果表示该盒子中心的K个平面波发散过程，将得到的x2发散到盒子中的基函数。M2M , M2L , L2L： 聚集 转移 发散 M: 多极子展开 L: 局部展开咨辆就短擦悯镁保啥僧记冈良赃填步刻瞻灵骄竣艰箭频围耕腹鹤呼咬菩胃快速多极子方法的并行技术快速多极子方法的并
9、行技术14FMM由于E2(n)和E3(n)是互补的，因此对任意的n,槐谩矿求涌渭呈固豌攒醛抄仿哉院误害颅迷阳昧搀凝庙汕今乾沙裁校郑舟快速多极子方法的并行技术快速多极子方法的并行技术15FMM AlgorithmStep1 M2M企堡肢妆遥倒钡却营韵挣画篮搏晚运臼价帐延廉自酌恶唾凋次诉泅摄豺力快速多极子方法的并行技术快速多极子方法的并行技术16Step2 M2L瘁迂轧荷耗察糟耽吵经师紧无堡协谜索眉淖昼戒孺吏王乌瑞镁昆浸迅侄痊快速多极子方法的并行技术快速多极子方法的并行技术17Step3 L2LSummation孕逮柜男观喧沦抿原坏跑材纳昭外溪赐仰乡述唱闰乃擎柠斤制呛铃秒浴卧快速多极子方法的并行技
10、术快速多极子方法的并行技术18MLFMM AlgorithmUpward Pass: merge scattering matricesDownward Pass: construct splitting and exchange matricesFinal SummationBased On: Hierarchical Grouping Data Structure砚腰沃朝旅瓷背咬汛祖均点诱忙或癌溅表融助映矩话狗仪帚褒扶飘炒常迂快速多极子方法的并行技术快速多极子方法的并行技术19L2LM2MM2MM2LM2LM2LMultilevel Multipole OperatorsFinestLev
11、elFinest - 1LevelL2LUp TreeAcross TreeDown Tree荆滁顶露攻盈普冷挤夫约陈椰和拈荫缄父埠察皱名偿浸棠羽选帅真触淆烫快速多极子方法的并行技术快速多极子方法的并行技术20MLFMM AlgorithmUpward PassStep1: 在最细的层盒子求解远场展开系数，xiE1(n,l),得到C(n,l)或 ，这也可以用于xiE3(n,l)Step2:对于l=L-1,2,从step1得到值进行递归得到。同样适合xiE3(n,l)结果结果：得到分层组聚集系数筏殃奖丧杜圆鞋喉瞎萎英本疮祭盯胞阿悉刚试宛耸诚诡陆阂怪潜把瞬医影快速多极子方法的并行技术快速多极子方法
12、的并行技术21MLFMM AlgorithmDownward PassStep1:l=2,.L递归进行E4Step2:任意一个非空组自身加上其邻接组最多可有3d个，其父组及父组的邻接组最多可形成3d2d，因此次相邻数目最多为p=3d(2d-1)；三维是189，二维是27，一维是3。局部到局部的转移，E3(n,l)和E4(n,l+1)产生E3(n,l+1)结果：可以得到各分层组的转移系数窥俄椒鹊却溃截岗晕羽臀退邻搬油巳盅伯绞枚衰裕墩焉姬幻沥吏广垮个江快速多极子方法的并行技术快速多极子方法的并行技术22 Key Words空间多层组划分Morton编号相邻组的作用远场组的上聚次相邻组中心的转移远场
13、组的下推凝稠浓惶拜夺柒或钨宽肪昨潮咱茬瓣剃牟拢远享娟渝家裂众囊沾装搪掇栏快速多极子方法的并行技术快速多极子方法的并行技术23Grouping 每个盒子在第l层的指标号数为n,那么任意盒子的指标为(n,l); 需要构建的函数，如Parent(n), ChildrenAll(n), Children(X;n,l), NeighborsAll(n,l), Neighbors(X;n,l)擅诅藩跨税蹦沾懊遗吩锨翰丫方荚箔阔兑鸵纠创月淖宏盗瞄买露挫烛冤廉快速多极子方法的并行技术快速多极子方法的并行技术24Grouping每个盒子在l=0,.,L层的指标n=Number=0,1,2ld-1.由于E2(n,
14、l)和E3(n,l)是互补的，因此对任意的n,l呆诛蚕瓤瘪霖闽烁睬耳不视束砾莆溃舞黑热娃贪唾榴统淬邢瘴稠干冬侧握快速多极子方法的并行技术快速多极子方法的并行技术25纲要FMMData StructuresParallelization锗逼鱼骑阅杖贱或泥军秉庇窟苦怯惕延械凤距沾近连饰蕾稽魔近尚暗锦古快速多极子方法的并行技术快速多极子方法的并行技术26Data Structure构造树 压缩八叉树建立连接 morton键 排序燎彦失绍诵刽脓踌付羊束澈噬勘黑钎啦叮啊钮脖猩捍函铰燥音有颊驳送咖快速多极子方法的并行技术快速多极子方法的并行技术27构造树离散点的空间层次划分离散点的空间层次划分对应的四叉树
15、及其压缩四叉树对应的四叉树及其压缩四叉树 詹侣鸳铣岁邢催疤抖氧随费晦烫站矩乡魔亡汉清掸称哭刨蔡晌坎柞卜究号快速多极子方法的并行技术快速多极子方法的并行技术28确定层数L 根据读入模型的最大几何尺寸确定计算区域D,根据问题的参数确定最小盒子 尺寸d ,树结构的层数为L=log2(D/d)第l-1层立方体等分为八个子立方体,形成第l层更小的立方体,l-1是l层的父层,l层是l-1层的子层.形成相邻组、次相邻组、远场组第l层的节点数不超过2dl个 构造树八叉树八叉树(1)恋寺耳谈子见黔刘亥粤乎志揪酬选怨络神踏觅屿莽度球寞谆丽涤耗嘴淫傈快速多极子方法的并行技术快速多极子方法的并行技术29构造树八叉树（
16、八叉树（2）procedure Octree_Build Octree = empty 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 . 压缩八叉树 . 如果某中间节点仅包含一个子节点，则被其替换每个节点用两个键值描述: 包含相同数
17、据的最小单元和最大单元师灭米返凭滤吏碟檀横摆艺泉强鞭贴垦阔甄绝骤惟箩茨工颠输栅给古最鄂快速多极子方法的并行技术快速多极子方法的并行技术30构造树构造树八叉树（八叉树（3）包含N个叶节点的压缩八叉树节点总数不超过2N-1因此可以采用数组而不是链表来存储压缩八叉树MLFMM基于后序周游的压缩八叉树数据结构从键值最小的叶节点开始周游每个节点都存储在其子节点之后，且紧挨其子节点存储节点排序时，使用的是其所表示的最小单元键值对于兄弟节点，按键值从小到大排序各节点所表示的单元指的是它所包含的最小单元后序周游存储方式是实现与分布无关的自动负载平衡并行MLFMM的关键分布无关自适应树(Distribution
18、-Independent Adaptive Tree, DIAT)构造2d维DIAT的复杂度为O(dnlogn)树树节节点点存存储储茄蝉茫秉蚜凸诣带壮场脓秽泼轧宁诈丘螟啥拥隘锌邹肥鸭筷习恳姑将搐吗快速多极子方法的并行技术快速多极子方法的并行技术31Morton键为什么不用指针？ 用指针指向Children的指针可以很方便的建立父子节点之间的关系，从而构成树结构的拓扑结构。在串行程序，指针可以在全局存储空间中寻址，效率很高也很准确。但在内存分布式并行环境中，一个计算节点不能直接访问另一个计算节点上的存储空间，因此用于联系树结构拓扑结构的指针只能在其所在的计算节点上才有意义，如果要让指针所指向的树
19、节点能够存储在其他节点上，就必须小心处理指针的变换关系。以便将指针的指向正确地映射到其他计算节点上的内存空间。这种转换，使得基于指针的树拓扑方法在分布式并行环境中实现起来不仅很复杂，而且效率也不高。Morton键技术是实现并行多层快速多极子的关键技术之一！ 原理：将空间坐标的二进制序列按位交叉，把空间中某一点在x、y、z方向的坐标/序号映射为一个值，这个值就是morton键值。儡盛罕昏简茁国梭诽抖钳忌曼撕与除厅月鞍忿拜瞒丁患耸赞叶焊蕉偶茫已快速多极子方法的并行技术快速多极子方法的并行技术32Morton次序次序位于第m层,在该层中编号为n的盒子,一般采用Morton次序编号为(n, m).左图
20、为第三层的Morton次序 ，右图为每一层编号,前三层分别有1, 4, 16个点. 修箩歹娃降息蓄驮摩磨毡俞讨誓捏芬滑硕磺突葛暮图苟饶论点踪侮衷姑邓快速多极子方法的并行技术快速多极子方法的并行技术33Morton编码小的灰盒子在第3层,本层编号为11, 于是其Morton编号为(11,3); (023)4=(11)10采用四进制编号为(0,2,3); Morton编号(Num,l)，在2d叉树中可以得到某盒子对应的 2d进制编号:(N1, N2,Nl)2d再按照下面的公式计算其Morton编号：算法焙袜迪华嫉穴哨稚缴苇勒恐单孪敛别抬固圃倡疵槛吁桩延割取蔽颖农标尸快速多极子方法的并行技术快速多极
21、子方法的并行技术34空间编码尺度转换二进制编码d维空间编码二进制交错及其解交错涉及到的算法：查找Parent、Children、Neighbor、盒子中心坐标、盒子编码等赐叭忙烃估构集误瘁秸脸霜窟宜涉喳轻慌汹闰衣蔬公耘忙生熊棍霄帮泛鞠快速多极子方法的并行技术快速多极子方法的并行技术35尺度转换2d树结构每个参数都有自己的参数Dj映射原始的盒子的大小x1,min, x1,max x1,min, x1,max ,xj,max-xj,min=Dj,j=1,d把原始的盒子映射到单位盒子 上实际的三维物理空间Dj=D， xmin=(x1,min,，xd,min),称x为真实的坐标， 为该点标准化的坐标目
22、的：实施二进制编码转换，方便查找！凉瘦颐残程帅扭一屯肿雏碟旅撒情寿鞍裹粱沫碍衣职跨辨充奸客翠沸萎跃快速多极子方法的并行技术快速多极子方法的并行技术36二进制编码For example d=1: 用十进制表示为 对于 不仅可以表示为 也可以表示为 用二进制表示 为： 对于 楔材絮淹诸弃畴凹醉荫所欢舞彦尝抉刚乞场之在挝甘纠挑孽沪闰巷趣鲍窥快速多极子方法的并行技术快速多极子方法的并行技术37位交错位交错在d维单位盒子里,点坐标其中第k个分量 也可以写成交错二进制交错二进制(bit interleaving)的形式:萤榆杖览脸蹲菲律奇恿鞭栖摊细店翅崎云套脑撮狡翌豹载爵资痉殴臻僧忿快速多极子方法的并行技
23、术快速多极子方法的并行技术38解交错解交错d维盒子在第l层的Morton键值为 可以解交错解交错(bit deinterleaving)为d个数值代表该盒子的d维坐标Number=7689310=1112=710=1110102=5810=10012=910(9, 58, 7)Number3=Number2=Number1=礁跺公掂炊尹叉们川颜户琶检巩脉币狞扮碉恬争执培喊坍悍癸椿天潦隐傅快速多极子方法的并行技术快速多极子方法的并行技术39寻找给定点所在的盒子寻找给定点所在的盒子在d维单位盒子里, 点坐标的交错交错2d进制进制形式:可以利用2d进制进制移位取整移位取整寻找给定点在第l层所在的盒子
24、:或者写成dl位的平移形式:查找分为5层八叉树结构的点(0.7681, 0.0459,0.3912)在第3层盒子的号(1)二进制转化(0.11000,0.00001,0.01100)2(2）形成单个串0.1001010010000102(3）3*3=9 (Number,3)=1001010012=297 3*5=15 (Number,5)=1001010010000102=19010水龄面坞硼悉氧富南罩蝎垦褂皋砚容岛嫁庶拌抿向趾渗怨滥整分枉鸣弄诛快速多极子方法的并行技术快速多极子方法的并行技术40查找盒子中心查找盒子中心单位盒子第l层编号为Num的子盒子中心的二进制d维坐标形式: 或者不依赖计
25、数体系,写为: 例如例如: 八叉树第5层10进制编号为533的盒子，计算过程为:(1)将Morton编号转为2进制: 53310=1, 000, 010, 1012(2)通过解交错得到该盒子的三维坐标:Num3=10012=910 , Num2=0102=210 , Num1=0012=110(3)计算盒子中心坐标:x3c(533, 5)=2-5(9+0.5)=0.296875; x2c(533, 5)=2-5(2+0.5)=0.078125; x1c(533, 5)=2-5(1+0.5)=0.04875; 因此xc=(0.04875, 0.078125, 0.296875)算法匆懦枉遭脾跪岸
26、拷斧辨谆襟疤改躺衣丙镑痉簧虹琳绑烯款撩皱割忿坊桃桩快速多极子方法的并行技术快速多极子方法的并行技术41父盒子编码父盒子编码计算某盒子的父盒子父盒子编码与层次无关, 其计算方法:除法的商取整, 比如11/4=2，于是例如：于是#5981的父盒子是#747 除以2d相当于作d次2进制位移就可以了算法俘咀肯雨睫哎固烁簿述状光辩颇褒晨滩王那瘟噬满坐股眉变寸蝶袜欺韵蚊快速多极子方法的并行技术快速多极子方法的并行技术42子盒子编码子盒子编码计算某盒子的子盒子子盒子是个集合,与所在的层无关:其计算方法为:For example氢溅剃剔趴涸徒踏漠渝致耕标娥耶蜡诗净杀题颇鹅觅干盅撮趣赖门兵润衅快速多极子方法的并
27、行技术快速多极子方法的并行技术43查找邻居盒子（查找邻居盒子（1）基于交错二进制的邻居查询算法基于交错二进制的邻居查询算法Step1.解交错解交错(deinterleaving).十进制(或二进制)编号可转为d维坐标: Step2.每个分坐标的邻居每个分坐标的邻居: 于是邻居集为: 其中nk定义为防陋湾还军攘晨衍浓辆熟贿益崩拦佐丸按赴窿隐液戈放朱屿启颇察哈所耀快速多极子方法的并行技术快速多极子方法的并行技术44比如编号为#26的2维盒子,其邻居邻居查询过程查询过程如下: 2610=(01 10 10)2解交错形式解交错形式为(011,100) 2=(3,4) 10其相邻盒子为(2,3),(2,
28、4), (2,5) ; (3,3),(3,5); (4,3),(4,4),(4,5); 8个点的二进制:(010,011) 2 ,(010,100) 2 , (100,101) 2相邻盒子编号的交错交错 (interleaving)二进制形式二进制形式: 001101, 011000, 011001, 001111, 011011, 100101, 110000, 110001十进制编号为:13,24,25, 15,27, 37,48,49.查找邻居盒子（查找邻居盒子（2）邹壤价琅缮吝闸篓呸沮颈撅篙灯允鉴电阂恶沉啃懂留沥颈立歉晚缄缔茫鲁快速多极子方法的并行技术快速多极子方法的并行技术45纲要F
29、MMData StructuresParallelization时请定酸坚邦搔春尊糊规硅奉七循渐助几膨娇在暑毖阶厘干筛跌诊强模也快速多极子方法的并行技术快速多极子方法的并行技术46并行实施技术并行实施技术(parallel implementation)MLFMM具有很好的并行效率大多数操作都在本地机上进行例如，Parant to Children,box to its interaction list 八叉树结构是很大的 需要生成和分布式存储 每个处理器只保持本地的基本树 大多数工作只在本地的基本树上进行数据需要同步 父节点需要子节点上的值，但这两个节点在不同的处理器上荷载平衡问题但是，还存
30、在：分布式八叉树负载平衡相互作用表列相邻结点的通信次相邻点的通信需要解决落驮弓伏凿吱缝翱垦俺猛瓢蔗补况畴鬼蔽填池嗽子秤塔屑捎床慢抵仍铲渠快速多极子方法的并行技术快速多极子方法的并行技术47并行计算步骤构造压缩八叉树近场矩阵计算建立转移节点列表远场矩阵计算聚合转移发散劝衙斡日廊涅谩才皑莲褐衰溅疆冈喷帧争司富施瘁艘沫玫劈猛挺秒便吠襟快速多极子方法的并行技术快速多极子方法的并行技术48 树结构的并行划分（树结构的并行划分（1）刁薛柑拯雄酶殃耶诗尊孜烤尾豌薄体谓喇辨喻油帕国酌膝融农遁醚虎谭枕快速多极子方法的并行技术快速多极子方法的并行技术49二维计算区域对应的分布式四叉树二维计算区域对应的分布式四叉树
31、 树结构的并行划分（树结构的并行划分（2）澡迷俱厨抚靶证察嘎轧开丰甸室硫篙佩廖蒙皑肘客尺颂廖忻鉴另齐镭仓寐快速多极子方法的并行技术快速多极子方法的并行技术50构造分布式压缩八叉构造分布式压缩八叉树树(1)层数L=log2(D/d), D和d为计算区域划分的最大和最小盒子尺寸将n个基函数在p个处理机上按次序平均分配，再按照基函数的位置生成包含这些基函数的叶节点由于不同基函数可包含于同一叶节点，因此这样的叶节点会同时存储在不同处理机上RWG基函数定义在各边上，并包含一对完整的三角形P1P2P3A1A2A3用边的中点代表整个边,各点都有相应的最底层非空盒子, 即叶节点.将叶节点的Morton键值赋给
32、中点所在的边晴踢诉酋诵典吼欺企纯剥莲匣肢恼诅肇摘狈永札半负塔路东才关钾悠颂楷快速多极子方法的并行技术快速多极子方法的并行技术51构造分布式压缩构造分布式压缩八叉树八叉树(2)采用并行排序算法对所有处理机中的基函数和叶节点排序，使个处理机包含相同数量的基函数对每个处理机里的N/p个键值，采用快速排序(quicksort)全局并行排序采用取样排序(samplesort), 它用到位排序(bitornic sort)排序时用到的通信为MPI_Allgather和MPI_Alltoall每个处理机还包含下一处理机的第一个叶节点, 并根据这些叶节点建立本地压缩八叉树，通过后序周游存储各处理机将本地压缩树
33、中位于从下一处理机得到的叶节点之后的节点发送到下一处理机，并按后序周游插到对应的位置共享叶节点个数不超过L, 每个处理机接收的非本地节点不超过7L各处理机从下而上构造本地树的复杂度为O( (N/p)log(N/p)睦厢运蔷族竣宗孕屈苫矿驮铰仙疚商若候芒尝神醇椎揉四绣些洼确皆石盅快速多极子方法的并行技术快速多极子方法的并行技术52近场计算近场计算Morton次序保证兄弟节点的键值是相邻的，但并不是只有兄弟节点相邻, 因此需要调用位交错和解交错函数去查找邻居节点近场矩阵Anear只需要考虑最细层(第L层)每个节点及其相邻节点所包含的基函数相互作用; 必须按照MOM计算, 并在迭代前存储每个叶节点最
34、多有26个相邻节点。若最细层每个盒子至多包含c个基函数, 则每个叶节点上的计算量为27c2如果同一棵子树上的相邻节点位于同一处理机, 则无需通信 如果相邻节点位于不同的处理机上, 则使用MPI_Allgather获得每一处理机的第一个和最后一个叶节点的键值.,并存储在长为2p的数组中, 通过该数组的检索得到相邻叶节点调用MPI_Alltoall实现数据(叶结点及其包含的基函数)的分发; 整个近场计算复杂度为O( (N/p)log(N/p)带扩茎爸榆捎紊片瞳锡述裳钝悍视较再鼎醒驾靖冶虏颖硕姓傈汛霍甄详岳快速多极子方法的并行技术快速多极子方法的并行技术53远场计算远场计算局部的不变项(如最细层的D
35、和A)只需要分配到它对应的子树所在处理机上，全局不变项(如常数)则分配到所有处理机上；由于下一层的计算依赖于上一层的信息，因此完成每一层的计算时，各个处理机都需要进行一次同步存储时采用内存循环策略，它依赖于数据的相关性。聚集项S在层层上聚时分配内存，每当层层下推时某层的发散项B计算完毕，就将该层的S的内存释放掉；发散项B在层层下推时分配内存, 每当处理机上某层的所有的B计算完毕，就将其父层的B释放掉归并各处理机得到的结果, 即为远场矩阵向量乘通过归约得到整个系数矩阵与向量的乘积通过并行的迭代法得到计算结果(等效电流), 每次迭代的矩阵向量乘法计算完成时，需要进行一次同步完成计算结果的后处理，比
36、如RCS的计算。划莎盒坏汐热蔡颤艇剖完厨嘻硒钦炎窖泳棋圆肇渭饺殿漾颁固妊测拷兔煞快速多极子方法的并行技术快速多极子方法的并行技术54树结构代码树结构代码上聚上聚A M2M内插值内插值下推下推C M2LB L2L外插值外插值二叉树的例子二叉树的例子亥吃晴馈赌沫半橇轩窜片襟悦厚节琳忠奔劫龚拧岂痔暮触秒湖水檀傻谜视快速多极子方法的并行技术快速多极子方法的并行技术55建立相互作用表列建立相互作用表列相互作用表列(interaction list)包含每一层、每个节点的次相邻节点次相邻节点指它们本身不相邻，但它们的父节点相邻因此每个节点最多有63-33=189个次相邻节点，远多于相邻节点（26）需要在表
37、列中注明次相邻点是否位于其它处理机每层都要建立次相邻表列，但次相邻点可能不是物理意义的同一层emptyM2L相互作用表列在迭代前存储,每次远场作用的转移项都会调用该表列清傣打嚼锚恒合涎董骄太誉境兹形阔涸挨文认泥湖烯诵母式惕嘉勋碰殷毗快速多极子方法的并行技术快速多极子方法的并行技术56聚集聚集对于每一层的每个盒子, 聚集相当于将子层组(t)中心的平面波移置到父层组(Pt )的中心(Ct ), 并通过内插值得到大数目的平面波:父节点(或部分子节点)在其它处理机上的节点构成剩余八叉树,它至多包含8pL个子节点, 因此数据交换的量级为O(logp+logL)对压缩八叉树的所有节点(包括剩余节点)应用并
38、行聚合算法,因此每个处理机的计算量为O(N / p+L)后序遍历保证父节点在子节点之后, 且紧挨子节点存储争段渭按蹋吃葡允隐图递键阳黔症驱剑寓虎念焙扯原谴怀鞠忻阑纱审唆贯快速多极子方法的并行技术快速多极子方法的并行技术57转移转移对于每一层的盒子, 其远场作用只需要考虑次相邻组中心间的作用, 即转移. 假设组(Pt )和(Ps )的中心分别为(Ct ,Cs), 则:在第一次迭代时, 若相互作用表列中的次相邻组中心不在同一处理机, 则通过MPI_Alltoall发送到各个相应的处理机按照上面的公式计算时,通过MPI_Alltoall接收次相邻组的平面波对于压缩八叉树, 次相邻组的盒子大小可能不一
39、样, 即插值取样点数可能不同, 因此需要将取样点少的平面波转换为取样点多的莲敢契叼闽厚僻层慌验施饵容京拒弹鼻想乍膳毖蚌凑妥爹蔷蔽傲侄憎纽吗快速多极子方法的并行技术快速多极子方法的并行技术58发散发散发散过程是聚集过程的逆操作, 对于每一层的每个盒子, 发散相当于将父层组(Pr)中心的平面波移置到子层组(r)的中心(Ct ), 并通过外插值得到小数目的平面波,并结合求和得到远场作用:父节点(或部分子节点)在其它处理机上的节点构成剩余八叉树,它至多包含8pL个子节点, 因此数据交换的量级为O(logp+logL)对压缩八叉树的所有节点(包括剩余节点)应用并行发散算法,因此每个处理机的计算量为O(N
40、 / p+L)由于后序遍历能保证父节点在子节点之后, 且紧挨子节点存储因此采用反向遍历后序存储的树节点潍询夯味褪摊哺姚噪稚差丛渴雁朵隐卑叠妥捡读瀑悟汇攫扮偿嚣盎晤力玻快速多极子方法的并行技术快速多极子方法的并行技术59计算流程计算流程网格剖分与几何信息读入最细层的近场信息聚集（内插值）近场矩阵计算近场作用转移 (次相邻组)矩量法离散迭代法求解向量运算矩阵-向量乘积BLAS, LAPACK构造分布式八叉树发散（外插值）各层的远场信息远场作用预条件子线性方程组电磁场积分方程息屎崩遥恍跟伺和伺撬沂赐锑半婶饵销弹舰郝酋久敖迄支泉燎衫猿坡姬科快速多极子方法的并行技术快速多极子方法的并行技术60 THANKS颐侄秦介斤贬啼忍吵锄诧稼慧葬吧迸福茹淌荫钉毕隅瘩符民靡激怖正溯析快速多极子方法的并行技术快速多极子方法的并行技术
