西電新技術(shù)講座課程大作業(yè)-并行核外矩量法

1、新技術(shù)講座課程大作業(yè)報告 并行核外矩量法學(xué) 院： 電子工程學(xué)院 專 業(yè)： 電磁場與無線技術(shù) 班 級： 1302061 學(xué) 號： 姓 名： 電子郵件： 日 期： 2016 年 06 月 21日成 績： 指導(dǎo)教師： 張玉 摘要本文先簡要介紹并行核外計算的發(fā)展現(xiàn)狀與并行計算的核心思想及其評估方法中加速比的概念，再詳寫核內(nèi)LU分解的推導(dǎo)過程并由此推廣到并行核內(nèi)LU分解，最后引出并行核外LU分解算法。并行核內(nèi)矩量法與并行核外矩量法比較是本文核心，以求導(dǎo)體球的散射模型為例，比較并行核內(nèi)矩量法與并行核外矩量法，發(fā)現(xiàn)并行核外矩量法比并行核內(nèi)矩量法填充階段時間消耗多2-3倍，并且二者的加速比均不理想。同時也發(fā)現(xiàn)

2、并行核外矩量法在填充階段所消耗的時間比并行核內(nèi)矩量法多了不到一倍，結(jié)合在大規(guī)模電磁計算中計算機內(nèi)存的重要性，得出并行核外矩量法在大規(guī)模計算中以少量的的額外時間消耗換來計算機內(nèi)存的合理利用的結(jié)論。總而言之，為了突破計算機內(nèi)存大小的限制，并行核外矩量法為實際的工程電磁計算提供了一種綜合效率較高的選擇方案。關(guān)鍵詞：并行核外矩量法 加速比 計算機內(nèi)存 工程電磁計算 一、 并行核外計算發(fā)展現(xiàn)狀計電磁學(xué)發(fā)展至今，應(yīng)用范圍越來越廣，近些年來更是在電大尺寸平臺中得到了快速發(fā)展。由于電大尺寸平臺下所解決的問題復(fù)雜，研究目標不論是形狀還是環(huán)境都很繁雜。在采用矩量法分析后，雖然可以得到很高的精度，但卻面臨著龐大的矩

3、陣規(guī)模。引入機群處理后，設(shè)計并行計算來處理需要很大的內(nèi)存，種種原因的折衷結(jié)果就是引入核外空間存儲該矩陣，然后分塊讀取和處理，最后計算出所需的各類參數(shù)，引出目標體相應(yīng)的特性。二、并行計算2. 1并行計算簡介并行計算（parallel computing）是將某一個運算任務(wù)進行分解，然后將分解后所得的子任務(wù)交給各個很多處理器進行運算處理。在運算過程中，每個處理器之間實時進行數(shù)據(jù)通信和協(xié)同運算，并完成了子任務(wù)。在這一基礎(chǔ)上，整個運算的速度大大提高，求解計算速度效率顯著增強，計算的規(guī)模可以成倍增加。通過并行計算的定義可以看出，并行計算至少需要兩臺以上的計算機同時運行，且每臺計算機之間可以實時進行數(shù)據(jù)交

4、換；待處理的運算任務(wù)可以被劃分成多個子任務(wù)，并且，每個子運算任務(wù)可以并行在各個計算機處理器上同時計算，還要有固定的程序?qū)Ω鱾€處理器上的數(shù)據(jù)編程處理，匯總運算結(jié)果，最終達到并行計算的目的。2.2并行算法評估評估手段有很多，這里重點介紹加速比的概念：在處理器資源獨享的情況下，單個處理器進行計算所需的時間比多個處理器在相同環(huán)境下處理同一個任務(wù)時所需時間的比值，稱為加速比公式定義為加速比（P個處理器）：（2-1）其中是指單個處理器完成真?zhèn)€運算任務(wù)所需的時間，是指P個處理器在并行算法下運算同一個任務(wù)所需要的時間。三、并行核內(nèi)與核外LU分解3.1矩陣方程我們首先關(guān)注小型運算問題。并行計算的數(shù)值分析，包括設(shè)

5、計矩量法（MOM）時需要進行的矩陣填充和其后的矩陣分解，也涉及核內(nèi)或者核外的問題。 在使用并行路兩發(fā)程序進行電磁場積分方程的運算時，執(zhí)行過程中會產(chǎn)生如下的矩陣方程： （3-1） 其中，A為M*M的矩陣，且M和未知量相關(guān)，當索要計算的目標模型和跑分的尺寸確定后，未知數(shù)是能夠計算出來的，A表示阻抗矩陣；X為M*1的向量，時所需要求解的電流矩陣（向量）；B也是M*1的向量，表示在激勵電磁波或者所加載激勵源作用下模型表面產(chǎn)生的電壓矩陣。 求解過程中如果A矩陣的規(guī)模太大，計算機內(nèi)存RAM存儲不下，也就處理不了，所以需要將硬盤的空間開辟出來用以存儲這個巨大規(guī)模的矩陣，也就是之前提及的核外技術(shù)。這種和外處理

