科学计算常用的基础并行求解软件库介绍 王彦棡 2009年12月18日.

Presentation on theme: "科学计算常用的基础并行求解软件库介绍 王彦棡 2009年12月18日."— Presentation transcript:

1 科学计算常用的基础并行求解软件库介绍 王彦棡 2009年12月18日

2 背景介绍 深腾7000是世界上规模最大的一个结点无盘启动的机群系统，成功实现了基于1428个无盘结点的机群系统。 深腾7000是国内第一个实际性能突破每秒百万亿次的异构机群系统，成功实现了1240个2路薄结点和38个16路厚结点的协同计算，实际Linpack性能突破每秒106.5万亿次。

3 背景介绍 Jaguar（rank 1） arpack aztec fftpack fftw gsl hypre libsci metis
Parmetis mumps petsc pspline Scalapack sprng sundials superlu superlu_dist Trilinos umfpack 橡树岭国家实验室

4 JUGENE(rank 4)、JuRoPa(rank 13)、JUMP
背景介绍 JUGENE(rank 4)、JuRoPa(rank 13)、JUMP NAG Parallel Library、ScaLAPACK、ARPACK、PARPACK、 PETSc、MUMPS、SPRNG、ParMETIS、hypre、sundials 利希研究中心 NAG Parallel Library(ScaLAPACK,Eigenvalue and singular value problems, Input/Output, data distribution, Optimisation, Quadrature, Random number generators, Sparse linear algebra, Sparse matrix solvers, Support/utility routines),

5 Alabama Supercomputer Authority
背景介绍 Alabama Supercomputer Authority deal.II, METIS, Octave, PDE2D, PETSc, R, SCSL, SLATEC, Trilinos Ecole Polytechnique Fédérale de Lausanne ARPACK,AZTEC,MUMPS, PETSC,BLACS,ScaLAPACK, SPRNG, FFTW, NAG Fortran 90 library, LAPACK/BLAS from MKL 第四名nasa只布置了编译器、库函数之类的。。。 第五、九名再美国劳伦斯利弗莫尔国家实验室，它们主要安装了PETSc 阿拉巴马州超算中心和洛桑联邦理工学院

6 背景介绍 Trilinos petsc sundials hypre tao slepc adic Aztec BlockSolve95
gsl MUMPS ParMetis pARMS spai spooles fftw SuperLU_dist sprng arpack parpack 通过对上面几个超级计算机软件部署的总结，为深腾7000选择了。。。。。。

7 软件介绍 解决大规模、复杂物理工程和科学应用的面向对象的软件框架下开发并行解决算法和数学库。 数值软件
类别 工具 功能 数值软件 Trilinos 解决大规模、复杂物理工程和科学应用的面向对象的软件框架下开发并行解决算法和数学库。 PETSc 用于在分布式存储环境高效求解偏微分方程组及相关问题。 SUNDIALS 用于求解非线性微分/代数方程。 Hypre 用于大规模并行计算机上求解大型稀疏线性方程组。 ScaLAPACK 可扩展线性代数程序包。 SLEPc 可并行求解大规模稀疏矩阵特征问题。 SuperLU 大型稀疏矩阵直接求解器。 TAO 在高性能机器上求解大规模最优化问题。

8 软件介绍 计算问题 方法 算法 函数库 线性方程组 直接求解法 LU Factorization
ScaLAPACK(dense) SuperLU (sparse) Cholesky Factorization ScaLAPACK LDLT (Tridiagonal matrices) QR Factorization QR with column pivoting LQ factorization

9 软件介绍 计算问题 方法 算法 函数库 线性方程组 迭代方法 Conjugate Gradient GMRES CG Squared
AztecOO (Trilinos) PETSc GMRES AztecOO Hypre CG Squared Bi-CG Stab Quasi-Minimal Residual (QMR) Transpose Free QMR

