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 high-throughput data layout transformation for memory efficiency, and a dynamic tiling approach for reducing the memory access footprint caused by branch divergence.
| Original language | English (US) |
|---|---|
| Title of host publication | 2012 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2012 |
| DOIs | |
| State | Published - Dec 1 2012 |
| Event | 2012 24th International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2012 - Salt Lake City, UT, United States Duration: Nov 10 2012 → Nov 16 2012 |
Publication series
| Name | International Conference for High Performance Computing, Networking, Storage and Analysis, SC |
|---|---|
| ISSN (Print) | 2167-4329 |
| ISSN (Electronic) | 2167-4337 |
Other
| Other | 2012 24th International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2012 |
|---|---|
| Country | United States |
| City | Salt Lake City, UT |
| Period | 11/10/12 → 11/16/12 |
Fingerprint
Keywords
- GPGPU
- GPU Computing
- SPIKE
- Tridiagonal Solver
ASJC Scopus subject areas
- Computer Networks and Communications
- Computer Science Applications
- Hardware and Architecture
- Software
Cite this
A scalable, numerically stable, high-performance tridiagonal solver using GPUs. / Chang, Li Wen; Stratton, John A.; Kim, Hee Seok; Hwu, Wen-Mei W.
2012 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2012. 2012. 6468510 (International Conference for High Performance Computing, Networking, Storage and Analysis, SC).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - A scalable, numerically stable, high-performance tridiagonal solver using GPUs
AU - Chang, Li Wen
AU - Stratton, John A.
AU - Kim, Hee Seok
AU - Hwu, Wen-Mei W
PY - 2012/12/1
Y1 - 2012/12/1
N2 - 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 high-throughput data layout transformation for memory efficiency, and a dynamic tiling approach for reducing the memory access footprint caused by branch divergence.
AB - 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 high-throughput data layout transformation for memory efficiency, and a dynamic tiling approach for reducing the memory access footprint caused by branch divergence.
KW - GPGPU
KW - GPU Computing
KW - SPIKE
KW - Tridiagonal Solver
UR - http://www.scopus.com/inward/record.url?scp=84877702106&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84877702106&partnerID=8YFLogxK
U2 - 10.1109/SC.2012.12
DO - 10.1109/SC.2012.12
M3 - Conference contribution
AN - SCOPUS:84877702106
SN - 9781467308069
T3 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC
BT - 2012 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2012
ER -