6、方式放在并行環(huán)境下結(jié)合矩量法處理電磁場計算問題，就是本論文所需要討論的采用并行核外MOM方法求解電磁場積分方程的問題。存儲問題依靠核外技術(shù)加以解決，求解矩陣方程的問題，由于所產(chǎn)生的矩陣是稠密矩陣，所以在這里選用直接求解的LU分解技術(shù)。因為LU方法起源于核內(nèi)算法，所以下面將逐步介紹LU分解過程中矩陣的填充分布和求解方法。3.2核內(nèi)LU分解 求解式（3-1）的方程，需要先將A矩陣進行LU分解。這是非常重要的矩陣求解方法之一，LU分解是將A矩陣分解為兩個三角矩陣的乘積，這兩個矩陣分別為上三角矩陣和下三角矩陣，如圖所示。分解方法很多，最知己的方法是每次將下三角矩陣的某一行和上三角矩陣的某一列填充到內(nèi)存

7、中：圖3.1 核內(nèi)LU分解步驟 式3-1可以表示為 （3-2）第一次填充時 （3-3） （3-4）進行到第r次時因為 (3-5)所以可以得出 （3-6）可以總結(jié)出：U矩陣的計算中，進行到第r行時，其第j個元素需要用該元素本值減去兩個向量的乘積。它們的一個向量為U矩陣中第1行到第r行的第j列元素，另一個向量是L矩陣中第一列到第r列的第r行元素。 同樣地，可以得出 （3-7）式（3-7）表示：L矩陣的第i行計算中，其第r個元素也需要用該元素本值減去兩個向量的乘積，然后除以。其中的一個向量是L矩陣中第一行到第i行的第i列元素，另一個向量是U矩陣中第1列到第r列的第r列元素。 上述的LU分解完成后，式

8、（3-1）表示的矩陣方程變?yōu)椋?（3-8）其中： （3-9） (3-10) 上面兩個矩陣方程（3-9）和（3-10）的求解過程比較簡單，計算速度也很快。 如果計算（3-1）所示的矩陣方程時，A矩陣過于巨大，可以講A矩陣分塊，然后對分塊后的A矩陣進行塊LU分解。所以式（3-1）可以表示成 （3-11）其中，,都是K*K矩陣；0是空矩陣。于是可以得到下面的矩陣方程： （3-12） （3-13） （3-14） 其中，每一個分塊矩陣的計算可以根據(jù)前面（3-3）到（3-10）所述的方法進行LU分解。當然A矩陣也可以分成很多塊，而不止上面所討論的4塊，原理是相同的。LAPACK提供了求解式（3-1）矩陣方

9、程的連續(xù)算法，在對上面所討論的核內(nèi)LU算法進行并行擴展或，可以在并行計算機群眾獲得高性能，即為并行核內(nèi)LU分解。如果對CPU之外的硬盤區(qū)加以利用，即可成為并行核外LU分解，下面將以并行核內(nèi)LU分解為基礎(chǔ)，簡要介紹并行核外LU分解。3.3 并行核外LU 分解3.3.1核外算法 所謂核外技指的是將數(shù)據(jù)先放在硬盤上，等用的時候再讀取出來，每次一點，分批進行，處理完后再寫入硬盤，等用的時候重復(fù)前面的步驟。而核外算法就是基于核外技術(shù)設(shè)計的算法結(jié)構(gòu)，其主要目的是處理一些超大規(guī)模矩陣方程，不論是直接求解（例如LU分解），或是間接求解（例如迭代解）都需要超大內(nèi)存，甚至達到TB級別，給算法的設(shè)計和程序的編寫調(diào)試

