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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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