Fast tridiagonal solvers on the GPU

doi:10.1145/1837853.1693472

Fast tridiagonal solvers on the GPU

2010-01-09

0

OA

AI

DOI：10.1145/1837853.1693472

原文链接

查看原文

摘要

En 中文

We study the performance of three parallel algorithms and their hybrid variants for solving tridiagonal linear systems on a GPU: cyclic reduction (CR), parallel cyclic reduction (PCR) and recursive doubling (RD). We develop an approach to measure, analyze, and optimize the performance of GPU programs in terms of memory access, computation, and control overhead. We find that CR enjoys linear algorithm complexity but suffers from more algorithmic steps and bank conflicts, while PCR and RD have fewer algorithmic steps but do more work each step. To combine the benefits of the basic algorithms, we propose hybrid CR+PCR and CR+RD algorithms, which improve the performance of PCR, RD and CR by 21%, 31% and 61% respectively. Our GPU solvers achieve up to a 28x speedup over a sequential LAPACK solver, and a 12x speedup over a multi-threaded CPU solver.

Fast tridiagonal solvers on the GPU

摘要

AI总结

期刊

机构

引用论文