10、帶來諸多不便。又由于硬盤相對比較廉價，因此使用硬盤代替內(nèi)存來存儲計算過程中所產(chǎn)生的超大規(guī)模矩陣顯得十分必要，將開發(fā)成本降到可以接受的范圍。 核外技術(shù)由于純運算速度快，所以大部分時間都浪費在了數(shù)據(jù)存儲和交換上。希望隨著算法的不斷優(yōu)化，存儲交換技術(shù)的不斷進步，將來內(nèi)存和硬盤之間數(shù)據(jù)的交換變的越來越快，促使看、核外算法進一步完善。 3.3.2 核外存儲 核外存儲是按照數(shù)據(jù)所占空間大小對矩陣分塊完成的，如圖3.2所示圖3.2核外存儲矩陣劃分單核運行時，核外矩陣填充可以輕松地完成。然而，當多個核進行運算時，核外的填充是一塊一塊地進行分布式填充，這樣矩陣的填充就被設(shè)計成上面的模式，以便避免多余的運算而得到

11、更好的并行效率。3.3.3核外LU分解假設(shè)核外矩陣的填充完成后，進而需要進行的操作及時和外LU分解，當前的理論普遍認為，矩陣相乘運算最有計算方法是通過矩陣分塊形式來完成的。 參照式（3-1），通過LU所分解矩陣元素的分布形成和其相應(yīng)的乘法法則將核外LU分解為兩種形式，left-looking和right-looking。如圖所示：圖3.3 left-looking LU分解圖3.4 right-looking LU分解圖3.3和圖3.4分別描繪兩個3*3矩陣塊運用LU算法是其數(shù)據(jù)是如何入到內(nèi)存進行處理的，其中陰影部分代表將要讀入內(nèi)存進行計算的行或者列。圖 中列的計算需要用不到之前的LU分解得到

12、的列：圖 中行和列的計算后需要更新右下角.如此進行，使用兩個LU分解形式，最終都將得到整個矩陣的分解結(jié)果，從而實現(xiàn)核外算法。 left-looking和right-looking兩種形式得核外LU分解方法相比，從運算時讀取和寫入的數(shù)據(jù)來看，left-looking的相對較少。因此大多數(shù)情況下用left-looking形式的LU分解方法，而且在矩陣寫入硬盤之前阻抗矩陣是經(jīng)過主元確定處理的。 left-looking核外LU分解用到的有BLAS庫中的GEMM函數(shù)和LAPACK庫中的GETRF函數(shù)。如果要進行并行核外的LU分解，其函數(shù)得到ScaLAPACK庫中的PxGETRF等，同時得調(diào)用LAREA

13、D函數(shù)和LAWRITE函數(shù)進行讀寫。四、并行核外矩量法相比于并行核內(nèi)矩量法的優(yōu)越性 我們所研究的并行核外矩量法，顧名思義，包含并行與核外兩個關(guān)鍵點，并行計算的速度要大于單核計算的速度，但是核外矩量法真的要優(yōu)于核內(nèi)矩量法嗎？或者說它有多大的優(yōu)越性，下面我們將用一個例子進行比較4.1 導(dǎo)體球體的散射 自由空間中有如圖所示的半徑1m的導(dǎo)體球，在600MHz的平面波激勵下，計算其雙站RCS。入社電磁平面波為，且該球面破分為9.812個三角形，未知數(shù)有14.718個。并行核外矩量法（OC）和并行核內(nèi)矩量法（IC）的RCS結(jié)果與Mie級數(shù)的解析結(jié)果對比如圖 和圖 所示，可見三個結(jié)果幾乎完全吻合，驗證了兩種

14、并行算法的正確性。圖4.1 導(dǎo)體球模型及電磁平面波圖4.2半徑1m導(dǎo)體球核內(nèi)外算法XOZ面散射場對比4.2不同塊大小的測試在并行LU分解算法中，為了實現(xiàn)負載均衡，需要將矩陣采用快循環(huán)方式存儲。塊的大?。˙lockSize）將影響矩陣讀寫速度，從而影響算法的計算速度。在核內(nèi)算法中，塊大小影響內(nèi)存讀寫矩陣的速度；而在核外算法中，塊大小影響文件讀寫矩陣的速度。對于導(dǎo)體球模型，在4*6=24核內(nèi)進程網(wǎng)格情況下，測試不同塊大小時的計算時間。根據(jù)圖4.3和4.4所示，課件不論是核內(nèi)的計算時間還是核外的計算時間都在塊大小取128時達到最小值，因此本例后續(xù)計算中均將塊大小設(shè)置為128進行測試圖4.3 并行核內(nèi)