10 软件介绍 计算问题 方法 算法 函数库 线性方程组 迭代方法 SYMMLQ Precondition CG Richardson
PETSc Precondition CG AztecOO Hypre Richardson Block Jacobi Preconditioner Point Jocobi Preconditioner Least Squares Polynomials

11 软件介绍 线性方程组 迭代方法 多重网格 计算问题 方法 算法 函数库 SOR Preconditioning PETSc
Overlapping Additive Schwartz Approximate Inverse Hypre Sparse LU preconditioner AztecOO Incomplete LU (ILU) preconditioner Least Squares Polynomials 多重网格 MG Preconditioner Algebraic MG Semi-coarsening

12 软件介绍 计算问题 方法 算法 函数库 线性最小二乘 最小二乘 最小范数 极小范数最小二乘 特征值问题 对称特征值 奇异值分解 奇异值问题
ScaLAPACK 最小范数 极小范数最小二乘 特征值问题 对称特征值 For A=AH or A=AT ScaLAPACK (dense) SLEPc (sparse) Anasazi(sparse) 奇异值问题 奇异值分解 广义特征值

13 软件介绍 计算问题 方法 算法 函数库 非线性方程组 Newton Based PETSc NOX&LOCA Matrix Free
Line Search PETSc NOX&LOCA Trust Regions Pseudo-Transient Continuation Matrix Free

14 软件介绍 非线性最优化问题 Newton Based CG 计算问题 方法 算法 函数库 Newton
MOOCHO TAO Finite-Difference Newton Quasi-Newton Non-linear Interior Point CG Standard Non-linear CG Limited Memory BFGS Gradient Projections

15 软件介绍 计算问题 方法 算法 函数库 常微分方程组 Integration 非线性代数方程 Inexact Newton 差分代数方程
Adam-Moulton (Variable coefficient forms) CVODE (SUNDIALS) CVODES Backward Differential Formula Direct and Iterative Solvers CVODE 非线性代数方程 Inexact Newton Line Search KINSOL (SUNDIALS) 差分代数方程 IDA (SUNDIALS)

16 Trilinos Trilinos受到美国政府ASC、LDRD（Laboratory Directed Research and Development）等计划联合资助，是Sandia国家实验室实施的一个大型数值软件项目。其目的是要在一个为解决大规模、复杂物理工程和科学应用的面向对象的软件框架下开发并行解决算法和数学库。 自2001年启动至今，Trilinos已演变到第10版，目前仍处于活跃开发中。它广泛采用面向对象技术，大部分代码用C++编写，底层关键部分则用FORTRAN（主要是BLAS和LAPACK程序）、C（ML）实现。Trilinos能在串行、并行系统上求解线性、非线性和特征问题，提供一致的数值应用程序接口（APIs, Application Programming Interfaces）以方便数值软件协作。特别地，它已经被成功的移植到目前世界最快的计算机Roadrunner上。

17 Objective Package(s) Linear algebra objects Epetra, Jpetra, Tpetra, Kokkos Krylov solvers AztecOO, Belos, Komplex ILU-type preconditioners AztecOO, IFPACK Multilevel preconditioners ML, CLAPS Eigenvalue problems Anasazi Block preconditioners Meros Direct sparse linear solvers Amesos Direct dense solvers Epetra, Teuchos, Pliris Abstract interfaces Thyra Nonlinear system solvers NOX, LOCA Time Integrators/DAEs Rythmos C++ utilities, (some) I/O Teuchos, EpetraExt, Kokkos Trilinos Tutorial Didasko “Skins” PyTrilinos, WebTrilinos, Star-P, Stratimikos, ForTrilinos Optimization MOOCHO, Aristos Archetype package NewPackage Other new in 7.0 (8.0) Galeri, Isorropia, Moertel, RTOp, Aristos, RBGen

18 Trilinos PyTrilinos, WebTrilinos, Star-P, Stratimikos, ForTrilinos, Didasko, NewPackage Galeri, Isorropia, Moertel, RTOp, Aristos, RBGen, Sacado, Stokhos NOX, LOCA MOOCHO, Aristos, Rythmos AztecOO, Belos, Komplex IFPACK, ML, CLAPS Epetra, Jpetra, Tpetra Thyra Teuchos, EpetraExt, Kokkos Epetra, Teuchos, Pliris, Amesos

