【正文】 本征值。 2048個(gè)核上性能達(dá)到了較高的可擴(kuò)展性能 N u m o f C o r e s 5 1 2 1 0 2 4 2 0 4 8T i m e ( s e c ) 2 2 2 0 . 6 1 3 5 0 . 4 9 1 2 . 5T F L O P S 4 . 5 T 8 . 2 T 1 4 . 5 TRun n i n g tim e (s) Num of C or e s 3 0000* 3 0000 6 0000* 6 0000 128 8 5 6 5 9 8 5 256 6 7 8 3 8 3 2 .78 512 4 6 5 2 7 5 8 .77 1024 4 0 3 2 2 3 0 .48 17 Hypre軟件包 美國加州大學(xué)（ UC） 勞倫斯 利弗莫爾國家實(shí)驗(yàn)室（ LLNL） / 應(yīng)用科學(xué)計(jì)算中心（ CASC） 18 軟件包概述 Hypre （ High Performance Preconditioners, 高性能預(yù)條件子） 源于美國能源部和 LLNL等在研究國防、環(huán)境、 能 源和生物科學(xué)中的物理現(xiàn)象時(shí)，開發(fā)的一些模擬代碼 。主要用于大規(guī)模并行計(jì)算機(jī)上求解大型稀疏線性方程組，目的是為用戶提供高級(jí)并行預(yù)條件子 ， Hypre具有強(qiáng)壯性、易用性、 適應(yīng)性和互動(dòng)性，其 主要特性為： ? 可擴(kuò)展的預(yù)條件子： 包括諸如結(jié)構(gòu)化多重網(wǎng)格（ SMG）和代數(shù)多重網(wǎng)格（ AMG）等幾類可擴(kuò)展求解超大規(guī)模稀疏線性方程組的預(yù)條件子算法。 ? 常用的迭代法實(shí)現(xiàn)： Hypre提供一些最常用的基于 Krylov子空間迭代法。比如求解非對(duì)稱矩陣的 GMRES和求解對(duì)稱矩陣的 CG（包括 PCG, CGNR, BiCGStab）。 ? 直觀的以網(wǎng)格為中心的界面： Hypre通過各種網(wǎng)格界面表示和處理稀疏矩陣，每個(gè)界面提供對(duì)一些求解器的訪問，因此不需要用戶去學(xué)習(xí)和創(chuàng)建復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 19 Hypre：數(shù)據(jù)結(jié)構(gòu)、求解器和網(wǎng)格接口關(guān)系 第一層表示各種線性系統(tǒng)的網(wǎng)格界面， 第二層表示各種線性求解器（迭代法和預(yù)條件子） 第三層表示各種數(shù)據(jù)劃分和矩陣向量存儲(chǔ)策略。 20 網(wǎng)格接口 HYPRE為不同的應(yīng)用提供了不同的接口 , 該接口目前僅支持標(biāo)量偏微分方程。 ? 結(jié)構(gòu)化 （ Struct） 接口 ： 面向結(jié)構(gòu)網(wǎng)格離散的應(yīng)用 .每個(gè)網(wǎng)格點(diǎn)的離散格式具有相同的模式。如有限差分（ 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ù)方程組 ,是適用范圍最廣泛的接口。應(yīng)用于稀疏線性方程組 , 為網(wǎng)格界面的補(bǔ)充 21 迭代法與預(yù)條件子 ? 迭代方法 Krylov解法器（ CG， GMRES(缺省情形 )， TFQMR， BiCGSTAB）； BoomerAMG（一個(gè)并行代數(shù)多重網(wǎng)格解法器）； 具有迭代加細(xì) (refinement)的 SuperLU直接解法器（串行）。 ? 預(yù)條件子 Diagonal：對(duì)角，塊 Jacobi預(yù)條件子 (缺省情形 )； PILUT：具有閾值（ threshold）的并行不完全 LU分解（ PILU）； Euclid：并行 ILU預(yù)條件子的擴(kuò)展； SMG：半粗化（ semicoarsening）多重網(wǎng)格預(yù)條件子；二維和三維情形的光滑子 (smoother)分別采用線松弛和面松弛 PFMG：半粗化多重網(wǎng)格預(yù)條件子，使用簡(jiǎn)單點(diǎn)松弛作為光滑子； BoomerAMG：并行代數(shù)多重網(wǎng)格（ AMG）預(yù)條件子；用戶可選擇不同的并行粗化策略及松馳格式光滑子 . ParaSails：并行稀疏近似逆預(yù)條件子 22 – ParaSails用于計(jì)算優(yōu)化問題： , 因此 M為 Frobenius范數(shù)下 A的近似逆 。 如果 A對(duì)稱 , 且有 Cholesky分解 ： A=LLT, 求解 得到三角近似逆 G, ； – PILUT并行求解 A的一個(gè)近似分解。矩陣 A支持 HYPRE 的 ParCSR格式 、 PETSc 的矩陣形式和 ISIS++ Row的矩陣形式。由于 M是非對(duì)稱的（即使 A 是對(duì)稱的），因此不適合作為對(duì)稱矩陣的迭代法（如CG）的預(yù)條件子； – Euclid是一種擴(kuò)展性能較好的并行不完全 LU分解（ ILU）預(yù)條件子，它支持各種 ILU（ k）和 ILUT, 包括塊 Jacobi ILU（ k），并行 ILU（ k），它比塊 Jacobi預(yù)條件子更有效 min || ||FI MA?min || ||FI MA?23 網(wǎng)格接口與求解器的關(guān)系 Hypre的網(wǎng)格界面與求解器的關(guān)系 X表示支持 HYPRE為不同的接口定義了不同的數(shù)據(jù)結(jié)構(gòu) ,并配以適合該接口的解法器 24 多重網(wǎng)格 MG ? 多重網(wǎng)格解法器是 HYPRE的重要特色 . ? 多重網(wǎng)格方法包含三個(gè)要素 ：光滑算子、限制算子和延拓算子 – 分片線性插值作為延拓 – 相鄰點(diǎn)的加權(quán)平均作為限制 – 松弛迭代 (如 GaussSeidel、 SSOR)等簡(jiǎn)單迭代作為光滑 ? HYPRE提供多個(gè)多重網(wǎng)格解法器 如 AMS,SMG,PFMG,MLI, BoomerAMG. 這些可滿足各種應(yīng)用的需求。其中 SMG和 BoomerAMG是目前實(shí)際應(yīng)用中使用最廣泛的兩個(gè)解法器 . 25 – SMG求解矩形網(wǎng)格下對(duì)流擴(kuò)散方程的 FDM, FEM或FVM離散得到的方程組。二維時(shí) SMG只在 x方向半粗化 , 在 y方向用的是線光滑 , 三維時(shí)則采用面光滑。而 PFMG僅使用簡(jiǎn)單的點(diǎn)光滑，因此 PFMG的健壯性不如 SMG，但是它在作 V循環(huán)迭代時(shí)效率更高 . – BoomerAMG既可作為迭代法 , 也可作為預(yù)條件子 。 用戶可以根據(jù)情況選擇不同的并行粗化技巧 （比 如 CLJP粗化 、 經(jīng)典 RS粗化 ） 和松弛策略 （比如 GaussSeidel松弛 、 Jacobi或加權(quán) Jacobi松弛 ） . 26 Hypre 使用方法 下面的例子是采用 并行半粗化 多 重網(wǎng)格迭代法求解結(jié)構(gòu)網(wǎng)格界面下的線性系統(tǒng) /* Set up the grid and stencil */ HYPRE_StructGridCreate(MPI_COMM_WORLD, dim, amp。grid)。 HYPRE_StructGridSetExtents(grid, ilower, iupper)。 HYPRE_StructGridAssemble(grid)。 % 構(gòu)造結(jié)構(gòu)網(wǎng)格和模板 HYPRE_StructStencilCreate(dim, stencil_size, amp。stencil)。 HYPRE_StructStencilSetElement(stencil, 0, offset0)。 /* Set up the matrix, righthand side, and initial guess*/ HYPRE_StructMatrixCreate(MPI_COMM_WORLD, grid, stencil, amp。A)。 HYPRE_StructMatrixInitialize(A)。 % 構(gòu)造結(jié)構(gòu)化矩陣 HYPRE_StructMatrixSetBoxValues(A, ilower, iupper, nelts, elts, Avalues)。 HYPRE_StructMatrixAssemble(A)。 HYPRE_StructVectorCreate(MPI_COMM_WORLD, grid, amp。b)。 HYPRE_StructVectorInitialize(b)。 % 右端向量的初始化 HYPRE_StructVectorSetBoxValues(b, ilower, iupper, bvalues)。 ... HYPRE_StructVectorAssemble(b)。 HYPRE_StructVectorCreate(MPI_COMM_WORLD, grid, amp。x)。 HYPRE_StructVectorInitialize(x)。 % 解向量的初始化 27 HYPRE_StructVectorSetBoxValues(x, ilower, iupper, xvalues)。 ... HYPRE_StructVectorAssemble(x)。 /* Set up the solver */ HYPRE_StructPFMGCreate(MPI_COMM_WORLD, amp。solver)。 HYPRE_StructPFMGSetMaxIter(solver, 50)。 /* optional */ HYPRE_StructPFMGSetTol(solver, )。 /* optional */ HYPRE_StructPFMGSetup(solver, A, b, x)。 %創(chuàng)建求解器 (PFMG) /* Solve the linear system */ HYPRE_StructPFMGSolve(solver, A, b, x)。 %求解線性方程組 /* Get solution info and free up memory */ %返回結(jié)果并釋放內(nèi)存 HYPRE_StructVectorGetBoxValues(x, ilower, iupper, xvalues)。 HYPRE_StructPFMGDestroy(solver)。 HYPRE_StructGridDestroy(grid)。 HYPRE_StructStencilDestroy(stencil)。 HYPRE_StructMatrixDestroy(A)。 HYPRE_StructVectorDestroy(b)。 HYPRE_StructVectorDestroy(x)。 28 算例 ? 對(duì)流 反應(yīng) 擴(kuò)散方程 對(duì)流 反應(yīng) 擴(kuò)散 (ConvectionReactionDiffusion)方程 : div (K grad u + B u) + C u = F in Ω, 采用五點(diǎn)差分離散 , 得到方程組 : Au = b, 其中 A = [Aii Aib 。 Abi Abb], u = [ui 。 ub], b = [bi 。 u0]。 考慮到邊界條件 u= u0 on ?Ω, 即 ub= u0 . 于是 [Aii 0 。 0 I] [ui 。 ub] = [bi Aibu0 。 u0] 。 在 , Ω為單位正方形 , 處理機(jī)網(wǎng)格為 N N，每個(gè)處理機(jī)上的網(wǎng)格為 n n, h=1/(Nn+1), 采用結(jié)構(gòu)網(wǎng)格界面和 5點(diǎn)差分離散 , 并考慮邊界條件。 相關(guān)系數(shù) : 擴(kuò)散系數(shù) K=x2+exp(y)。 對(duì)流系數(shù) B=。 反應(yīng)系數(shù) C=。 邊界條件 : u0 =(sin(5πx)+sin(5πy))/1000。 右端項(xiàng) : F= 2π2 sin(πx)sin(πy) 。 4種迭代法： SMG、 PFMG、 PCG、 GMRES, 后兩種迭代法可以增加 SMG、 PFMG, 對(duì)角或塊 Jacobi等 4種預(yù)條件子。 29 Struct和 IJ兩種界面下 , 各求解器的迭代次數(shù)和運(yùn)行時(shí)間 (256 256,Np=4 ) 界面 結(jié)構(gòu)化網(wǎng)格界面 矩陣界面 求解器 SMG PCG + SMG AMG PCG + AMG PCG + Parasails CG 迭代次數(shù) 9 6 9 7 209 437 計(jì)算時(shí)間 (s) 注 : T(SMG) = T(SMG_setup) + T(SMG_solve), (cpu clock time), Np=4, tol= AMG的并行效率 (網(wǎng)格規(guī)模為 1024 1024) 30 MUMPS 由 CEC ESPRIT