SI2-SSE Collaborative Research: SPIKE-An Implementation of a Recursive Divide-and-Conquer Parallel Strategy for Solving Large Systems of Linear Equations

SI2-SSE 合作研究：SPIKE——求解大型线性方程组的递归分治并行策略的实现

• 批准号: 1147680
• 负责人: Matthew Knepley
• 金额: $ 11.77万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-06-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1147680&HistoricalAwards=false
• 关键词: SI2; SSE; Collaborative; Research; SPIKE

Drs. Negrut, Sameh, and Knepley will investigate, produce, and maintain a methodology and its software implementation that leverage emerging heterogeneous hardware architectures to solve billion-unknowns linear systems in a robust, scalable, and efficient fashion. The two classes of problems targeted under this project are banded dense and sparse general linear systems.This project is motivated by the observation that the task of solving a linear system is one of the most ubiquitous ingredients in the numerical solution of Applied Mathematics problems. It is relied upon for the implicit integration of Ordinary Differential Equation (ODE) and Differential Algebraic Equation (DAE) problems, in the numerical solution of Partial Differential Equation (PDE) problems, in interior point optimization methods, in least squares approximations, in solving eigenvalue problems, and in data analysis. In fact, the vast majority of nonlinear problems in Scientific Computing are solved iteratively by drawing on local linearizations of nonlinear operators and the solution of linear systems. Recent advances in (a) hardware architecture; i.e., the emergence of General Purpose Graphics Processing Unit (GP-GPU) cards, and (b) scalable solution algorithms, provide an opportunity to develop a new class of parallel algorithms, called SPIKE, which can robustly and efficiently solve very large linear systems of equations.Drawing on its divide-and-conquer paradigm, SPIKE builds on several algorithmic primitives: matrix reordering strategies, dense linear algebra operations, sparse direct solvers, and Krylov subspace methods. It provides a scalable solution that can be deployed in a heterogeneous hardware ecosystem and has the potential to solve billion-unknown linear systems in the cloud or on tomorrow?s exascale supercomputers. Its high degree of scalability and improved efficiency stem from (i) optimized memory access pattern owing to an aggressive pre-processing stage that reduces a generic sparse matrix to a banded one through a novel reordering strategy; (ii) good exposure of coarse and fine grain parallelism owing to a recursive, divide-and-conquer solution strategy; (iii) efficient vectorization in evaluating the coupling terms in the divide-and-conquer stage owing to a CPU+GPU heterogeneous computing approach; and (iv) algorithmic polymorphism, given that SPIKE can serve both as a direct solver or an effective preconditioner in an iterative Krylov-type method.In Engineering, SPIKE will provide the Computer Aided Engineering (CAE) community with a key component; i.e., fast solution of linear systems, required by the analysis of complex problems through computer simulation. Examples of applications that would benefit from this technology are Structural Mechanics problems (Finite Element Analysis in car crash simulation), Computational Fluid Dynamics problems (solving Navier-Stokes equations in the simulation of turbulent flow around a wing profile), and Computational Multibody Dynamics problems (solving Newton-Euler equations in large granular dynamics problems).SPIKE will also be interfaced to the Portable, Extensible Toolkit for Scientific Computation (PETSc), a two decades old flexible and scalable framework for solving Science and Engineering problems on supercomputers. Through PETSc, SPIKE will be made available to a High Performance Computing user community with more than 20,000 members worldwide. PETSc users will be able to run SPIKE without any modifications on vastly different supercomputer architectures such as the IBM BlueGene/P and BlueGene/Q, or the Cray XT5. SPIKE will thus run scalably on the largest machines in the world and will be tuned for very different network and hardware topologies while maintaining a simple code base.The experience collected and lessons learned in this project will augment a graduate level class, ?High Performance Computing for Engineering Applications? taught at the University of Wisconsin-Madison. A SPIKE tutorial and research outcomes will be presented each year at the International Conference for High Performance Computing, Networking, Storage and Analysis. A one day High Performance Computing Boot Camp will be organized each year in conjunction with the American Society of Mechanical Engineers (ASME) conference and used to disseminate the software outcomes of this effort. Finally, this project will shape the research agendas of two graduate students working on advanced degrees in Computational Science.

Negrut，Sameh和Knepley博士将研究，生产和维护一种方法及其软件实现，该方法及其软件实现利用新兴的异构硬件架构以强大，可扩展和高效的方式解决数十亿未知的线性系统。本项目的目标是两类问题带状密集和稀疏的一般线性系统。本项目的动机是观察到解决线性系统的任务是应用数学问题的数值解决方案中最普遍的成分之一。它依赖于常微分方程（ODE）和微分代数方程（DAE）问题的隐式积分，偏微分方程（PDE）问题的数值解，内点优化方法，最小二乘近似，求解特征值问题和数据分析。事实上，科学计算中的绝大多数非线性问题都是通过利用非线性算子的局部线性化和线性系统的解来迭代求解的。（a）硬件结构方面的最新进展;即，通用图形处理单元（GP-GPU）卡的出现，以及（B）可扩展的求解算法，为开发一类新的并行算法（称为SPIKE）提供了机会，该算法可以鲁棒且有效地求解非常大的线性方程组。SPIKE借鉴其分治范式，建立在几个算法基元之上：矩阵重排策略，稠密线性代数运算，稀疏直接求解器，和Krylov子空间方法。它提供了一个可扩展的解决方案，可以部署在异构的硬件生态系统中，并有潜力解决云或未来的数十亿未知线性系统。的亿万级超级计算机。它的高度可扩展性和提高的效率源于（i）由于积极的预处理阶段，通过新的重新排序策略将通用稀疏矩阵减少到带状矩阵，从而优化了存储器访问模式;（ii）由于递归的分而治之的解决方案策略，良好地暴露了粗粒度和细粒度并行性;（iii）由于CPU+GPU异构计算方法，在分而治之阶段中评估耦合项的有效向量化;以及（iv）算法多态性，假定SPIKE可以在迭代Krylov型方法中用作直接求解器或有效的预处理器。SPIKE将为计算机辅助工程（CAE）社区提供一个关键组件;即，通过计算机模拟分析复杂问题所需的线性系统的快速解决方案。结构力学问题就是受益于这种技术的应用实例（汽车碰撞模拟中的有限元分析），计算流体动力学问题（在翼型周围湍流模拟中求解Navier-Stokes方程）和计算多体动力学问题（解决大颗粒动力学问题中的牛顿-欧拉方程）。SPIKE还将与便携式可扩展科学计算工具包（PETSc）接口，这是一个二十年前的灵活和可扩展的框架，用于解决超级计算机上的科学和工程问题。通过PETSc，SPIKE将提供给全球拥有20，000多名成员的高性能计算用户社区。PETSc用户将能够在不同的超级计算机架构上运行SPIKE，而无需任何修改，例如IBM BlueGene/P和BlueGene/Q或Cray XT 5。因此，SPIKE将可扩展地运行在世界上最大的机器上，并将针对非常不同的网络和硬件拓扑进行调整，同时保持一个简单的代码库。工程应用的高性能计算在威斯康星大学麦迪逊分校任教SPIKE教程和研究成果将每年在高性能计算、网络、存储和分析国际会议上发表。每年将与美国机械工程师协会（ASME）会议一起组织为期一天的高性能计算靴子营，并用于传播这一努力的软件成果。最后，这个项目将塑造两个研究生在计算科学的高级学位工作的研究议程。