19 Trilinos的应用 流体力学，如不可压缩湍流问题、线性可压缩流问题、三维海洋流的分叉性分析问题、与时间相关的热辐射传递问题、风洞流问题、大振幅稳态水波旋流问题等。 Gregory Larson et al., Application of single-level, pointwise algebraic, and smoothed aggregation multigrid methods to direct numerical simulations of incompressible turbulent flows, Comput Visual Sci, 11(2008), 27—40. H. C. Elman et al., A parallel block multi-level preconditioner for the 3D incompressible Navier-Stokes equations, Journal of Computational Physics, 187 (2003), 504—523. Howard Elman et al., A taxonomy and comparison of parallel block multi-level preconditioners for the incompressible Navier-Stokes equations, Journal of Computational Physics, 227 (2008), 1790—1808. Dave A. May and Louis Moresi, Preconditioned iterative methods for Stokes flow problems arising in computational geodynamics, Physics of the Earth and Planetary Interiors, 171 (2008), 33—47. David K. Gartling and Clark R. Dohrmann, Quadratic finite elements and incompressible viscous flows, Comput. Methods Appl. Mech. Engrg., 195 (2006), 1692—1708. 19

20 半导体工艺技术，如共振隧穿二极管中的电子转移问题、具辐射损害性的双极型结型晶体管大尺度瞬间灵敏度分析问题。
Trilinos的应用 电磁学 Peter Arbenz et al., On a parallel multilevel preconditioned Maxwell eigensolver, Parallel Computing, 32 (2006), 157—165. T. Vejchodsky et al., Modular hp-FEM system HERMES and its application to Maxwell’s equations, Mathematics and Computers in Simulation, 76 (2007), 223—228. 半导体工艺技术，如共振隧穿二极管中的电子转移问题、具辐射损害性的双极型结型晶体管大尺度瞬间灵敏度分析问题。 M. S. Lasater et al., Parallel Parameter Study of the Wigner- Poisson Equations for RTDs, Computers and Mathematics with Applications, 51 (2006), E. T. Phipps et al., Large-Scale Transient Sensitivity Analysis of a Radiation- Damaged Bipolar Junction Transistor via Automatic Differentiation. 20

21 医学，如心电学中心肌组织作用位的扩展问题。
Trilinos的应用 医学，如心电学中心肌组织作用位的扩展问题。 L. Gerardo-Giorda et al., A model-based block-triangular preconditioner for the Bidomain system in electrocardiology, Journal of Computational Physics, 228 (2009), 3625—3639. 材料学，如表面压力下金属纳米线的共振性质问题、石英晶体的高频共振问题。 Harold S. Park and Patrick A. Klein, Surface stress effects on the resonant properties of metal nanowires: The importance of finite deformation kinematics and the impact of the residual surface stress, Journal of the Mechanics and Physics of Solids, 56 (2008), 3144—3166. Ji Wang et al., Parallel finite element analysis of high frequency vibrations of quartz crystal resonators on LINUX cluster, Acta Mechanica Solida Sinica, Vol. 21, No. 6, December, 2008. 21

22 Trilinos的应用 大气学，如海洋气候模型等。 其它，如核物理学。
Katherine J. Evans et al., A Scalable and Adaptable Solution Framework within Components of the Community Climate System Model, ICCS 2009, Part II, LNCS 5545, pp. 332–341, 2009. Arie de Niet et al., A tailored solver for bifurcation analysis of ocean-climate models, Journal of Computational Physics, 227 (2007), 654—679. 其它，如核物理学。 M. Rizea et al., Finite difference approach for the two-dimensional SchrÖinger equation with application to scission-neutron emission, Computer Physics Communications, 179 (2008), 466—478. 22

