【正文】 — 父節(jié)點(diǎn)需要子節(jié)點(diǎn)上的值，但這兩個(gè)節(jié)點(diǎn)在不同的處理器上 ? 荷載平衡問(wèn)題 但是，還存在： ? 分布式八叉樹(shù) ? 負(fù)載平衡 ? 相互作用表列 ? 相鄰結(jié)點(diǎn)的通信 ? 次相鄰點(diǎn)的通信 需要解決 47 并行計(jì)算步驟 ? 構(gòu)造壓縮八叉樹(shù) ? 近場(chǎng)矩陣計(jì)算 ? 建立轉(zhuǎn)移節(jié)點(diǎn)列表 ? 遠(yuǎn)場(chǎng)矩陣計(jì)算 –聚合 –轉(zhuǎn)移 –發(fā)散 48 樹(shù)結(jié)構(gòu)的并行劃分（ 1） 49 二維計(jì)算區(qū)域?qū)?yīng)的分布式四叉樹(shù) 樹(shù)結(jié)構(gòu)的并行劃分（ 2） 50 構(gòu)造分布式壓縮八叉 樹(shù) (1) ? 層 數(shù) L=log2(D/d), D和 d為計(jì)算區(qū)域劃分的最大和最小盒子尺寸 ? 將 n個(gè)基函數(shù)在 p個(gè)處理機(jī)上按次序平均分配，再按照基函數(shù)的位置生成包含這些基函數(shù)的葉節(jié)點(diǎn) – 由于不同基函數(shù)可包含于同一葉節(jié)點(diǎn)，因此這樣的葉節(jié)點(diǎn)會(huì)同時(shí)存儲(chǔ)在不同處理機(jī)上 – RWG基函數(shù)定義在各邊上，并包含一對(duì)完整的三角形 P1 P2 P3 A1 A2 A3 用邊的中點(diǎn) 代表整個(gè)邊 , 各點(diǎn)都有相應(yīng)的最底層 非空盒子 , 即葉節(jié)點(diǎn) .將 葉節(jié)點(diǎn)的 Morton鍵值賦給中點(diǎn)所在的邊 51 構(gòu)造分布式壓縮 八叉樹(shù) (2) ? 采用并行排序算法對(duì)所有處理機(jī)中的基函數(shù)和葉節(jié)點(diǎn)排序，使個(gè)處理機(jī)包含相同數(shù)量的基函數(shù) – 對(duì)每個(gè)處理機(jī)里的 N/p個(gè)鍵值，采用快速排序 (quicksort) – 全局并行排序采用取樣排序 (samplesort), 它用到位排序 (bitornic sort) – 排序時(shí)用到的通信為 MPI_Allgather和 MPI_Alltoall ? 每個(gè)處理機(jī)還包含下一處理機(jī)的第一個(gè)葉節(jié)點(diǎn) , 并根據(jù)這些葉節(jié)點(diǎn)建立本地壓縮八叉樹(shù)，通過(guò)后序周游存儲(chǔ) ? 各處理機(jī)將本地壓縮樹(shù)中位于從下一處理機(jī)得到的葉節(jié)點(diǎn)之后的節(jié)點(diǎn)發(fā)送到下一處理機(jī)，并按后序周游插到對(duì)應(yīng)的位置 ? 共享葉節(jié)點(diǎn)個(gè)數(shù)不超過(guò) L, 每個(gè)處理機(jī)接收的非本地節(jié)點(diǎn)不超過(guò) 7L ? 各處理機(jī)從下而上構(gòu)造本地樹(shù)的復(fù)雜度為 O( (N/p)log(N/p)) 52 近場(chǎng)計(jì)算 ? Morton次序保證兄弟節(jié)點(diǎn)的鍵值是相鄰的，但并不是只有兄弟節(jié)點(diǎn)相鄰 , 因此需要調(diào)用位交錯(cuò)和解交錯(cuò)函數(shù)去查找鄰居節(jié)點(diǎn) ? 近場(chǎng)矩陣 [Anear]只需要考慮最細(xì)層 (第 L層 )每個(gè)節(jié)點(diǎn)及其相鄰節(jié)點(diǎn)所包含的基函數(shù)相互作用 。 必須按照 MOM計(jì)算 , 并在迭代前存儲(chǔ) ? 每個(gè)葉節(jié)點(diǎn)最多有 26個(gè)相鄰節(jié)點(diǎn)。若最細(xì)層每個(gè)盒子至多包含 c個(gè)基函數(shù) , 則每個(gè)葉節(jié)點(diǎn)上的計(jì)算量為 27c2 ? 如果同一棵子樹(shù)上的相鄰節(jié)點(diǎn)位于同一處理機(jī) , 則無(wú)需通信 ? 如果相鄰節(jié)點(diǎn)位于不同的處理機(jī)上 , 則 – 使用 MPI_Allgather獲得每一處理機(jī)的第一個(gè)和最后一個(gè)葉節(jié)點(diǎn)的鍵值 .,并存儲(chǔ)在長(zhǎng)為 2p的數(shù)組中 , 通過(guò)該數(shù)組的檢索得到相鄰葉節(jié)點(diǎn) – 調(diào)用 MPI_Alltoall實(shí)現(xiàn)數(shù)據(jù) (葉結(jié)點(diǎn)及其包含的基函數(shù) )的分發(fā) 。 ? 整個(gè)近場(chǎng)計(jì)算復(fù)雜度為 O( (N/p)log(N/p)) 53 遠(yuǎn)場(chǎng)計(jì)算 ? 局部的不變項(xiàng) (如最細(xì)層的 D和 A)只需要分配到它對(duì)應(yīng)的子樹(shù)所在處理機(jī)上，全局不變項(xiàng) (如常數(shù) )則分配到所有處理機(jī)上；由于下一層的計(jì)算依賴(lài)于上一層的信息，因此完成每一層的計(jì)算時(shí)，各個(gè)處理機(jī)都需要進(jìn)行一次同步 ? 存儲(chǔ)時(shí) 采用內(nèi)存循環(huán)策略 ，它依賴(lài)于數(shù)據(jù)的相關(guān)性。聚集項(xiàng) S在層層上聚時(shí)分配內(nèi)存，每當(dāng)層層下推時(shí)某層的發(fā)散項(xiàng) B計(jì)算完畢，就將該層的 S的內(nèi)存釋放掉；發(fā)散項(xiàng) B在層層下推時(shí)分配內(nèi)存 , 每當(dāng)處理機(jī)上某層的所有的 B計(jì)算完畢，就將其父層的 B釋放掉 ? 歸并各處理機(jī)得到的結(jié)果 , 即為遠(yuǎn)場(chǎng)矩陣向量乘 ? 通過(guò)歸約得到整個(gè)系數(shù)矩陣與向量的乘積 ? 通過(guò)并行的迭代法得到計(jì)算結(jié)果 (等效電流 ), 每次迭代的矩陣向量乘法計(jì)算完成時(shí)，需要進(jìn)行一次同步 ? 完成計(jì)算結(jié)果的后處理，比如 RCS的計(jì)算。 54 樹(shù)結(jié)構(gòu)代碼 ? 上聚 – A — M2M – 內(nèi)插值 ? 下推 – C — M2L – B — L2L – 外插值 ? 二叉樹(shù)的例子 55 建立相互作用表列 ? 相互作用 表列 (interaction list)包含每一層、每個(gè)節(jié)點(diǎn)的次相鄰節(jié)點(diǎn) – 次相鄰節(jié)點(diǎn)指它們本身不相鄰，但它們的父節(jié)點(diǎn)相鄰 – 因此每個(gè)節(jié)點(diǎn)最多有 6333=189個(gè)次相鄰節(jié)點(diǎn)，遠(yuǎn)多于 相鄰節(jié)點(diǎn)（ 26） ? 需要在表列中注明次相鄰點(diǎn)是否位于其它處理機(jī) ? 每層都要建立次相鄰表列，但次相鄰點(diǎn)可能不是物理意義的同一層 empty M2L 相互作用表列 在迭代前 存儲(chǔ) , 每次遠(yuǎn)場(chǎng)作用 的轉(zhuǎn)移項(xiàng)都會(huì) 調(diào)用該表列 56 聚集 ? 對(duì)于每一層的每個(gè)盒子 , 聚集相當(dāng)于將子層組 (t)中心的平面波移置到父層組 (Pt )的中心 (Ct ), 并通過(guò)內(nèi)插值得到大數(shù)目的平面波 : ? 父節(jié)點(diǎn) (或部分子節(jié)點(diǎn) )在其它處理機(jī)上的節(jié)點(diǎn)構(gòu)成 剩余八叉樹(shù) ,它至多包含 8pL個(gè)子節(jié)點(diǎn) , 因此數(shù)據(jù)交換的量級(jí)為 O(logp+logL) ? 對(duì)壓縮八叉樹(shù)的所有節(jié)點(diǎn) (包括剩余節(jié)點(diǎn) )應(yīng)用并行聚合算法 ,因此每個(gè)處理機(jī)的計(jì)算量為 O(N / p+L) ? 后序遍歷保證父節(jié)點(diǎn)在子節(jié)點(diǎn)之后 , 且緊挨子節(jié)點(diǎn)存儲(chǔ) , () p tintj k C xptnxPF v e???? ?kk57 轉(zhuǎn)移 ? 對(duì)于每一層的盒子 , 其遠(yuǎn)場(chǎng)作用只需要考慮次相鄰組中心間的作用 , 即轉(zhuǎn)移 . 假設(shè)組 (Pt )和 (Ps )的中心分別為 (Ct ,Cs), 則 : ? 在第一次迭代時(shí) , 若相互作用表列中的次相鄰組中心不在同一處理機(jī) , 則通過(guò) MPI_Alltoall發(fā)送到各個(gè)相應(yīng)的處理機(jī) ? 按照上面的公式計(jì)算時(shí) ,通過(guò) MPI_Alltoall接收次相鄰組的平面波 ? 對(duì)于壓縮八叉樹(shù) , 次相鄰組的盒子大小可能不一樣 , 即插值取樣點(diǎn)數(shù)可能不同 , 因此需要將取樣點(diǎn)少的平面波轉(zhuǎn)換為取樣點(diǎn)多的 ()( ) ( ) ( , )rtp p pr t L r tP NF PG F T C C????k k k58 發(fā)散 ? 發(fā)散過(guò)程是聚集過(guò)程的逆操作 , 對(duì)于每一層的每個(gè)盒子 , 發(fā)散相當(dāng)于將父層組 (Pr)中心的平面波移置到子層組 (r)的中心 (Ct ), 并通過(guò)外插值得到小數(shù)目的平面波 ,并結(jié)合求和得到遠(yuǎn)場(chǎng)作用 : ? 父節(jié)點(diǎn) (或部分子節(jié)點(diǎn) )在其它處理機(jī)上的節(jié)點(diǎn)構(gòu)成剩余八叉樹(shù) ,它至多包含 8pL個(gè)子節(jié)點(diǎn) , 因此數(shù)據(jù)交換的量級(jí)為 O(logp+logL) ? 對(duì)壓縮八叉樹(shù)的所有節(jié)點(diǎn) (包括剩余節(jié)點(diǎn) )應(yīng)用并行發(fā)散算法 ,因此每個(gè)處理機(jī)的計(jì)算量為 O(N / p+L) ? 由于后序遍歷能保證父節(jié)點(diǎn)在子節(jié)點(diǎn)之后 , 且緊挨子節(jié)點(diǎn)存儲(chǔ)因此采用反向遍歷后序存儲(chǔ)的樹(shù)節(jié)點(diǎn) , () p mrpj k x Cf ar pm p rV j k w G e ???? ? kk k59 計(jì)算流程 網(wǎng)格剖分與幾何信息讀入 最細(xì)層的近場(chǎng)信息 聚集（內(nèi)插值） 近場(chǎng)矩陣計(jì)算 近場(chǎng)作用 轉(zhuǎn)移 (次相鄰組 ) 矩量法離散 迭代法求解 向量運(yùn)算 矩陣 向量乘積 BLAS, LAPACK 構(gòu)造分布式八叉樹(shù) 發(fā)散（外插值） 各層的遠(yuǎn)場(chǎng)信息 遠(yuǎn)場(chǎng)作用 預(yù)條件子 線性方程組 電磁場(chǎng)積分方程 60 THANKS