Sparse Direct Methods on High-Performance Heterogeneous Architectures

高性能异构架构的稀疏直接方法

• 批准号: 1115297
• 负责人: Sanjay Ranka
• 金额: $ 31万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-15 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115297&HistoricalAwards=false
• 关键词: Sparse; Direct; Methods; Performance; Heterogeneous

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.

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