并行软件库介绍.ppt

1,并行软件库介绍 赵永华中国科学院计算机网络信息中心 超级计算中心,2,主要内容,自主并行软件包HPSEPS介绍MUMPS并行软件包介绍hypre并行软件包介绍Parmetis并行软件包介绍PETSc并行软件包介绍,3,自主并行软件包HPSEPS开发者：赵永华迟学斌等中国科学院计算机网络信息中心超级计算中心,4,概述,HPSEPS（High Performance Symmetric Eigenproblem Software，高性能对称特征问题软件）是由中科院计算机网络信息中心/超级计算中心自主开发。主要用于高性能并行求解实对称/厄密矩阵特征问题、SVD奇异值分解、LSQR分解及其相关问题。是目前国际上唯一提供了稠密和稀疏特征问题等多个并行求解器 的并行软件包：稠密问题并行求解器优于国际通用软件包ScaLAPACK，并被鉴定专家评为国际领先水平（十五信息化建设专项鉴定专家）；稀疏问题并行求解器在可扩展性优于国际通用软件包PARPACK；形成了在千核以上对大规模问题的可扩展并行计算；已用于多个具体应用问题的并行求解,用户应用程序可以直接调用所需的并行求解器可将软件包的并行模块作为黑匣子嵌入应用程序,5,应用领域,大规模特征值问题是许多科学和工程应用：结构动力分析、量子化学、电子结构和材料科学等计算核心，成为国外许多超级计算机极力求解的计算问题之一。随着计算模型变得越来越复杂，导致的稀疏矩阵规模达到千万阶甚至上亿。量子计算中电子结构遇到的特征问题达到了千万阶以上规模，有时需要得到几百个特征对；离子加速器产生的大规模稀疏特征问题可达到上亿阶；日本地球模拟器上费米-Hubbard模型中遇到的大规模稀疏特征问题规模达到了几百亿阶。,应用范围广是国外许多超级计算机极力求解的计算问题之一。需要扩展到几千处理器规模；具有求解上亿个自由度的计算能力；,6,HPSEPS功能,HPSEPS软件包主要包括下列一些求 解器：稠密对称特征问题并行求解器（基于不同的块算法）稀疏对称特征问题并行求解器显示重开始 deflate技术Lanczos 方法LOPBCG方法SVD奇异值分解和LQSR并行求解器并已用于：中科院化学所的二百万规模“有机共轭体系分子”的求解。量子点（Quantum Dots）中较大规模稀疏本征问题的并行求解，形成了2048核的可扩展性并行计算；HPSEPS已被安装到中山大学光电材料与技术国家重点实验室的并行计算机系统上。求解了光子晶体中大规模问题，得到了非常好的效果。,7,软件包架构,HPSEPS的设计采用了自底向上的层次设计方法，每个子程序建立在一些基本例程之上。整个软件包由多层结构构成，其层次结构如下图。,8,软件包涉及到的主要算法,提出了各类大规模数值计算和对称特征问题有效并行算法和实现技术。求解稠密特征问题的不同并行块算法；求解稀疏特征问题的deflate Lanczos 并行算法；基于最优化的各类预处理并行算法；多级混合并行实现技术。,9,软件包功能模块接口,下面给出了HPSEPS提供的子程序的简要说明，其中在子程序名中出现的符号*代表z(复双精度)、c（复单精度）、d（双精度）或s（单精度）。稠密对称矩阵特征问题的子程序主要模块和接口：第一层是计算对称特征系统问题的一些驱动程序。包括：(1)p*gseps：广义对称/厄密特征问题并行求解（选定的特 征值和特征向量）(2)p*sseps:标准对称/厄密特征问题并行求解（选定的特征 值和特征向量）第二层包含特征问题并行求解器所需要的矩阵转换子程序、分解子程序和线性代数子程序等，主要包括：(1)p*syg2st：广义实对称特征问题转化为标准特征问题(2)p*heg2st：广义Hermitian特征问题转化为标准特征问题(3)p*trsm：并行计算含有多个右端项的实三角矩阵方程组(4)p*htrsm：并行计算含有多个右端项的复三角矩阵方程组(5)p*sytrd：Householder并行转换对称矩阵为三对角形式,10,(6)p*hetrd：Householder并行转换Hermitian矩阵为三对角形式。(7)p*stebz：分而治之并行求解实对称三对角矩阵的特征值。(8)p*steiz：逆迭代并行求解实对称三对角矩阵的特征向量(9)p*t2s：回代转化并行求解标准特征问题的特征向量(10)p*st2g：回代转化并行求解广义特征问题的特征向量最后一层包含HPSEPS内部子程序、通信有关的子程序和一些数据处理、错误检测等管理工具。下面列出了其中部分主要子程序。与通信有关的子程序：(1)mpi_init：MPI初始化子程序(2)mpi_creat_cart：创建二维处理器网格通信器(3)mpi_sub_col：创建一维行通信器(4)mpi_sub_row：创建一维列通信器与矩阵分布有关的子程序：(1)mat_2d:矩阵的二维-块循环分布子程序，得到矩阵的数据 结构和在二维处理器网格上的分布信息,11,(2)indxg2l：得到存储全局矩阵元素（i,j）的处理器在二 维处理器网格中的逻辑坐标（row_i,col_j）(3)indxg2p：得到全局矩阵元素（i,j）在处理器器上的局 部子矩阵中对应的元素坐标(loc_i,loc_j)(4)mat _ div：三对角矩阵秩-2划分。(5)*get_sub_mat：得到三对角矩阵秩-2后的子矩阵。(6)pdist_A:将矩阵按2D-块方式分布到二维处理器网格中其它子程序(1)p*gnrm:广义特征问题特征向量余范数求解(2)p*nrm:标准特征问题特征向量余范数求解(3)*lag_app_eigen：Laguerre迭代求解函数近似值(4)*sort：数据排序子程序(5)Mem_free：释放内存空间(6)Comm_free：释放通信器,12,稀疏对称特征问题,在HPSEPS中，提供了基于显式重启-再正交和deflate技术的Lanczos算法的稀疏对称矩阵特征问题并行求解模块。HPSEPS为标准稀疏对称特征问题和广义稀疏对称标准特征问题求解提供了不同的方法和接口:对于标准稀疏对称特征问题：Ax=x HPSEPS提供了两种求解方式：标准求解方式 OP=A 位移逆求解方式 OP=(A-I)-1,13,对于广义稀疏对称特征问题：Ax=Mx 首先将此问题转换为标准特征问题，HPSEPS提供了四种求解方式：(1)标准逆方式 OP=M-1A(2)位移逆方式 OP=(A-M)-1M 为此，HPSEPS提供了不同的用户求解接口，为了给用户使用该软件包提供更好的灵活性，软件包允许用户提供不同的OP操作：为了保持操作的有效性，矩阵向量应保持输入向量和输出向量在处理器上分布的一致性。输入向量的第j个元素在处理器P上，输出向量的第j个元素也必须在处理器P上,14,主要模块和接口：(1)p*lancs：Lanczos框架接口。其通过调用不同的模块，完成矩阵的三对角分解、正交化处理，得到收敛的Ritz对等。(2)p*getv：产生分布在不同处理器上的初始向量。(3)p*sletr：m-步Lanczos并行化处理和分解。(4)p*orth：向量并行正交化过程(5)p*norm2：并行计算向量的2-范数。另外，针对一般性稀疏矩阵结构，HPSEPS提供了稀疏矩阵-向量积的并行求解模块。,15,使用HPSEPS编程的方法,HPSEPS为求解不同模式的矩阵特征问题提供了相应的模板。用户通过适当的修改这些模板，可以得到求解具体特征问题的程序。下面是使用HPSEPS软件包应遵循的一些步骤：选择一个合适的驱动程序。确定处理器的二维网格结构，分布矩阵到各处理器（稠密问题）。修改问题依赖的变量。核查计算结果的精度。,16,稠密特征问题：在深腾7000超级计算机，使用128，256，512，1024核并行求解 3000030000和6000060000 规模问题的全部本征对。稀疏特征问题：求解问题规模大约为190万，得到5个最小本征值。2048个核上性能达到了较高的可扩展性能,17,Hypre软件包 美国加州大学（UC）劳伦斯-利弗莫尔国家实验室（LLNL）/应用科学计算中心（CASC）,18,软件包概述,Hypre（High Performance Preconditioners,高性能预条件子）源于美国能源部和LLNL等在研究国防、环境、能源和生物科学中的物理现象时，开发的一些模拟代码。主要用于大规模并行计算机上求解大型稀疏线性方程组，目的是为用户提供高级并行预条件子，Hypre具有强壮性、易用性、适应性和互动性，其主要特性为：可扩展的预条件子：包括诸如结构化多重网格（SMG）和代数多重网格（AMG）等几类可扩展求解超大规模稀疏线性方程组的预条件子算法。常用的迭代法实现：Hypre提供一些最常用的基于Krylov子空间迭代法。比如求解非对称矩阵的GMRES和求解对称矩阵的CG（包括PCG,CGNR,BiCGStab）。直观的以网格为中心的界面：Hypre通过各种网格界面表示和处理稀疏矩阵，每个界面提供对一些求解器的访问，因此不需要用户去学习和创建复杂的数据结构,19,Hypre：数据结构、求解器和网格接口关系,第一层表示各种线性系统的网格界面，第二层表示各种线性求解器（迭代法和预条件子）第三层表示各种数据划分和矩阵向量存储策略。,20,网格接口,HYPRE为不同的应用提供了不同的接口,该接口目前仅支持标量偏微分方程。结构化（Struct）接口：面向结构网格离散的应用.每个网格点的离散格式具有相同的模式。如有限差分（FDM）半结构化（Sstruct）接口 面向半结构(semi-struct)网格离散的应用，如局部加密AMG、块结构网格上的应用,如有限差分方法（FDM）,有限体积方法（FVM）基于有限元的无结构界面（FEI）应用于有限元（FEM）得到的线性方程组 基于线性代数的非结构矩阵界面（IJ）该接口以矩阵方式显式地表示线性代数方程组,是适用范围最广泛的接口。应用于稀疏线性方程组,为网格界面的补充,21,迭代法与预条件子,迭代方法 Krylov解法器（CG，GMRES(缺省情形)，TFQMR，BiCGSTAB）；BoomerAMG（一个并行代数多重网格解法器）；具有迭代加细(refinement)的SuperLU直接解法器（串行）。预条件子 Diagonal：对角，块Jacobi预条件子(缺省情形)；PILUT：具有阈值（threshold）的并行不完全LU分解（PILU）；Euclid：并行ILU预条件子的扩展；SMG：半粗化（semi-coarsening）多重网格预条件子；二维和三维情形的光滑子(smoother)分别采用线松弛和面松弛PFMG：半粗化多重网格预条件子，使用简单点松弛作为光滑子；BoomerAMG：并行代数多重网格（AMG）预条件子；用户可选择不同的并行粗化策略及松驰格式光滑子.ParaSails：并行稀疏近似逆预条件子,22,ParaSails用于计算优化问题：,因此M为Frobenius范数下A的近似逆。如果A对称,且有Cholesky分解：A=LLT,求解 得到三角近似逆G,；PILUT并行求解A的一个近似分解。矩阵A支持HYPRE 的ParCSR格式、PETSc 的矩阵形式和ISIS+Row的矩阵形式。由于M是非对称的（即使A 是对称的），因此不适合作为对称矩阵的迭代法（如CG）的预条件子；Euclid是一种扩展性能较好的并行不完全LU分解（ILU）预条件子，它支持各种ILU（k）和 ILUT,包括块Jacobi ILU（k），并行ILU（k），它比块Jacobi预条件子更有效,23,网格接口与求解器的关系,Hypre的网格界面与求解器的关系 X表示支持,HYPRE为不同的接口定义了不同的数据结构,并配以适合该接口的解法器,24,多重网格MG,多重网格解法器是HYPRE的重要特色.多重网格方法包含三个要素：光滑算子、限制算子和延拓算子分片线性插值作为延拓相邻点的加权平均作为限制松弛迭代(如Gauss-Seidel、SSOR)等简单迭代作为光滑HYPRE提供多个多重网格解法器 如AMS,SMG,PFMG,MLI,BoomerAMG.这些可满足各种应用的需求。其中SMG和BoomerAMG是目前实际应用中使用最广泛的两个解法器.,25,SMG求解矩形网格下对流扩散方程的FDM,FEM或FVM离散得到的方程组。二维时SMG只在x方向半粗化,在y方向用的是线光滑,三维时则采用面光滑。而PFMG仅使用简单的点光滑，因此PFMG的健壮性不如SMG，但是它在作V-循环迭代时效率更高.BoomerAMG既可作为迭代法,也可作为预条件子。用户可以根据情况选择不同的并行粗化技巧（比如CLJP粗化、经典RS粗化）和松弛策略（比如Gauss-Seidel松弛、Jacobi或加权Jacobi松弛）.,26,Hypre 使用方法,下面的例子是采用并行半粗化多重网格迭代法求解结构网格界面下的线性系统/*Set up the grid and stencil*/HYPRE_StructGridCreate(MPI_COMM_WORLD,dim,%解向量的初始化,27,HYPRE_StructVectorSetBoxValues(x,ilower,iupper,xvalues);.HYPRE_StructVectorAssemble(x);/*Set up the solver*/HYPRE_StructPFMGCreate(MPI_COMM_WORLD,28,算例,对流-反应-扩散方程对流-反应-扩散(Convection-Reaction-Diffusion)方程:div(-K grad u+B u)+C u=F in,采用五点差分离散,得到方程组: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。在ex4.c中,为单位正方形,处理机网格为N N，每个处理机上的网格为n n,h=1/(Nn+1),采用结构网格界面和5点差分离散,并考虑边界条件。相关系数:扩散系数K=x2+exp(y);对流系数B=1.0;反应系数 C=10.0;边界条件:u0=(sin(5x)+sin(5y)/1000;右端项:F=22 sin(x)sin(y)。ex4.c提供4种迭代法：SMG、PFMG、PCG、GMRES,后两种迭代法可以增加SMG、PFMG,对角或块Jacobi等4种预条件子。,29,Struct和IJ两种界面下,各求解器的迭代次数和运行时间(256256,Np=4),注:T(SMG)=T(SMG_setup)+T(SMG_solve),(cpu clock time),Np=4,tol=1.e-6,AMG的并行效率(网格规模为10241024),30,MUMPS由 CEC ESPRIT IV长期研究计划项目资助,31,MUMPS概述,MUMPS：多波前大规模并行稀疏直接解法器（A MUltifrontal Massively Parallel sparse direct Solver）MUMPS是一个通过直接方法求解线性方程组:Ax=b 的并行软件包，其中A是一个对称或非对称的稀疏方阵。MUMPS基于多波前方法的直接求解方法。通过将矩阵A直接分解为A=LU或A=LDLT（对称矩阵）形式完成大规模线性方程的求解。,32,主要功能,求解不同类型的稀疏矩阵方程问题：对称或非对称矩阵（部分主元法），复和实算术矩阵 提供了多种矩阵输入格式：组装格式（assembled format）分布式组装格式（distributed assembled format）单元格式（elemental format）迭代加密和向前误差分析;部分分解和Schur补矩阵提供了多个排序接口：AMD，AMF，PORD，METIS和SCOTCH,33,输入矩阵,矩阵类型 矩阵类型在初始化阶段（JOB=-1）由所有进程通过参数mumps par%SYM设定：0:A是非对称型 1：A是对称正定型 3：A是一般对称矩阵矩阵的输入格式 MUMPS提供了多种矩阵输入格式，这些由参数ICNTL(5)和ICNTL(18)控制。单元格式：矩阵由主进程(host)集中输入，置 ICNTL(5)=1 ICNTL(18)=0组装格式（assembled format）矩阵由主进程(host)集中输入结构由主进程提供(analysis)元素被分布到各处理器上(numeric factorization),34,主要计算步,MUMPS计算Ax=b通过三步完成:,(1)分析(JOB=1)主进程执行排序操作 主进程执行符号分解(2)A=LU或A=LDLT分解(JOB=2)A被分布到各处理器 由主进程和一个或多个从进程对每个波前矩阵进行数值分解(3)求解(JOB=3)b由主进程分布到各处理器 x由分布到各处理器的因子计算得到 x被聚集到主进程或分布到各处理器,35,主要特性,每个处理阶段可独立调用异步通信 使得计算和通信实现了重叠动态调度 算法是自适应的，在执行时重分布任务和数据到适当的处理器,36,MUMPS应用,MUMPS用户包括学术界和工业界，目前用户数已超过1000个。并且平均每天被下载一次。典型应用包括：结构力学和CAD流体力学、磁流体和物理化学地震波传播与成像，海洋模式声学和电磁学传播有限元分析，数值优化，仿真航空、地球物理等,37,OSSAU code of French CEA/CESTA：2D/3D structural mechanics codeODYSSEE code of French CEA/CESTA 已成功应用到具有3千万未知量的3D网格问题Electro-magnetism code(Finite Element Meth.+Integral Equation)Complex double precision,Schur Compl.Fluid mechanicsLU factorization with static pivoting(SuperLU approach like)Car body148770 unknowns and 5396386 nonzeros MSC.Software,38,MUMPS使用方法及实例,组装格式程序 下面是使用MUMPS计算双精度问题的组装格式例子程序。两个文件mpi.h和mumps_struc.h必须被包含在程序中，MPI的初始化和终止通过调用MPI_INIT和MPI_FINALIZE完成。在程序中，首先设定 JOB=1对初始化MUMPS，由主进程读入求解的问题（N,NZ,IRN,JCN,A,和HS）。通过设定JOB=6，然后调用MUMPS由所有进程完成问题的求解。最后设定JOB=-2，调用MUMPS完成数据结构的释放 PROGRAM MUMPS_EXAMPLE NCLUDE mpif.h INCLUDE dmumps_struc.h TYPE(DMUMPS_STRUC)id INTEGER IERR,I CALL MPI_INIT(IERR)C Define a communicator for the package id%COMM=MPI_COMM_WORLDC Ask for unsymmetric code id%SYM=0C Host working id%PAR=1C 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 IFC Call package for solutionid%JOB=6CALL DMUMPS(id)C Solution has been assembled on the hostIF(id%MYID.eq.0)THENWRITE(6,*)Solution is,(id%RHS(I),I=1,id%N)END IFC Deallocate user dataIF(id%MYID.eq.0)THENDEALLOCATE(id%IRN)DEALLOCATE(id%JCN)DEALLOCATE(id%A)DEALLOCATE(id%RHS)END IFC Destroy the instance(deallocate internal data structures)id%JOB=-2CALL DMUMPS(id)CALL MPI_FINALIZE(IERR)STOPEND,这样，对一个构造好的矩阵和右端向量：,，,我们给出如下输入：5：N12:NZ1 2 3.02 3-3.04 3 2.05 5 1.02 1 3.01 1 2.05 2 4.03 4 2.02 5 6.03 2-1.01 3 4.03 3 1.0:A20.024.09.06.013.0:RHS我们将得到解RHS(i)=i,i=1,.,5.,40,ParMETIS并行软件Lawrence Livermore National Laboratory,41,ParMETIS,ParMETIS：并行图划分和填充-约化矩阵排序(Parallel Graph Partitioning and Fill-reducing Matrix Ordering)，特别适合于大规模无结构网格的并行数值模拟。ParMETIS基于MPI并行库，实现了用于无结构图划分、网格划分、计算稀疏矩阵的填充-约化次序等多种算法。ParMETIS扩展了METIS所提供的功能并包含了特别适合于并行计算和大规模数值模拟的子程序。ParMETIS中实现的算法基于并行多层k-路图划分算法、自适应再划分算法及并行多约束算法。,42,功能描述,图划分 快速计算非常大规模图的高质量划分；利用几何信息(当可用时)降低划分时间而不损失质量；可为多相及多物理计算划分图。网格划分 直接计算非常大规模网格高质量划分,无需应用程序创建基本图；提供网格对偶图的高效并行程序。图重划分快速计算自适应加密网格的高质量再划分；优化移去的顶点个数以及所得划分的边切割。划分加细 改进由其它划分算法产生的划分的质量。矩阵重排序 计算稀疏矩阵的填充-约化(fill-reducing)次序；使用基于节点的嵌套剖分算法，此算法显示比其它流行重排序算法更优越。,43,子程序调用,44,无结构图划分,图划分的并行子程序ParMETIS_V3_PartKway基于串行多层k-路分区算法。该算法已被证明能够迅速生成高质量的划分。它包括三个阶段：图的粗化、初步划分、加密。当顶点坐标可用时，PARMETIS也为非结构图划分提供了ParMETIS_PartGeom函数。ParMETIS _PartGeom仅基于空间填充曲线方法计算一个分区。因此，它非常快（通常比ParMETIS PartGeomKway快5到10倍），但它的计算质量差。此子程序可用于空间填充曲线适合的分区技术中的某些计算（例如，N体计算）。,45,下面为一个无结构图的划分过程：,46,直接网格划分,PARMETIS3.0提供了一个新的例程ParMETIS_V3_PartMeshKway支持由网格（而不是图）作为输入的划分和重划分计算。在内部，ParMETIS_V3的PartMeshKway使用mesh_to-graph子程 序，然后调用由ParMETIS_V3 PartKway和ParMETIS_V3 PartGeomKway使用的同样核心划分子程序。PARMETIS没有提供直接计算网格自适应重划分这样的例程。然而，它提供了例程ParMETIS_V3_Mesh2Dual，用来快速、并行地为一个给定的网格构造一个偶图（dual graph）。它可以用来为ParMETIS_V3_AdaptiveRepart子程序构建一个输入图形。从本质上讲，ParMETIS_V3_PartMeshKway和ParMETIS_V3_Mesh2Dual承担着用户高效地编写一个网格到图的子程序责任。实验表明，这个例行通常占用了PARMETIS计算划分时约一半的运行时间,47,自适应加密网格,PARMETIS提供了重划分自适应加密网格的子程序ParMETIS_V3_ AdaptiveRepart。该子程序假设网格已很好地分布在各处理器，但存在着不好的负载平衡。,48,划分加密,PARMETIS提供了用来改善已存在划分质量的子程序ParMETIS_V3_ RefineKway。一旦一个图被划分并被重新分布，可以调用ParMETIS_V3_ RefineKway,进一步改善划分的质量。像ParMETIS_V3_AdaptiveRepart，该子程序假设图已很好的被分布在各处理器。同ParMETIS_V3_AdaptiveRepart一样,ParMETIS_V3_RefineKway执行局部粗化。这两个子程序也使用用样加密算法。不同之处在于ParMETIS_V3_RefineKway没用像ParMETIS_V3_AdaptiveRepart一样对最粗的图进行初始平衡化分解。二是假设图已很好地分布，并且初始划分有好的平衡。这样对于已很好分布的图而言，ParMETIS_V3_RefineKway是很快的。,49,填充-约化(fill-reducing)次序,ParMETIS_V3_NodeND是PARMETIS提供的计算填充-约化次序的子程序。适合于基于Cholesky的直接分解算法。ParMETIS_V3_NodeND对图初始如何分布在各处理器没用要求。它能有效地随机分布图的填充-约化次序。ParMETIS_V3_NodeND首先使用ParMETIS V3 PartKway计算高质量的划分并相应的进行图的重新分布。接下来计算logp层消去树。当图已经被分成P部分（P是处理器数），图被重新分布在各处理器。这样每个处理器接收唯一的子图，而一个多最小度算法用来对这些更小的子图进行排序。,50,Parmetis输入输出格式,在Parmetis中，所有与图有关的子程序的输入格式包括：图的邻接结构、顶点和边的权重、描述图如何被分布在各处理器上的数组。图得结构采用压缩存储格式（CSR）,我们首先为串行图描述CSR存储结构，然后描述图如何被分布到各处理器上。下面为一个结构图的存储例图,图(a)为一个简单的图，图(b)为串行CSR存储格式，而图(C)是分布式CSR格式。,51,测试结果,测试数据：在深腾7000上对上述数据在1024核上所测试的结果：,52,PETSC：并行可扩展科学计算工具箱Argonne 国家实验室,53,PETSC,PETSC：并行可扩展科学计算工具箱（Parallel Extensible Toolkits for Scientific Computing）国能源部ODE2000 支持开发的20 多个ACTS 工具箱之一，由Argonne 国家实验室开发的可移植可扩展科学计算工具箱，主要用于在分布式存储环境高效求解偏微分方程组及相关问题。PETSc所有消息传递通信均采用MPI标准实现。提供大量面向对象的并行代数数据结构、解法器和相关辅助部件，适合并行可扩展求解PDE方程（有限差分、有限元、有限体离散的隐式和显示格式）。基于MPI、BLAS库、LAPACK库使用Fortran、C/C+开发,越来越多的应用程序在PETSc环境上开发，并逐渐显示出PETSc在高效求解大规模数值模拟问题方面的优势和威力,54,PETSc：并行可扩展科学计算工具箱（Parallel Extensible Toolkits for Scientific Computing）核心人员：美国数学与计算机部、Argonne国家重点实验室等等基于MPI、BLAS库、LAPACK库使用Fortran、C/C+开发PETSc软件包含一个功能强大的工具集以在高性能计算机上数值求解偏微分方程及其相关问题可移植性：CRAY T3D，T3E，Origin 2000,IBM SP,HP UX,ASCI Red,Blue Mountain,NOWs，LINUX，ALPHA等公开源代码，免费下载,55,PETSc 的一些模块处理：索引集，包括用于向量索引的置换，重新计数等向量矩阵（一般是稀疏的）分布阵列（对正规的基于网格问题的并行化有用）Krylov 子空间方法预条件子，包括多重网格和稀疏直接解法器非线性解法器解时间相关（非线性）PDEs 的时间步进解法器,56,体系结构,PETSc为用户提供了一个通用的层次化应用程序开发平台。基于PETSc提供的大量对象和解法库，用户可以灵活地开发自己的应用程序。,PDE解法器,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),TS时间步进,矩阵,向量,索引集,KSP(Krylov子空间方法),PC(预条件),DRAW,BLAS,LAPACK,MPI,应用程序,PDE解法器,应用程序,PDE解法器,应用程序,PDE解法器,LAPACK,MPI,BLAS,LAPACK,MPI,BLAS,LAPACK,MPI,向量,BLAS,LAPACK,MPI,索引集,向量,BLAS,LAPACK,MPI,矩阵,索引集,向量,BLAS,LAPACK,MPI,KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,TS时间步进,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,应用程序,TS时间步进,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,MPI,TS时间步进,SNES(无约束优化、非线性解法器),SLES(线性方程解法器),DRAW,PC(预条件),KSP(Krylov子空间方法),矩阵,索引集,向量,BLAS,LAPACK,PETSc实现的层次结构,57,PETSc的数值组件,向量,58,PETSc的基本对象,向量向量是最简单的PETSc对象。PETSc向量对象主要用于存储线性方程组的解和右端向量。PETSc 提供AO 对象来管理向量在全局和局部之间的索引、排序和映射。PETSc 还提供了两个对象DA和IS，来分别管理向量在规则正交网格和无结构网格上各进程之间的分发、聚集和边界点的数据通信等操作。矩阵矩阵是PETSc的基本对象。PETSc同时提供了稠密矩阵和稀疏行矩阵的基本运算功能，以及一些特殊格式（如“无矩阵”实现，无结构网格划分等内容）和用户提供的某些功能扩展和实现。PETSc 的矩阵运算和操作主要包括矩阵的创建、插值、聚集、各种算术运算和释放。PETSc 的各种矩阵运算和操作使用起来非常方便，用户无需关心矩阵的具体存储实现。,59,PETSc的核心组件,PETSc的三个核心组件包括：线性方程求解器（SLES）、非线性方程求解器（SNES）和时间步进积分器（TS）。线性方程求解构成了PETSc最核心的部分。它不仅是几乎所有PDE方程求解器的基本内核，而且也是实现PETSc 的其它两个核心组件SNES 和TS 的必不可少的部分。SLES求解线性方程组Ax=b 其中解算子A是n维非奇异矩阵，b是n维右端向量，x为n维解向量。SLES求解包括：线性方程求解环境的创建、Krylov子空间方法和预条件子（PC）的选择、收敛性判据、LU直接求解等。其本用法：SLESCreate：创建一个线性方程求解环境SLESSetOperators：设置求解算子（矩阵）SLESSetFromoptions：通过运行参数设置SLES运行选项SLESSolve：启动一个线性方程求解器SLESDestroy：释放一个线性方程求解环境SLESSetup：启动一个线性方程求解器SLESGetPC：获得PC对象/环境的访问权SLESGetKSP：获得KSP对象/环境的访问权,60,非线性方程求解SNES非线性解法器基于牛顿迭代法（线性搜索和信赖域方法），依赖线性解法器SLES实现。雅可比矩阵的求解是SNES解法器的重要组成部分。SNES求解以下形式的非线性方程组F(x)=0其中解算子F:Rn Rn。基本用法SNESCreate：创建一个非线性方程求解环境SNESSetType：设置非线性求解器的类型SNESSetFromOptions：通过运行参数设置SNES运行选项SNESSolve：启动一个非线性方程求解器SNESDestroy：释放一个非线性方程求解器SNESSetFunction：设置非线性函数SNESSetJacobian：设置雅可比矩阵,61,时间步进积分TS 时间步进积分器，用于求解依赖时间或时间演化的ODE 方程，或依赖时间的离散化后的PDE方程。TS主要求解如下时间依赖问题u t=F(u,t)其中u为有限维解向量，上式通常为运用有限差分或有限元方法离散后的常微分方线性程组。对于非时间演化或稳态方程，PETSc提供了伪时间步进积分器。TS积分器最终依赖线性解法器SLES和非线性解法器SNES来实现。PETSc为PVODE求解器提供了接口。基本用法TSCreate：创建一个TS求解环境TSSetType：设置TS求解器的类型TSSetInitialTimeStep：设置初始时间和步长TSSetTimeStep：设置时间步长TSGetTimeStep：获得时间步长TSSetDuration：设置最大时间步数TSSetUp：启动TS求解环境TSDestroy：释放TS求解环境TSView：启动TS屏幕输出,62,PETSc与其它软件,PETSc 可扩展性的另一个方面表现在其为非常广泛的一类数值软件和数学库提供了很方便的软件接口。主要包括以下几种类型：线性代数求解器，如AMG、BlockSolve95、DSCPACK、hypre、ILUTP、LUSOL、SPAI、SPOOLES、SuperLU、SuperLU_Dist；最优化软件，如TAO、Veltisto；离散化和网格生成和优化工具包，如Overture、SAMRAI、SUMAA3d；常微分方程求解器，如PVODE；其它，如Matlab、ParMETIS。,63,PETSc编程,PETS