A Scalable, Numerically Stable, High-performance Tridiagonal Solver using GPUs
Li‐Wen Chang, John A. Stratton, Hee-Seok Kim et al. · 2013
Abstract—In this paper, we present a scalable, numerically stable, high-performance tridiagonal solver. The solver is based on the SPIKE algorithm for partitioning a large matrix into small independent matrices, which can be solved in parallel. For each small matrix, our solver applies a general 1-by-1 or 2-by-2 diagonal pivoting algorithm, which is also known to be numerically stable. Our paper makes two major contributions. First, our solver is the first numerically stable tridiagonal solver for GPUs. Our solver provides comparable quality of stable solutions to Intel MKL and Matlab, at speed comparable to the GPU tridiagonal solvers in existing packages like CUSPARSE. It is also scalable to multiple GPUs and CPUs. Second, we present and analyze two key optimization strategies for our solver: a highthroughput data layout transformation for memory efficiency, and a dynamic tiling approach for reducing the memory access footprint caused by branch divergence.
Cited by 46 works.
Authors
References
- Elementary Numerical Analysis: An Algorithmic Approach
- A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
- Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems
- Iterative Methods for Solving Linear Systems
- Parallel Computers 2: Architecture, Programming and Algorithms
- GPU clusters for high-performance computing
- Fast tridiagonal solvers on the GPU
- An asymmetric distributed shared memory model for heterogeneous parallel systems
- A parallel hybrid banded system solver: the SPIKE algorithm