Sparse Direct Methods on High-Performance Heterogeneous Architectures

点击翻译按钮获取中文摘要

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.