【文章內(nèi)容簡介】 IV長期研究計(jì)劃項(xiàng)目資助 31 MUMPS概述 MUMPS：多波前大規(guī)模并行稀疏直接解法器（ A MUltifrontal Massively Parallel sparse direct Solver） ? MUMPS是一個(gè)通過直接方法求解線性方程組 : Ax=b 的并行軟件包，其中 A是一個(gè)對稱或非對稱的稀疏方陣。 ? MUMPS基于多波前方法的直接求解方法。通過將矩陣 A直接分解為 A=LU或 A=LDLT（對稱矩陣）形式完成大規(guī)模線性方程的求解。 32 主要功能 ? 求解不同類型的稀疏矩陣方程問題： 對稱或非對稱矩陣（部分主元法），復(fù)和實(shí)算術(shù)矩陣 ? 提供了多種矩陣輸入格式： ? 組裝格式（ assembled format） ? 分布式組裝格式（ distributed assembled format） ? 單元格式（ elemental format） ? 迭代加密和向前誤差分析 。 ? 部分分解和 Schur補(bǔ)矩陣 ? 提供了多個(gè)排序接口： AMD， AMF， PORD， METIS和 SCOTCH 33 輸入矩陣 ? 矩陣類型 矩陣類型在初始化階段（ JOB=1）由所有進(jìn)程通過參數(shù) mumps par%SYM設(shè)定： 0: A是非對稱型 1： A是對稱正定型 3： A是一般對稱矩陣 ? 矩陣的輸入格式 MUMPS提供了多種矩陣輸入格式，這些由參數(shù) ICNTL(5)和ICNTL(18)控制。 ?單元格式： 矩陣由主進(jìn)程 (host)集中輸入， 置 ICNTL(5)=1 ICNTL(18)=0 ?組裝格式（ assembled format） – 矩陣由主進(jìn)程 (host)集中輸入 – 結(jié)構(gòu)由主進(jìn)程提供 (analysis) – 元素被分布到各處理器上 (numeric factorization) 34 主要計(jì)算步 ? MUMPS計(jì)算 Ax=b通過三步完成 : (1)分析 (JOB=1) ? 主進(jìn)程執(zhí)行排序操作 ? 主進(jìn)程執(zhí)行符號(hào)分解 (2) A=LU或 A=LDLT分解 (JOB=2) ? A被分布到各處理器 ? 由主進(jìn)程和一個(gè)或多個(gè)從進(jìn)程對每個(gè)波前矩陣進(jìn)行數(shù)值分解 (3) 求解 (JOB=3) ? b由主進(jìn)程分布到各處理器 ? x由分布到各處理器的因子計(jì)算得到 ? x被聚集到主進(jìn)程或分布到各處理器 35 主要特性 ? 每個(gè)處理階段可獨(dú)立調(diào)用 ? 異步通信 使得計(jì)算和通信實(shí)現(xiàn)了重疊 ? 動(dòng)態(tài)調(diào)度 算法是自適應(yīng)的，在執(zhí)行時(shí)重分布任務(wù)和數(shù)據(jù)到適當(dāng)?shù)奶幚砥? 36 MUMPS應(yīng)用 ? MUMPS用戶包括學(xué)術(shù)界和工業(yè)界，目前用戶數(shù)已超過 1000個(gè)。 并且平均每天被下載一次。 ? 典型應(yīng)用包括： – 結(jié)構(gòu)力學(xué)和 CAD – 流體力學(xué)、磁流體和物理化學(xué) – 地震波傳播與成像，海洋模式 – 聲學(xué)和電磁學(xué)傳播 – 有限元分析，數(shù)值優(yōu)化，仿真 – 航空、地球物理等 37 ? OSSAU code of French CEA/CESTA：2D / 3D structural mechanics code ? ODYSSEE code of French CEA/CESTA 已成功應(yīng)用到具有 3千萬未知量的 3D網(wǎng)格問題 ? Electromagism code (Finite Element Meth. + Integral Equation) ? Complex double precision, Schur Compl. ? Fluid mechanics ? LU factorization with static pivoting (SuperLU approach like) ? Car body ? 148770 unknowns and 5396386 nonzeros 38 MUMPS使用方法及實(shí)例 ? 組裝格式程序 下面是使用 MUMPS計(jì)算雙精度問題的組裝格式例子程序。兩個(gè)文件 須被包含在程序中， MPI的初始化和終止通過調(diào)用 MPI_INIT和 MPI_FINALIZE完成。在程序中，首先設(shè)定 JOB=1對初始化 MUMPS，由主進(jìn)程讀入求解的問題（ N, NZ, IRN, JCN, A, 和 HS）。通過設(shè)定 JOB=6，然后調(diào)用 MUMPS由所有進(jìn)程完成問題的求解。最后設(shè)定 JOB=2，調(diào)用 MUMPS完成數(shù)據(jù)結(jié)構(gòu)的釋放 PROGRAM MUMPS_EXAMPLE NCLUDE ’’ INCLUDE ’’ TYPE (DMUMPS_STRUC) id INTEGER IERR, I CALL MPI_INIT(IERR) C Define a municator for the package id%COMM = MPI_COMM_WORLD C Ask for unsymmetric code id%SYM = 0 C Host working id%PAR = 1 C Initialize an instance of the package id%JOB = 1 CALL DMUMPS(id) 39 C Define problem on the host (processor 0) IF ( id%MYID .eq. 0 ) THEN READ(5,*) id%N READ(5,*) id%NZ ALLOCATE( id%IRN ( id%NZ ) ) ALLOCATE( id%JCN ( id%NZ ) ) ALLOCATE( id%A( id%NZ ) ) ALLOCATE( id%RHS ( id%N ) ) READ(5,*) ( id%IRN(I) ,I=1, id%NZ ) READ(5,*) ( id%JCN(I) ,I=1, id%NZ ) READ(5,*) ( id%A(I),I=1, id%NZ ) READ(5,*) ( id%RHS(I) ,I=1, id%N ) END IF C Call package for solution id%JOB = 6 CALL DMUMPS(id) C Solution has been assembled on the host IF ( id%MYID .eq. 0 ) THEN WRITE( 6, * ) ’ Solution is ’,(id%RHS(I),I=1,id%N) END IF C Deallocate user data IF ( id%MYID .eq. 0 )THEN DEALLOCATE( id%IRN ) DEALLOCATE( id%JCN ) DEALLOCATE( id%A ) DEALLOCATE( id%RHS ) END IF C Destroy the instance (deallocate internal data structures) id%JOB = 2 CALL DMUMPS(id) CALL MPI_FINALIZE(IERR) STOP END 55?2 3 4331 1 2241??????????20249613????????????????這樣，對一個(gè)構(gòu)造好的 矩陣和右端向量： ， 我們給出如下輸入： 5 ： N 12 : NZ 1 2 2 3 4 3 5 5 2 1 1 1 5 2 3 4 2 5 3 2 1 3 3 3 : A :RHS 我們將得到解 RHS(i) = i, i = 1, . . . , 5. 40 ParMETIS并行軟件 Lawrence Livermore National Laboratory 41 ParMETIS ParMETIS：并行圖劃分和填充 約化矩陣排序 (Parallel Graph Partitioning and Fillreducing Matrix Ordering) ， 特別適合于大規(guī)模無結(jié)構(gòu)網(wǎng)格的并行數(shù)值模擬。 ? ParMETIS基于 MPI并行庫，實(shí)現(xiàn)了用于無結(jié)構(gòu)圖劃分、網(wǎng)格劃分、計(jì)算稀疏矩陣的填充 約化次序等多種算法。 ? ParMETIS擴(kuò)展了 METIS所提供的功能并包含了特別適合于并行計(jì)算和大規(guī)模數(shù)值模擬的子程序。 ? ParMETIS中實(shí)現(xiàn)的算法基于并行多層 k路圖劃分算法、自適應(yīng)再劃分算法及并行多約束算法。 42 功能描述 ? 圖劃分 – 快速計(jì)算非常大規(guī)模圖的高質(zhì)量劃分； – 利用幾何信息 (當(dāng)可用時(shí) ) 降低劃分時(shí)間而不損失質(zhì)量； – 可為多相及多物理計(jì)算劃分圖。 ? 網(wǎng)格劃分 – 直接計(jì)算非常大規(guī)模網(wǎng)格高質(zhì)量劃分 , 無需應(yīng)用程序創(chuàng)建基本圖； – 提供網(wǎng)格對偶圖的高效并行程序。 ? 圖重劃分 – 快速計(jì)算自適應(yīng)加密網(wǎng)格的高質(zhì)量再劃分； – 優(yōu)化移去的頂點(diǎn)個(gè)數(shù)以及所得劃分的邊切割。 ? 劃分加細(xì) – 改進(jìn)由其它劃分算法產(chǎn)生的劃分的質(zhì)量。 ? 矩陣重排序 – 計(jì)算稀疏矩陣的填充 約化 (fillreducing)次序； – 使用基于節(jié)點(diǎn)的嵌套剖分算法，此算法顯示比其它流行重排序算法更優(yōu)越。 43 子程序調(diào)用 ParMetis可以執(zhí)行下列操作 無結(jié)構(gòu)圖劃分 是否存在頂點(diǎn)坐標(biāo) ParMETIS_V3_PartKway 你有什么時(shí)間 /質(zhì)量權(quán)衡 ParMETISV3_PartGeomKway ParMETIS_V3_PartGeom ParMETIS_V3_Mesh2Dual ParMETIS_V3_PartMeshKway ParMETIS_V3_AdaptiveRepart ParMETIS_V3_RefineKway ParMETIS_V3_NodeND 網(wǎng)格劃分 由網(wǎng)格構(gòu)造圖 自適應(yīng)加密重劃分圖 精化劃分質(zhì)量 計(jì)算填充約化次序 44 無結(jié)構(gòu)圖劃分 ? 圖劃分的并行子程序 ParMETIS_V3_PartKway基于串行多層 k路分區(qū)算法。該算法已被證明能夠迅速生成高質(zhì)量的劃分。它包括三個(gè)階段： 圖的粗化、初步劃分、加密。 ? 當(dāng)頂點(diǎn)坐標(biāo)可用時(shí)， PARMETIS也為非結(jié)構(gòu)圖劃分提供了ParMETIS_PartGeom函數(shù)。 ParMETIS _PartGeom僅基于空間填充曲線方法計(jì)算一個(gè)分區(qū)。因此，它非?？欤ㄍǔ１?ParMETIS PartGeomKway快 5到 10倍），但它的計(jì)算質(zhì)量差。此子程序可用于空間填充曲線適合的分區(qū)技術(shù)中的某些計(jì)算（例如， N體計(jì)算）。 45 下面為一個(gè)無結(jié)構(gòu)圖的劃分過程： 46 直接網(wǎng)格劃分 ParMETIS_V3_PartMeshKway支持由網(wǎng)格（而不是圖）作為輸入的劃分和重劃分計(jì)算。 ? 在內(nèi)部， ParMETIS_V3的 PartMeshKway使用 mesh_tograph子程 序，然后調(diào)用由 ParMETIS_V3 Pa