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的体系结构来实现计算性能的数量级增长。 用于多帧稀疏QRFactorization的焦点膜和多个GPU算法。 QR分解具有广泛的适用性，在数值方面稳定，并且在许多应用领域都有用。 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在计算科学中。 它可用于查找解决方案tosparse线性系统，稀疏线性最小二乘问题，特征性问题，等级和空空间确定以及数值线性代数中的许多其他数学问题。 可以利用这项研究结果的应用领域包括结构工程，计算流动动力学，电磁学，半导体设备，热力学，材料，声学，声学，计算机图形/视觉，机器人/运动学，优化，电路，电路模拟，经济和财务模型，文本/文本模拟，文本/文本模拟，文本/文本模拟，文本/文本网络和其他许多其他区域。 QRFactorization代表了许多其他稀疏直接方法，具有不规则的粗粒平行性和常规的细粒并行性，而开发的方法与这些其他方法非常相关。 这项工作对计算线性性，优化和相关应用领域有广泛的影响。 PI的研究范围超出了数值线性代数的这些特定应用，表明如何在富有挑战性但有希望的GPU计算景观上进行不规则和常规计算的问题，并向许多其他类型的应用打开了大门。 研究人员及其同事计划由于这项工作而生产和分发高质量的软件，他们拥有20年的记录。