23 PETSc 可扩展可移植科学计算工具箱PETSc (Portable, Extensible Toolkit for Scientific Computation) 是美国能源部DOE2000支持开发的20多个ACTS工具箱之一，是由Argonne国家实验室开发的可移植可扩展科学计算工具箱，主要用于在分布式存储环境高效求解偏微分方程组及相关问题。PETSc所有消息传递通信均采用MPI标准实现。 PETSc 包含许多并行线性和非线性方程求解器，这些求解器是使用C ，C++，Fortran77/90和现在的Python编写的，而且PETSc支持有助于有限差分方法的并行分布式阵列。PETSc用C语言开发，遵循面向对象设计的基本特征，用户基于PETSc对象可以灵活开发应用程序。PETSc支持Fortran 77/90、C和C++编写的串行和并行代码。 PETSc最新版本为Petsc-3.0.0。

24 PETSc接口 Chaco - a graph partitioning package.
FFTW - Fastest Fourier Transform in the West, developed at MIT by Matteo Frigo and Steven G. Johnson. Hypre - the LLNL preconditioner library. MUMPS - MUltifrontal Massively Parallel sparse direct Solver. ParMeTiS - parallel graph partitioner pARMS - A Package for the Parallel Iterative Solution of General Large Sparse Linear System, by Zhongze Li and Yousef Saad. ScaLAPACK - Scalable LAPACK. SPAI - for parallel sparse approximate inverse preconditioning. SPOOLES - SParse Object Oriented Linear Equations Solve developed by Cleve Ashcraft. SPRNG - The Scalable Parallel Random Number Generators Library. Sundial/CVODE - the LLNL SUite of Nonlinear and DIfferential/ALgebraic equation Solvers. SuperLU, SuperLU_Dist - robust and efficient sequential and parallel direct sparse solves. Zoltan - Parallel Partitioning, Load Balancing and Data-Management Services.

25 PETSc结构 Application Codes ODE Integrators Visualization
Computation and Communication Kernels MPI, MPI-IO, BLAS, LAPACK Profiling Interface Application Codes Matrices, Vectors, Indices Grid Management Linear Solvers Preconditioners + Krylov Methods Nonlinear Solvers ODE Integrators Visualization Interface

26 PETSc PETSc结构 Main Routine Timestepping Solvers (TS)
PETSc code User code Application Initialization Function Evaluation Jacobian Post- Processing PC PETSc Main Routine Linear Solvers (KSP) Nonlinear Solvers (SNES) Timestepping Solvers (TS)

27 TAO TAO (The Toolkit for Advanced Optimization)是美国能源部DOE2000 支持开发的20 多个ACTS 工具箱之一，是2001年由Argonne 国家实验室开发的高级最优化工具箱。TAO的核心开发人员是Argonne国家实验室数学与计算机科学部的Steve Benson ，Lois Curfman McInnes ，Jorge Moré，Jason Sarich等人。 研发TAO的主要目的是在高性能机器上求解大规模最优化问题，采用面向对象的编程技术，充分利用底层工具箱所提供的支持（并行稀疏矩阵数据结构、预条件子、解法器等）。在此基础上进行开发，不必重写这些代码，可以提高开发效率，节省开发时间，目标是设计出移植性好、性能高、扩展性好、独立于体系结构的并行优化软件。

28 TAO

29 SLEPc SLEPc(Scalable Library for Eigenvalue Problem Computations) 由西班牙Politecnica de Valencia大学的高性能网络设计与计算小组的成员开发，主要负责人是Jose E. Roman and Andrés Tomás。SLEPc是一个并行求解大规模稀疏矩阵特征问题的软件库。它建立在PETSc基础之上，从软件结构到语法标准都与PETSc完全一致，可以理解为PETSc的功能扩展。 SLEPc提供了多个软件包的接口，其中包括ARPACK, BLZPACK, PLANSO, TRLAN等，这些软件包都是可选择安装的，并不影响SLEPc的使用。SLEPc全面支持Fortran语言、C语言以及C++，可以在绝大多数UNIX系统上运行。

