Sparse Direct Methods on High-Performance Heterogeneous Architectures

稀疏直接方法构成了计算科学中许多应用的支柱，但这些方法跟不上异构计算体系结构的发展。高端系统可以构建为包含多个通用CPU核心，再加上一个或多个图形处理单元（gpu），每个图形处理单元都有数百个简单而快速的计算核心。该项目开发高性能并行稀疏直接方法，可以利用基于gpu的架构来实现计算性能的数量级增益。重点研究了多正面稀疏QRfactorization的单GPU和多GPU算法。QR分解具有广泛的适用性，在数值上非常稳定，在许多应用领域都很有用。稀疏QR分解的非均匀和分层结构以及GPU的独特性要求开发新的算法。这包括管理正面矩阵中规则计算的同时混合，以及计算树中节点之间和并发子树之间组装过程中的不规则计算。高效的稀疏QR分解是计算科学中许多问题的核心。它可以用于求解稀疏线性系统、稀疏线性最小二乘问题、特征值问题、秩和零空间确定以及数值线性代数中的许多其他数学问题。可以利用本研究成果的应用领域包括结构工程、计算流体动力学、电磁学、半导体器件、热力学、材料、声学、计算机图形学/视觉、机器人/运动学、优化、电路仿真、经济和金融建模、化学过程仿真、文本/文档网络以及许多其他领域。QRfactorization是许多其他稀疏直接方法的代表，具有不规则的粗粒度并行性和规则的细粒度并行性，并且所开发的方法与这些方法非常相关。该工作在计算线性代数、优化及相关应用领域具有广泛的影响。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.