15、塊大小測試結(jié)果圖4.4并行核外塊大小測試結(jié)果4.3進程網(wǎng)格的測試 在并行LU分解算法中，將所有進程排列成二維的錦城網(wǎng)格（Process Grid）。不同的進程網(wǎng)格計算效率可能有很大差別。同樣以導(dǎo)體球為例，將塊大小設(shè)置為128，取總核數(shù)為24。將24個核分成不同的進程網(wǎng)格進行測試，如圖4.5和4.6所示。可見當錦城網(wǎng)格接近正方形時，核內(nèi)程序和核外程序的計算時間都是最少的。當進程網(wǎng)格偏離正方形時，核內(nèi)和核外程序時間都會增大。因此本文后續(xù)的算例中，錦城網(wǎng)格都盡量趨于正方形。圖4.5并行核內(nèi)進程網(wǎng)格測試結(jié)果圖4.6并行核外進程網(wǎng)格測試結(jié)果4.4不同核數(shù)的測試 除了塊大小和進程兩個因素之外，并行程序中需

16、要設(shè)置的最重要的參數(shù)就是核的總數(shù)。對于上述代替求模型，采用最優(yōu)的分塊大小和合適的而為進程網(wǎng)格進行測試，計算時間如下表4.1所示。 從表4.1中可以看出：（1）在矩陣填充階段，并行核外矩量法的時間比并行核內(nèi)矩量法多幾倍。隨著核數(shù)增加，兩種方法消耗的時間都在減少。注意到核內(nèi)算法的加速比達不到理想的加速比，而核外算法的加速比更低，這表明兩種并行算法都還需要進一步優(yōu)化。（2）在矩陣LU分解階段，并行核外矩量法的時間仍然比并行核內(nèi)矩量法所用時間長，但是前者最多比后者多0.9倍。核外算法的這種額外開銷在工程實踐中是可以接受的。表4.1導(dǎo)體球核內(nèi)外時間對照表4.5內(nèi)存的對比一般情況下并行核內(nèi)矩量法所需內(nèi)存較

17、大，并行核外矩量法的所使用內(nèi)存較小。如表4.2所示，由于并行核內(nèi)矩量法只是用內(nèi)存，則可以算出計算導(dǎo)體球時其存儲所需內(nèi)存為3305.4MB，然后對參加計算的每個處理器評分：并行核外矩量法因為使用了硬盤替代內(nèi)存故而對內(nèi)存的需求較少。表4.2每個處理器/進程的內(nèi)存需求 可以明顯看出稟性和外巨量法中每個處理器所需的內(nèi)存遠遠小于使用相同核數(shù)進行計算導(dǎo)體球時稟性和內(nèi)巨量法所需的內(nèi)存，這是因為并行核外矩量法使用了硬盤代替了內(nèi)存來存儲矩陣元素，而且每次填充或者求解時最多讀取兩列子塊，相對應(yīng)的并行核內(nèi)矩量法則需要在內(nèi)存中一次性存儲所有的元素并進行求解。4.6 并行核外矩量法相比于并行核內(nèi)矩量法的優(yōu)越性本節(jié)通過對

18、導(dǎo)體球的并行核內(nèi)矩量法和并行核外矩量法欲望不同矩陣規(guī)模下的測試結(jié)果和Mie級數(shù)對比驗證了并行算法的正確性。然后通過相同核數(shù)下不同塊大小的測試證實了分塊的最優(yōu)大小，在依照最優(yōu)分塊大小及相同的核數(shù)下采用不同的二維進程網(wǎng)格測試發(fā)現(xiàn)，最合適的進程網(wǎng)格應(yīng)該接近于正方形。在對導(dǎo)體球在不同核數(shù)的測試下發(fā)現(xiàn)，大量的時間消耗在了矩陣填充階段，矩陣LU分解階段的時間消耗相比較少。最后還分析了并行核外矩量法相比并行核內(nèi)矩量法在內(nèi)存使用上的優(yōu)點，因為算法設(shè)計不同，前者使用的內(nèi)存大大少于后者。又因為實際的科學(xué)實踐核工程應(yīng)用中資源的限制，并行核外矩量法以少量的的額外時間消耗換來資源的合理利用是十分具有意義的。五、并行核外矩量法總結(jié)本文主要按照我對并行核外矩量法的認識的過程寫來，先寫并行核外計算的發(fā)展現(xiàn)狀，并簡要介紹并行計算，再詳寫核內(nèi)LU分解的推導(dǎo)過程并由此推廣到并行核內(nèi)LU分解，并行核外LU分解算法。最后的并行核內(nèi)矩量法與并行核外矩量法比較是本文核心，以求導(dǎo)體球的散射模型為例，比較并行核內(nèi)矩量法與并行核外矩量法，發(fā)現(xiàn)并行核外矩量法比并行核內(nèi)矩量法填充階段時間消耗多2-3倍，隨著核數(shù)的增加二者的填充時間都變小了，然而二者的