30

31 流体力学，如可压缩非粘性流问题、地下水或地表水的流体问题、粘弹流体流问题、维多利亚水螅水母引起的流体流动模拟、冰川的形变和流变等。
PETSc、TAO、SLEPc的应用 流体力学，如可压缩非粘性流问题、地下水或地表水的流体问题、粘弹流体流问题、维多利亚水螅水母引起的流体流动模拟、冰川的形变和流变等。 Mehmet Sahin and Helen J. Wilson, A semi-staggered dilation-free finite volume method for the numerical solution of viscoelastic fluid flows on all-hexahedral elements, J. Non-Newtonian Fluid Mech., 147 (2007), 79—91. C.M. Klaij et al., Pseudo-time stepping methods for space-time discontinuous Galerkin discretizations of the compressible Navier-Stokes equations, Journal of Computational Physics, 219 (2006), 622—643. Laslo T. Diosady and David L. Darmofal, Preconditioning methods for discontinuous Galerkin solutions of the Navier-Stokes equations, Journal of Computational Physics, 228 (2009), 3917—3935. Feng-Nan Hwang and Xiao-Chuan Cai, A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier-Stokes equations, Journal of Computational Physics, 204 (2005), 666—691.

32 医学，如三维超声心电图的研究、三维心肌图像恢复模拟问题、脑模型、计算生物学。
PETSc、TAO、SLEPc的应用 医学，如三维超声心电图的研究、三维心肌图像恢复模拟问题、脑模型、计算生物学。 L. Carracciuolo et al., Towards a parallel component for imaging in PETSc programming environment: A case study in 3-D echocardiography, Parallel Computing, 32 (2006), 67—83. P. Colli Franzone et al., Simulating patterns of excitation, repolarization and action potential duration with cardiac Bidomain and Monodomain models, Mathematical Biosciences, 197 (2005), 35—66. Prashanth Dumpuri et al., An atlas-based method to compensate for brain shift: Preliminary results, Medical Image Analysis, 11 (2007), 128—145. Joe Pitt-Francis et al., Chaste: A test-driven approach to software development for biological modeling, Computer Physics Communications, 40th Anniversary Issue. 32

33 PETSc、TAO、SLEPc的应用 动力学，如地球动力学模拟、烟囱中由热化学对流引起的灰尘定向凝固模拟、回转动力学粒子模拟、在微流控芯片中粒子流动和运动现象的电动学模拟、化学工程中的分子动力学模拟、Bose Hubbard 模型（气态Bose–Einstein冷凝物动力学）、磁流体动力学等。 R.F. Katz et al., Numerical simulation of geodynamic processes with the Portable Extensible Toolkit for Scientific Computation, Physics of the Earth and Planetary Interiors, 163 (2007), 52—68. 烟囱： Richard F. Katz and M. Grae Worster, Simulation of directional solidification, thermochemical convection, and chimney formation in a Hele-Shaw cell, Journal of Computational Physics, 227 (2008), 9823—9840. Y. Nishimura et al., A finite element Poisson solver for gyrokinetic particle simulations in a global field aligned mesh, Journal of Computational Physics, 214 (2006), 657—671. 33

34 Hypre 高性能预条件子Hypre（High Performance Preconditioners）由美国加州大学（UC）和劳伦斯-利弗莫尔国家实验室（LLNL）应用科学计算中心（CASC）开发。开发Hypre软件包的动机起因于美国能源部LLNL在研究国防、环境、能源和生物科学中的物理现象时开发的一些模拟代码。该软件包主要用于大规模并行计算机上求解大型稀疏线性方程组，主要目的是为用户提供高级并行预条件子。Hypre具有功能强大性、易用性、适应性和互动性等特点。

35 Hypre

36 Hypre Solver Struct SStruct FEI IJ Jacobi  SMG PFMG BoomerAMG ParaSails Euclid PILUT PCG GMRES

