針對SMP集群系統採用MPI和OpenMP混合併行提高計算速度的方法
2023-08-02 21:48:36
針對SMP集群系統採用MPI和OpenMP混合併行提高計算速度的方法
【專利摘要】本發明公開了一種針對SMP集群系統採用MPI和OpenMP混合併行提高計算速度的方法，根據計算節點數目和節點內可用CPU核數確定可調用的MPI進程數和OpenMP線程數；每個進程讀入已有子稀疏矩陣、子初始向量、塊向量和最大計算公差；每個進程開啟多線程編譯指令；在各個進程上進行預條件共軛梯度法的循環計算，循環計算中的OpenMP柵障僅有三個；若計算的誤差小於允許值，循環結束，否則繼續循環；歸約各個進程的計算結果，輸出問題的解；並行計算時，首先MPI進程啟動，對問題進行多進程分解，開始節點間的並行，每個MPI進程被分配到一個計算節點上，進程間使用消息傳遞交換信息；然後在每個MPI進程中，使用OpenMP制導指令創建一組線程，並分配到計算節點的不同處理器上並行執行。
【專利說明】針對SMP集群系統採用MPI和OpenMP混合併行提高計算速 度的方法
【技術領域】
[0001] 本發明涉及一種並行計算技術，具體地說，涉及一種並行計算提高計算速度的方 法。
【背景技術】
[0002] 迭代法是目前求解大型稀疏線性方程組的主流方法，迭代法中的預條件共軛梯度 法是通過預處理技術減少共軛梯度法的迭代次數，並能加速收斂的一種方法，在工程和科 學計算中已有廣泛的應用。共軛梯度法是求解特定線性系統的數值解的方法，其中的係數 矩陣為對稱和正定的實數陣。隨著科學與工程問題的規模和複雜程度的提高，串行共軛梯 度法已經很難滿足對稀疏線性系統的求解規模和速度的要求。
[0003] 由於串行計算本身存在的瓶頸，當計算量相對較大，計算機本身的性能將大大制 約其進行演算的效率。現有技術中採用串行方法計算共軛梯度法，僅在處理稀疏矩陣向量 乘時才啟用MPI，通過在各節點上計算分塊稀疏矩陣與分塊向量的乘積實現並行計算。但共 軛梯度法除了稀疏矩陣向量乘，還有多個向量與向量、標量與向量的乘積和求和，以及線性 方程組求解等計算步驟，這些計算仍然使用串行方法計算，不能最大限度地將算法並行優 化。對於分布式和共享式存儲結構混合的SMP集群系統，難以充分利用計算資源，提升其計 算速度。
【發明內容】
[0004] 本發明的目的在於提供一種針對SMP集群系統採用MPI和OpenMP混合併行提高 計算速度的方法，通過利用集群以及多核平臺的優勢，提升共軛梯度法的計算速度，滿足對 稀疏線性系統的求解規模和速度的要求。
[0005] 為了實現上述目的，本發明所採用的技術方案如下：
[0006] 一種針對SMP集群系統採用MPI和OpenMP混合併行提高計算速度的方法，包括以 下步驟：
[0007] ( 1)計算準備
[0008] a)啟動MPI多進程計算，其中進程數小於或等於可用計算節點數目；
[0009] b)每個進程讀入子稀疏矩陣A、子初始向量Xtl、塊向量b和最大計算公差 Tolerance，子稀疏矩陣A、子初始向量Xtl和塊向量b是通過網格劃分軟體劃分問題的計算 域後生成；
[0010] (2)開始預條件共軛梯度法的MPI+OpenMP並行的循環計算 [0011] 1)根據初始值X。，計算r=b_Ax。；
[0012] 2)p = M_1r ；
[0013] 3) P = rTp ；
[0014] 4)每個進程開啟OpenMP多線程編譯指令，其中線程數小於或等於該線程所處計 算節點可用CPU核數目：
[0015] #pragmaompparalIel {/* 開始 OpenMP 線程 */
[0016] 5) fori=l, 2,...... /* 開始循環 */
[0017] 6) #pragmaompparalIelforreduction (+: α){
[0018] 7) q = Ap /*稀疏矩陣向量乘*/
[0019] 其中，具體包括以下步驟：
[0020] ①多線程並行計算行循環：按行順序，i從0循環到稀疏矩陣最後一行。其中：
[0021] a)預先讀取子稀疏矩陣A第i行的數據，存到向量tmp中；
[0022] b) j從0循環到第i行非零值結尾。其中：
[0023] i. k=第i行第j個非零值的列指數；
[0024] ii. q[k]=tmp[j]*+q[k]。
[0025] ②MPI非阻塞通信交換各節點的q。
[0026] 8) a = pTq /* 向量內積 */
[0027] 9)}
[0028] 10) α = p / α
[0029] 11) ρ〇ω= ρ
[0030] 12) #pragmaompparallelforreduction (+: P , error){
[0031] 13) x = x+ a p /*AXPY*/
[0032] 14) r = r-a q /*AXPY*/
[0033] 15) q = IVT1!· /* 向量內積 */
[0034] 16) q = rTq /* 向量內積 */
[0035] 17) error = rTr /* 向量內積 */
[0036] 18) }
[0037] 19) β = P / P old
[0038] 20) #pragmaompparallelfornowait {ρ = q+βρ} /*AXPY*/
[0039] 21) #pragmaompsingle{MPI_A1lgather(error);
[0040] 22) If (error<tolerance)break}
[0041] 23) } /*結束for循環和OpenMP多線程計算*/
[0042] (3)各計算節點的計算結果歸約後得到最終計算結果。
[0043] 並行計算時，首先MPI進程啟動，對問題進行多進程分解，開始節點間的並行，每 個MPI進程被分配到一個計算節點上，進程間使用消息傳遞交換信息；然後在每個MPI進程 中，使用OpenMP制導指令創建一組線程，並分配到計算節點的不同處理器上並行執行。
[0044] 進一步，所述網格劃分軟體可為Metis或ParMetis。
[0045] 進一步，開啟MPI多進程計算和OpenMP多線程計算後，能夠針對多核SMP集群多 核、多節點的硬體資源特性，實現計算節點間和計算節點內的兩級並行。
[0046] 進一步，並行計算執行過程中，計算節點間（即進程間)通過MPI消息傳遞方式通信 數據，在計算節點內（即進程內）通過OpenMP線程組的共享內存方式實現數據共享。
[0047] 進一步，每一子稀疏矩陣的存儲格式為CSR。
[0048] 進一步，並行計算執行過程中，可以訪問的存儲空間分為三級存儲空間，進程控制 的處理器全局共享第一級存儲空間，線程組共享第二級存儲空間，線程私有第三級存儲空 間。
[0049] 進一步，預條件共軛梯度法的1^1+0?6111^並行的循環計算中只有第6)、12)和21) 這三步存在OpenMP柵障，各線程計算到OpenMP柵障時需要等待所有線程計算到這一步才 能進行下一步的計算。
[0050] 與現有技術相比，本發明融合了消息傳遞模型和多線程並行編程模型的優點，更 好地解決每個計算節點內各個處理器間的交互，充分利用計算資源，減少算法中的OpenMP 柵障數目，減少了多線程計算中的同步，提高了預條件共軛梯度法的計算速度。
【專利附圖】
【附圖說明】
[0051] 圖1為本發明的編程模式示意圖；
[0052] 圖2為本發明的流程步驟示意圖；
[0053] 圖3為本發明的稀疏矩陣向量乘的示意圖。
【具體實施方式】
[0054] 下面結合附圖和具體實施例對本發明針對SMP集群系統採用MPI和OpenMP混合 並行提高計算速度的方法作進一步說明。
[0055] 高性能計算機（HPC)按其存儲結構可分為共享存儲結構和分布存儲結構兩大類。 分布式存儲系統沒有一個統一的內存空間，其中的一個或多個處理器和它們的內存空間構 成一個獨立的系統，多個系統由一個作業系統控制，可以獨立運行。每個系統叫作節點，這 些節點使用網絡接口相互連接進行通信。共享式存儲系統多為對稱式共享存儲體系結構， 又叫對稱多處理器結構（SymmetricMulti-Processing，SMP)。伺服器中多個CPU對稱工作， 無主次或從屬關係。各CPU共享相同的物理內存，每個CPU訪問內存中的任何地址所需時 間是相同的，因此SMP也被稱為一致存儲器訪問結構（UMA，UniformMemoryAccess)。SMP集 群系統可以看成是這兩種內存結構的集合，它由擁有多個處理器的SMP節點和連接各節點 間的高速網絡組成一套多級體系結構。SMP集群即有分布式節點系統的良好擴展性，也支持 共享式存儲系統的數據共享。因此當前以SMP集群為代表的高性能計算機發展迅速，成為 高性能計算機領域的主流。
[0056] 不同存儲結構的高性能計算機有相應的並行編程模型，其中一種是基於消息傳遞 模型，一般應用於分布式存儲結構，也可用於共享式存儲結構。通過將計算任務或數據按照 進程數劃分，各個並行執行的任務之間通過傳遞消息來交換信息、協調步伐、控制執行。其 中，MPI (messagepassinginterface)是為開發基於消息傳遞模型的並行程序而制定的工 業標準。另一種是基於共享存儲的多線程並行編程模型。OpenMP是其中的共享存儲並行編 程的典型方法，能提供描述並行區域的編譯製導語句並隱藏有關並行線程創建和管理的細 節，是一種能顯式指導多線程、共享內存並行的應用程式編程接口（API)。OpenMP標準化了 細粒度的並行性，同時也支持粗粒度的並行性。
[0057] 本發明採用MPI和OpenMP混合編程模型，將分布式存儲編程模型MPl、共享存儲編 程模型OpenMP相結合，充分利用SMP集群層次存儲結構的特點。本發明的MPI和OpenMP 混合編程模型具有的層次結構為上層的MPI表示節點間的並行，下層的OpenMP表示節點內 的並行。本發明的MPI和OpenMP混合編程模型基於如下的理論分配模型：首先對問題進行 MPI分解，將任務劃分成通信不密集的幾個部分，每個部分分配到一個SMP節點（即一個進 程）上，節點間通過消息傳遞進行通信；然後添加 OpenMP編譯製導語句將每個節點上的部 分再次分解，並分配到SMP的不同處理器上由多個線程並行執行，節點內通過共享存儲進 行通信。MPI和OpenMP混合編程模型提供了節點間和節點內的兩級並行機制，結合了進程 級的粗粒度並行）和循環級的細粒度並行。
[0058] 集群系統是由一組計算機系統（節點）通過高性能網絡或區域網互連而形成的具 有單一系統映像的高可用、高性能、高可擴展性的計算機集群系統。運行在機群系統上的並 行程序將其計算任務分割成若干並行的子任務，並分配給每個計算節點執行。根據並行程 序算法需求，在某些子任務間存在保序關係，因此需要進行同步處理。
[0059] 柵障（Barrier)是同步機制的一種，被廣泛應用於機群系統。Barrier操作是並行 程序的同步點，並行程序要等待所有參與其中的計算節點都到達這個同步點後，才能執行 後續操作。共同完成一個計算任務的所有計算節點，通過某種拓撲網絡，互連形成一棵在邏 輯上有根的Barrier樹。當Barrier樹中的計算節點到達Barrier同步點後就停止執行其 他操作，直到它被通知Barrier樹中的所有計算節點都已到達同步點，Barrier同步完成， 計算節點才能夠繼續處理其它任務。Barrier同步完成的時間取決於Barrier樹中最後一 個達到Barrier同步點的計算節點，Barrier同步的延時定義為從最後一個計算節點達到 Barrier同步點到Barrier樹中所有計算節點都被通知到Barrier同步完成所需的時間。 在接收到Barrier完成通知前，Barrier樹中所有提前到達Barrier同步點的計算節點都 處在空閒等待狀態，降低了並行系統的性能，因此降低Barrier同步延時對提高並行系統 的性能有重要作用。
[0060] 現有的採用MPI和OpenMP混合編程模型的預條件共軛梯度法求解算法如下：
[0061] (1)計算準備
[0062] a)啟動MPI多進程計算，其中進程數小於或等於可用計算節點數目。
[0063] b)每個進程讀入子稀疏矩陣A、子初始向量Xtl、塊向量b和最大計算公差 Tolerance，子稀疏矩陣A、子初始向量Xtl和塊向量b是通過網格劃分軟體劃分問題的計算 域為子計算域後生成。
[0064] (2)開始預條件共軛梯度法的MPI+OpenMP並行的循環計算
[0065] 1)根據初始值X。，計算r=b_AxQ。
[0066] 2)每個進程開啟OpenMP多線程編譯指令，其中線程數小於或等於該線程所處計 算節點可用CPU核數目。
[0067] 3)開始 fori=l, 2,…循環。
[0068] 4) #pragmaompfor 指令多線程並行計算 Z=IVT1I^
[0069] 5) #pragmaompfor 指令多線程並行計算 P
[0070] 6) #pragmaompsingle指令單線程進行MPI通信，MPI_Allreduce函數歸約各計算 節點的P η。
[0071] 7) ifi=l β =Oelse β = P h/ P 卜2。
[0072] 8)#pragmaompfor 指令多線程並行計算 ρ=ζ+β p。
[0073] 9) #pragmaompfor指令多線程並行計算q=Ap。
[0074] 10) #pragmaompfor 指令多線程並行計算 α =ρ η/ρ、。
[0075] 11) #pragmaompreduction 指令多線程並行計算 χ=χ+α p。
[0076] 12) #pragmaompreduction 指令多線程並行計算 r=r_ a q。
[0077] 13)#pragmaompsingle指令單線程進行MPI_Allreduce歸約各計算節點r的範數。
[0078] 14) if,循環迭代終止；elsegoto3)。
[0079] 15) end/*結束for循環和OpenMP多線程計算*/。
[0080] (3)各計算節點的計算結果X歸約後得到最終計算結果，得到最終的線性方程組 的解X，輸出線性方程組的解X。
[0081] 可以看出，上述算法共有9步OpenMP的#pragmaomp指令，每一步都有OpenMP柵 障（Barrier)，程序必須等待所有線程都達到同一柵障才能進行下一步。如果各線程計算量 不一樣，各線程將不能同時達到柵障，程序執行會大大延緩。所以，優化算法，減少OpenMP 柵障將會提高計算效率。
[0082] 本發明通過將和設置成線程局部變量，可以消除全局通信，這樣線程執行到和的 賦值時無需等待其它線程，可以直接執行下一步計算，因此減少了 OpenMP柵障。
[0083] 本發明公開了一種基於MPI和OpenMP混合編程模型並行計算提高計算速度的方 法，包括以下步驟：
[0084] 根據計算節點數目和節點內可用CPU核數確定可調用的MPI進程數和OpenMP 線程數；每個進程讀入已有子稀疏矩陣A、子初始向量Xtl和塊向量b和最大計算公差 Tolerance ;每個進程開啟多線程編譯指令；在各個進程上進行預條件共軛梯度法的循環 計算；若計算的誤差小於允許值，循環結束，否則繼續循環計算；歸約各個進程的計算結 果，輸出問題的解；並行計算時，首先MPI進程啟動，對問題進行多進程分解，開始節點間的 並行，每個MPI進程被分配到一個計算節點上，進程間使用消息傳遞交換信息；然後在每個 MPI進程中，使用OpenMP制導指令創建一組線程，並分配到計算節點的不同處理器上並行 執行。
[0085] 開啟多線程時，每一進程可開啟的線程數小於或等於該進程的可用處理器數。每 一子稀疏矩陣的存儲格式為CSR (CompressedSparseRow)。其中，程序在預條件共軛梯度 算法循環開始前動態確定可用線程數，開啟OpenMP多線程，在循環中根據需要調用不同 OpenMP多線程指令，如for循環指令、reduction指令、single指令等。並行計算執行過程 中，可以訪問的存儲空間分為三級存儲空間：進程控制的多核微處理器全局共享第一級存 儲空間，線程組共享第二級存儲空間，線程私有第三級存儲空間。線程組共享的第二級存儲 空間在共軛梯度循環前創建，將當前預條件共軛梯度算法函數內的變量空間作為線程組的 共享的第二級存儲空間，線程組內的每個線程均能訪問這一空間，但其它線程組不能訪問。 同時，每個線程會被分配一個只有線程才能訪問的私有的第三級存儲空間，該存儲空間具 有所屬線程相同的生命周期。
[0086] 實施例一
[0087] 本實施例採用針對SMP集群系統採用MPI和OpenMP混合併行提高計算速度的方 法求解大規模線性方程組。預條件共軛梯度法是求解對稱正定稀疏矩陣線性方程組的迭代 法，在工程和科學計算中有廣泛的應用，其算法如下所示：
[0088] 取 x(〇) e Rn,計算 r(〇) = b-Ax(〇)，令 p(〇) = r (0)
[0089]對k = 0，1，2, · · ·，計算
【權利要求】
1. 一種針對SMP集群系統採用MPI和化enMP混合併行提高計算速度的方法，其特徵在 於，包括W下步驟： (1) 計算準備 a) 啟動MPI多進程計算，其中進程數小於或等於可用計算節點數目； b) 每個進程讀入子稀疏矩陣A、子初始向量X。、塊向量b和最大計算公差Tolerance， 子稀疏矩陣A、子初始向量X。和塊向量b是通過網格劃分軟體劃分問題的計算域後生成； (2) 開始預條件共輛梯度法的MPI+化enMP並行的循環計算 1) 根據初始值X。，計算r=b-Ax。； 2. P = M-if ; 3. p = fTp ; 4) 每個進程開啟化enMP多線程編譯指令，其中線程數小於或等於該線程所處計算節 點可用CPU核數目： 牠^肖1113011^93腳1161{/*開始化6]11?線程*/ 5. fori=l,2,...... /* 開始循環 */ 6) #pragmaompparallelforreduction (+: a ) { 7. q = Ap /*稀疏矩陣向量乘*/ 其中，具體包括W下步驟： ① 多線程並行計算行循環：按行順序，i從0循環到稀疏矩陣最後一行，其中： a) 預先讀取子稀疏矩陣A第i行的數據，存到向量tmp中， b) j從0循環到第i行非零值結尾，其中： i. k=第i行第j個非零值的列指數， ii. q[k]=tmp[j]*p[k]+q比]， ② MPI非阻塞通信交換各節點的q ; 8. a = pTq /*向量內積*/ 9) } 10. a = p / a 11. P old = P 12) #pragmaompparallelforreduction (+: p, error) { 13. x = x+ap /*AXPY*/ 14. r = r-aq /*AXPY*/ 15. q = M-i;r /* 向量內積 */ 16. q = r^q /*向量內積*/ 17. error = rV /* 向量內積 */ 18) } 19)目=P / P old 20) #pragmaompparallelfornowait(p = q+0p} /*AXPY*/ 21) #pragmaompsingle{MPI_Allgather (error); 22. If (error<tolerance)break} 23) } /*結束for循環和化enMP多線程計算*/ (3)各計算節點的計算結果歸約後得到最終計算結果。 並行計算時，首先MPI進程啟動，對問題進行多進程分解，開始節點間的並行，每個MPI 進程被分配到一個計算節點上，進程間使用消息傳遞交換信息；然後在每個MPI進程中，使 用化enMP制導指令創建一組線程，並分配到計算節點的不同處理器上並行執行。
2. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於：所述網格劃分軟體可為Metis或ParMetis。
3. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於：開啟MPI多進程計算和化enMP多線程計算後，能夠針對多核SMP集群 多核、多節點的硬體資源特性，實現計算節點間和計算節點內的兩級並行。
4. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於：並行計算執行過程中，計算節點間巧P進程間）通過MPI消息傳遞方式 通信數據，在計算節點內（即進程內）通過化enMP線程組的共享內存方式實現數據共享
5. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於：每一子稀疏矩陣的存儲格式為CSR。
6. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於：並行計算執行過程中，可W訪問的存儲空間分為H級存儲空間，進程 控制的處理器全局共享第一級存儲空間，線程組共享第二級存儲空間，線程私有第H級存 儲空間。
7. 如權利要求1所述的針對SMP集群系統採用MPI和化enMP混合併行提高計算速度 的方法，其特徵在於；預條件共輛梯度法的MPI+化enMP並行的循環計算中只有第6)、12)和 21)該H步存在化enMP柵障，各線程計算到化enMP柵障時需要等待所有線程計算到該一步 才能進行下一步的計算。
【文檔編號】G06F9/38GK104461467SQ201310442102
【公開日】2015年3月25日 申請日期:2013年9月25日 優先權日:2013年9月25日
【發明者】羅海飆, 廖俊豪 申請人:廣州中國科學院軟體應用技術研究所