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

Negrut博士、Sameh博士和Knepley博士将研究、生产和维护一种方法及其软件实现，该方法利用新兴的异类硬件体系结构以健壮、可扩展和高效的方式解决数十亿个未知的线性系统。本项目所针对的两类问题是带状、稠密和稀疏的一般线性系统。本项目的动机是观察到在应用数学问题的数值解中，解线性系统的任务是最普遍的成分之一。它被用于常微分方程(ODE)和微分代数方程(DAE)问题的隐式积分、偏微分方程(PDE)问题的数值求解、内点优化方法、最小二乘逼近、特征值问题的求解和数据分析。事实上，科学计算中的绝大多数非线性问题都是通过利用非线性算子的局部线性化和线性系统的解来迭代求解的。(A)硬件体系结构方面的最新进展，即通用图形处理单元(GP-GPU)卡的出现，以及(B)可伸缩求解算法的出现，为开发一类新的并行算法提供了机会，称为SPAPKE，它可以健壮而高效地求解非常大的线性方程组。SPAPKE借鉴了其分而治之的范例，构建了几种算法原语：矩阵重排序策略、稠密线性代数运算、稀疏直接求解器和Krylov子空间方法。它提供了一个可扩展的解决方案，可以部署在异构的硬件生态系统中，并有可能在云中或未来解决数十亿个未知的线性系统--S艾级超级计算机。它的高度可伸缩性和改进的效率源于：(I)由于积极的预处理阶段而优化的存储器访问模式，其通过新的重新排序策略将通用稀疏矩阵缩减为带状矩阵；(Ii)由于递归、分而治之的求解策略，良好地暴露了粗粒度和细粒度的并行性；(Iii)由于CPU+GPU的异质计算方法，在分而治之阶段，在计算耦合项时进行了有效的矢量化；在工程上，SPRKE将为计算机辅助工程(CAE)社区提供一个关键组件，即通过计算机模拟分析复杂问题所需的线性系统的快速求解。例如结构力学问题(汽车碰撞模拟中的有限元分析)、计算流体动力学问题(在模拟机翼周围的湍流流动中求解Navier-Stokes方程)和计算多体动力学问题(在大颗粒动力学问题中求解牛顿-欧拉方程)。SPIKE还将与可移植、可扩展的科学计算工具包(PETSc)接口，PETSc是一个在超级计算机上解决科学和工程问题的灵活和可扩展的框架。通过PETSC，SPEKE将提供给在全球拥有20,000多名成员的高性能计算用户社区。PETSC用户将能够在非常不同的超级计算机体系结构上运行SPEKE，而无需任何修改，例如IBM Bluegene/P和Bluegene/Q，或Cray XT5。因此，SPEKE将在世界上最大的计算机上可扩展地运行，并将针对非常不同的网络和硬件拓扑进行调整，同时维护简单的代码库。在此项目中收集的经验和教训将增加研究生级别的课程-工程应用程序的高性能计算？在威斯康星大学麦迪逊分校任教。每年将在高性能计算、网络、存储和分析国际会议上提交一份尖峰教程和研究成果。每年将结合美国机械工程师协会(ASME)会议组织一次为期一天的高性能计算训练营，用于传播这项工作的软件成果。最后，这个项目将塑造两名攻读计算科学高级学位的研究生的研究议程。

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.