A Scalable Parallel Bisection Algorithm for Symmetric Tridiagonal Eigenvalue Problem

摘要

Bisection method is a numerically stable algorithm used to find the eigenvalues of symmetric tridiagonal matrices. It is distinct from other methods in that it can be used to compute a subset of eigenvalues with high accuracy. However, the algorithm is significantly slow compared to other methods when a large number of eigenvalues are desired. Fortunately, the algorithm exhibits a high level of parallelism when it is implemented on various types of multiprocessors, including a single-GPU system. In this paper, we describe a highly scalable implementation using multi-GPU systems to accommodate large matrices. Our approach exploits the latest memory management features available on Nvidia Tesla K20c GPUs, including unified memory architecture, peer-to-peer data transfer, and dynamic parallelism. Our implementation was at least 60 times faster than a multi-core CPU system and exhibits a linear speedup with respect to the number of GPUs in the system.