Sparse Direct Methods on High-Performance Heterogeneous Architectures

稀疏直接方法是计算科学中许多应用的基础，但是这些方法并没有跟上异构计算体系结构的发展。 高端系统可以构建为包含多个通用CPU核心，再加上一个或多个图形处理单元（GPU），每个GPU都有数百个简单而快速的计算核心。 该项目开发了高性能的并行稀疏直接方法，可以利用基于GPU的架构来提高计算性能的数量级。 重点研究了多波前稀疏QR分解的单GPU和多GPU算法。 QR分解具有广泛的适用性，数值稳定性好，在许多应用领域都有很好的应用. 稀疏QR分解沿着的非均匀和层次结构以及GPU的独特特性要求开发新的算法，包括管理前端矩阵中规则计算的同时混合，以及计算树中节点之间和并发子树之间的组装过程中的不规则计算，高效的稀疏QR分解是计算科学中许多问题的核心。 它可用于求解稀疏线性方程组、稀疏线性最小二乘问题、特征值问题、秩和零空间确定以及数值线性代数中的许多其他数学问题。 可以利用这项研究成果的应用领域包括结构工程，计算流体动力学，电磁学，半导体器件，热力学，材料，声学，计算机图形/视觉，机器人/运动学，优化，电路仿真，经济和金融建模，chemicalprocess simulation，文本/文档网络以及许多其他领域。 QR分解是许多其他稀疏直接方法的代表，具有不规则粗粒度并行性和规则细粒度并行性，并且所开发的方法与这些其他方法非常相关。 这项工作对计算线性代数、优化和相关应用领域具有广泛的影响。 PI的研究超出了数值线性代数的这些特定应用，展示了如何在GPU计算的挑战性但有前途的领域中执行不规则和规则计算的混合问题，并为许多其他类型的应用打开了大门。 调查员和他的同事计划通过这项工作生产和分发高质量的软件，他们有20年的跟踪记录。

Sparse direct methods form the backbone of many applications incomputational science, but the methods are not keeping pace with advancesin heterogeneous computing architectures. High end systems can be built tocontain multiple general-purpose CPU cores, coupled with one or moreGraphics Processing Units (GPUs) each with hundreds of simple yet fastcomputational cores. This project develops high-performance parallelsparse direct methods that can exploit GPU-based architectures to achieveorders of magnitude gains in computational performance. The focus issingle and multiple GPU algorithms for multifrontal sparse QRfactorization. QR factorization has wide applicability, is numericallyvery stable and is useful in many application areas. The nonuniform andhierarchical structure of sparse QR factorization along with the uniquefeatures of the GPU requires the development of novel algorithms.These include managing the simultaneous mix of regular computations insidethe frontal matrix, and irregular computations in the assembly processbetween nodes in the computational tree and between concurrent subtrees.An efficient sparse QR factorization is an essential kernel in manyproblems in computational science. It can be used to find solutions tosparse linear systems, sparse linear least squares problems, eigenvalueproblems, rank and null-space determination, and many other mathematicalproblems in numerical linear algebra. Application areas that can exploitthe result of this research include structural engineering, computationalfluid dynamics, electromagnetics, semiconductor devices, thermodynamics,materials, acoustics, computer graphics/vision, robotics/kinematics,optimization, circuit simulation, economic and financial modeling, chemicalprocess simulation, text/document networks, and many other areas. QRfactorization is representative of many other sparse direct methods, withboth irregular coarse-grain parallelism and regular fine-grain parallelism,and methodologies developed are very relevant for these othermethods. The work has broad impact on computational linearalgebra, optimization, and related application areas. The PI's research extends beyond these specific applications of numerical linear algebra, demonstrating how problems with a mixture of irregular and regular computation can be performed on the challenging yet promising landscape of GPU computing, and opens the door to many other kinds of applications. The investigator and his colleagues plan on producing and distributing high-quality software as a result of this work, for which they have a 20-year track record.