37 流体力学，如地下储水层复杂流模拟、正压大气模型（天气预测）、大气、海洋模型、可变粘性Stokes流问题等。
Hypre 流体力学，如地下储水层复杂流模拟、正压大气模型（天气预测）、大气、海洋模型、可变粘性Stokes流问题等。 Eric Chénier et al, A collocated finite volume scheme to solve free convection for general non-conforming grids, Journal of Computational Physics, 228 (2009), 2296—2311. C. Burstedde et al., Parallel scalable adjoint-based adaptive solution of variable-viscosity Stokes flow problems, Comput. Methods Appl. Mech. Engrg., 198 (2009), 1691—1700. M. Oevermann et al, A sharp interface finite volume method for elliptic equations on Cartesian grids, Journal of Computational Physics, 228 (2009), 5184—5206.

38 动力学，如水动力学、生物流体动力学（如血流动力学、肌肉壁和心瓣的弹性结构动力学）、低磁雷诺数下的自由表面流的磁流体动力学等。
Hypre 动力学，如水动力学、生物流体动力学（如血流动力学、肌肉壁和心瓣的弹性结构动力学）、低磁雷诺数下的自由表面流的磁流体动力学等。 Boyce E. Griffith et al., An adaptive, formally second order accurate version of the immersed boundary method, Journal of Computational Physics, 223 (2007), 10—49. 其他，如电离辐射的传输问题、中性粒子传输模型、具有限单元矩阵的核空间的计算问题等。 P. N. Brown et al., Fully implicit solution of large-scale non-equilibrium radiation diffusion with high order time integration, Journal of Computational Physics, 204 (2005), 760—783. 38

39 SUNDIALS SUNDIALS (Suite of Nonlinear and Differential/Algebraic Equation Solvers) 由LLNL（Lawrence Livermore National Laboratory）中的CASC（Center for Applied Scientific Computing）开发。SUNDIALS提供了鲁棒的时间积分和非线性求解器，主要适用于求解非线性微分/代数方程。SUNDIALS 基于标准C 语言开发，由串行/并行常微分方程初值问题求解器CVODE/PVODE，CVODE 的扩展CVODES、非线性代数方程求解器KINSOL和微分代数方程初值问题求解器IDA等多个子包组成。SUNDIALS的这四个解法器均提供串行和并行版本。2009 年5月发布了SUNDIALS当前最新的版本2.4.0。

40 SUNDIALS

41 SUNDIALS CVODE CVODES IDA IDAS KINSOL

42 SUNDIALS 工业生产，如钠制冷快速反应器的研究、泡沫流化床反应器的研究、氢气甲醛混合物的催化氧化模拟、甲烷空气混合物的催化氧化模拟、热力层作用下自燃现象的研究、灵敏度分析等。 Mihai Alexe and Adrian Sandu, Forward and adjoint sensitivity analysis with continuous explicit Runge-Kutta schemes, Applied Mathematics and Computation, 208 (2009), 328—346. Haihua Zhao et al., Improving SFR economics through innovations from thermal design and analysis aspects, Nuclear Engineering and Design, 239 (2009), 1042—1055. B.D. Dudson et al., BOUT++: A framework for parallel plasma fluid simulations, Computer Physics Communications, 180 (2009), 1467—1480. 42

43 生物学，如软组织力学、心脏动力学、红细胞新陈代谢作用研究、人脑中各项异性扩散模拟等。
SUNDIALS 生物学，如软组织力学、心脏动力学、红细胞新陈代谢作用研究、人脑中各项异性扩散模拟等。 Bjørn Hald et al., Quantitative evaluation of respiration induced metabolic oscillations in erythrocytes, Biophysical Chemistry, 141 (2009), 41—48. Ning Kang et al., Performance of ILU preconditioning techniques in simulating anisotropic diffusion in the human brain, Future Generation Computer Systems, 20 (2004), 687—698. Joe Pitt-Francis et al., Chaste: A test-driven approach to software development for biological modeling, Computer Physics Communications, 40th Anniversary Issue.

44 谢 谢 44