【正文】 j個元素也必須在處理器 P上 14 ? 主要模塊和接口： (1) p*lancs： Lanczos框架接口。 ? 與通信有關(guān)的子程序： (1) mpi_init： MPI初始化子程序 (2) mpi_creat_cart： 創(chuàng)建二維處理器網(wǎng)格通信器 (3) mpi_sub_col： 創(chuàng)建一維行通信器 (4) mpi_sub_row： 創(chuàng)建一維列通信器 ? 與矩陣分布有關(guān)的子程序： (1) mat_2d: 矩陣的二維 塊循環(huán)分布子程序，得到矩陣的數(shù)據(jù) 結(jié)構(gòu)和在二維處理器網(wǎng)格上的分布信息 11 (2) indxg2l： 得到存儲全局矩陣元素（ i, j）的處理器在二 維處理器網(wǎng)格中的邏輯坐標(biāo)（ row_i, col_j） (3) indxg2p： 得到全局矩陣元素（ i, j）在處理器器上的局 部子矩陣中對應(yīng)的元素坐標(biāo) (loc_i, loc_j) (4) mat _ div： 三對角矩陣秩 2劃分。包括： (1) p *gseps：廣義對稱 /厄密特征問題并行求解（選定的特 征值和特征向量） (2) p*sseps: 標(biāo)準(zhǔn)對稱 /厄密特征問題并行求解（選定的特征 值和特征向量） ? 第二層包含特征問題并行求解器所需要的矩陣轉(zhuǎn)換子程序、分解子程序和線性代數(shù)子程序等，主要包括： (1) p*syg2st：廣義實對稱特征問題轉(zhuǎn)化為標(biāo)準(zhǔn)特征問題 (2) p*heg2st：廣義 Hermitian特征問題轉(zhuǎn)化為標(biāo)準(zhǔn)特征問題 (3) p*trsm：并行計算含有多個右端項的實三角矩陣方程組 (4) p*htrsm： 并行計算含有多個右端項的復(fù)三角矩陣方程組 (5) p*sytrd： Householder并行轉(zhuǎn)換對稱矩陣為三對角形式 10 (6) p*hetrd： Householder并行轉(zhuǎn)換 Hermitian矩陣為三對角形式。 稠密和稀疏矩陣存儲分布方式： 2D塊循環(huán) AIJ BAIJ BDIAG matrixfree 其它 稠密矩陣處理 LANCZOS迭代處理 LOBPCG迭代處理 SVD和 PLSQR 分解并行器 求解器 厄密 /對稱稀疏矩陣 特征問題并行求解器 厄密 /對稱稠密矩陣特征問題并行求解器 并行 QR、 LU、 LLT分解 HouseHolder并行轉(zhuǎn)化 特征求解器有關(guān)的線性代數(shù)子程序， 預(yù)條件： ILU AMG 塊 Jacobi等 塊 Jacobi等 不同的譜轉(zhuǎn)換：（ Aδ I） 1 、 M1A、（ Aδ M） M1等 不同的并行正交化、重正交 以及 B正交化等 管理通信、錯誤核查和一些輔助子程序 BLAS LAPACK Sparse Matrixvector MPI OpenMP Multicore User selects a parallel solver 8 軟件包涉及到的主要算法 ? 提出了各類大規(guī)模數(shù)值計算和對稱特征問題有效并行算法和實現(xiàn)技術(shù)。 ? 量子點（ Quantum Dots）中較大規(guī)模稀疏本征問題的并行求解，形成了 2048核的可擴(kuò)展性并行計算； ? HPSEPS已被安裝到中山大學(xué)光電材料與技術(shù)國家重點實驗室的并行計算機(jī)系統(tǒng)上。 隨著計算模型變得越來越復(fù)雜，導(dǎo)致的稀疏矩陣規(guī)模達(dá)到千萬階甚至上億。1 并行軟件庫介紹 趙永華 中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心 超級計算中心 2 主要內(nèi)容 ? 自主并行軟件包 HPSEPS介紹 ? MUMPS并行軟件包介紹 ? hypre并行軟件包介紹 ? Parmetis并行軟件包介紹 ? PETSc并行軟件包介紹 3 自主并行軟件包 HPSEPS 開發(fā)者：趙永華 遲學(xué)斌等 中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心 超級計算中心 4 概述 HPSEPS（ High Performance Symmetric Eigenproblem Software，高性能對稱特征問題軟件）是由中科院計算機(jī)網(wǎng)絡(luò)信息中心 /超級計算中心自主開發(fā)。 ?量子計算中電子結(jié)構(gòu)遇到的特征問題達(dá)到了千萬階以上規(guī)模，有時需要得到幾百個特征對； ?離子加速器產(chǎn)生的大規(guī)模稀疏特征問題可達(dá)到上億階； ?日本 地球模擬器上費(fèi)米 Hubbard模型中遇到的大規(guī)模稀疏特征問題規(guī)模達(dá)到了幾百億階。求解了 光子晶體中 大規(guī)模問題，得到了非常好的效果。 ? 求解稠密特征問題的不同并行塊算法； ? 求解稀疏特征問題的 deflate Lanczos 并行算法； ? 基于最優(yōu)化的各類預(yù)處理并行算法； ? 多級混合并行實現(xiàn)技術(shù)。 (7) p*stebz： 分而治之并行求解實對稱三對角矩陣的特征值。 (5) *get_sub_mat： 得到三對角矩陣秩 2后的子矩陣。其通過調(diào)用不同的模塊，完成矩陣的三對角分解、正交化處理，得到收斂的 Ritz對等。 另外，針對一般性稀疏矩陣結(jié)構(gòu)， HPSEPS提供了稀疏矩陣 向量積的并行求解模塊。 – 確定處理器的二維網(wǎng)格結(jié)構(gòu)，分布矩陣到各處理器（稠密問題）。 ? 稀疏特征問題： 求解問題規(guī)模大約為 190萬，得到 5個最小本征值。比如求解非對稱矩陣的 GMRES和求解對稱矩陣的 CG（包括 PCG, CGNR, BiCGStab）。如有限差分（ FDM） ? 半結(jié)構(gòu)化 （ Sstruct）接口 面向半結(jié)構(gòu) (semistruct)網(wǎng)格離散的應(yīng)用，如局部加密 AMG、塊結(jié)構(gòu)網(wǎng)格上的應(yīng)用 , 如有限差分方法（ FDM） , 有限體積方法（ FVM） ? 基于有限元的無結(jié)構(gòu)界面 （ FEI） 應(yīng)用于有限元（ FEM）得到的線性方程組 ? 基于線性代數(shù)的非結(jié)構(gòu)矩陣界面 （ IJ） 該接口以矩陣方式顯式地表示線性代數(shù)方程組 ,是適用范圍最廣泛的接口。矩陣 A支持 HYPRE 的 ParCSR格式 、 PETSc 的矩陣形式和 ISIS++ Row的矩陣形式。而 PFMG僅使用簡單的點光滑，因此 PFMG的健壯性不如 SMG，但是它在作 V循環(huán)迭代時效率更高 . – BoomerAMG既可作為迭代法 , 也可作為預(yù)條件子 。 HYPRE_StructGridAssemble(grid)。 /* Set up the matrix, righthand side, and initial guess*/ HYPRE_StructMatrixCreate(MPI_COMM_WORLD, grid, stencil, amp。 HYPRE_StructMatrixAssemble(A)。 % 右端向量的初始化 HYPRE_StructVectorSetBoxValues(b, ilower, iupper, bvalues)。 HYPRE_StructVectorInitialize(x)。solver)。 %創(chuàng)建求解器 (PFMG) /* Solve the linear system */ HYPRE_StructPFMGSolve(solver, A, b, x)。 HYPRE_StructStencilDestroy(stencil)。 28 算例 ? 對流 反應(yīng) 擴(kuò)散方程 對流 反應(yīng) 擴(kuò)散 (ConvectionReactionDiffusion)方程 : div (K grad u + B u) + C u = F in Ω, 采用五點差分離散 , 得到方程組 : Au = b, 其中 A = [Aii Aib 。 考慮到邊界條件 u= u0 on ?Ω, 即 ub= u0 . 于是 [Aii 0 。 在 , Ω為單位正方形 , 處理機(jī)網(wǎng)格為 N N，每個處理機(jī)上的網(wǎng)格為 n n, h=1/(Nn+1), 采用結(jié)構(gòu)網(wǎng)格界面和 5點差分離散 , 并考慮邊界條件。 邊界條件 : u0 =(sin(5πx)+sin(5πy))/1000。 ? MUMPS基于多波前方法的直接求解方法。 ?單元格式： 矩陣由主進(jìn)程 (host)集中輸入， 置 ICNTL(5)=1 ICNTL(18)=0 ?組裝格式（ assembled format） – 矩陣由主進(jìn)程 (host)集中輸入 – 結(jié)構(gòu)由主進(jìn)程提供 (analysis) – 元素被分布到各處理器上 (numeric factorization) 34 主要計算步 ? MUMPS計算 Ax=b通過三步完成 : (1)分析 (JOB=1) ? 主進(jìn)程執(zhí)行排序操作 ? 主進(jìn)程執(zhí)行符號分解 (2) A=LU或 A=LDLT分解 (JOB=2) ? A被分布到各處理器 ? 由主進(jìn)程和一個或多個從進(jìn)程對每個波前矩陣進(jìn)行數(shù)值分解 (3) 求解 (JOB=3) ? b由主進(jìn)程分布到各處理器 ? x由分布到各處理器的因子計算得到 ? x被聚集到主進(jìn)程或分布到各處理器 35 主要特性 ? 每個處理階段可獨立調(diào)用 ? 異步通信 使得計算和通信實現(xiàn)了重疊 ? 動態(tài)調(diào)度 算法是自適應(yīng)的，在執(zhí)行時重分布任務(wù)和數(shù)據(jù)到適當(dāng)?shù)奶幚砥? 36 MUMPS應(yīng)用 ? MUMPS用戶包括學(xué)術(shù)界和工業(yè)界，目前用戶數(shù)已超過 1000個。在程序中，首先設(shè)定 JOB=1對初始化 MUMPS，由主進(jìn)程讀入求解的問題（ N, NZ, IRN, JCN, A, 和 HS）。 ? ParMETIS擴(kuò)展了 METIS所提供的功能并包含了特別適合于并行計算和大規(guī)模數(shù)值模擬的子程序。 ? 圖重劃分 – 快速計算自適應(yīng)加密網(wǎng)格的高質(zhì)量再劃分； – 優(yōu)化移去的頂點個數(shù)以及所得劃分的邊切割。該算法已被證明能夠迅速生成高質(zhì)量的劃分。因此，它非?？欤ㄍǔ１?ParMETIS PartGeomKway快 5到 10倍），但它的計算質(zhì)量差。 ? PARMETIS沒有提供直接計算網(wǎng)格自適應(yīng)重劃分這樣的例程。實驗表明，這個例行通常占用了 PARMETIS計算劃分時約一半的運(yùn)行時間 47 自適應(yīng)加密網(wǎng)格 PARMETIS提供了重劃分自適應(yīng)加密網(wǎng)格的子程序 ParMETIS_V3_ AdaptiveRepart。 ? 像 ParMETIS_V3_AdaptiveRepart，該子程序假設(shè)圖已很好的被分布在各處理器。二是假設(shè)圖已很好地分布，并且初始劃分有好的平衡。 ParMETIS_V3_NodeND對圖初始如何分布在各處理器沒用要求。當(dāng)圖已經(jīng)被分成 P部分（ P是處理器數(shù)），圖被重新分布在各處理器。下面為一個結(jié)構(gòu)圖的存儲例圖 , 圖 (a)為一個簡單的圖，圖 (b)為串行 CSR存儲格式，而圖 (C)是分布式 CSR格式。 ? 基于 MPI、 BLAS庫、 LAPACK庫 ? 使用 Fortran、 C/C++開發(fā) 越來越多的應(yīng)用程序在 PETSc環(huán)境上開發(fā)，并逐漸顯示出 PETSc在高效求解大規(guī)模數(shù)值模擬問題方面的優(yōu)勢和威力 54