QR decomposition on GPUs

ABSTRACT

QR decomposition is a computationally intensive linear algebra operation that factors a matrix A into the product of a unitary matrix Q and upper triangular matrix R. Adaptive systems commonly employ QR decomposition to solve overdetermined least squares problems. Performance of QR decomposition is typically the crucial factor limiting problem sizes.

Graphics Processing Units (GPUs) are high-performance processors capable of executing hundreds of floating point operations in parallel. As commodity accelerators for 3D graphics, GPUs offer tremendous computational performance at relatively low costs. While GPUs are favorable to applications with much inherent parallelism requiring coarse-grain synchronization between processors, methods for efficiently utilizing GPUs for algorithms computing QR decomposition remain elusive.

In this paper, we discuss the architectural characteristics of GPUs and explain how a high-performance implementation of QR decomposition may be implemented. We provide detailed performance analysis of the resulting implementation for real-valued matrices and offer recommendations for achieving high performance to future developers of dense linear algebra procedures for GPUs. Our implementation sustains 143 GFLOP/s, and we believe this is the fastest announced QR implementation executing entirely on the GPU.

REFERENCES

• 1: NVIDIA Corporation, Santa Clara, California, NVIDIA CUDA Compute Unified Device Architecture, 2008.
• 2: Khronos OpenCL Working Group, The OpenCL Specification, 2008.
• 3: A. Kerr, D. Campbell, and M. Richards, GPU Performance Assessment with the HPEC Challenge, in HPEC Workshop 2008, Lexington, MA, 2008, MIT Lincoln Laboratory.
• 4: R. Haney, T. Meuse, J. Kepner, and J. Lebak, HPEC Challenge Overview, MIT Lincoln Laboratory, 2005.
• 5: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 6: C. H. Bischof and C. V. Loan, The WY Representation for Products of Householder Matrices, Cornell University, Ithaca, NY, USA, 1985.
• 7: David Bindel , James Demmel , William Kahan , Osni Marques, On computing givens rotations reliably and efficiently, ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.206-238, June 2002 [doi>10.1145/567806.567809]
• 8: A. H. Sameh , D. J. Kuck, On Stable Parallel Linear System Solvers, Journal of the ACM (JACM), v.25 n.1, p.81-91, Jan. 1978 [doi>10.1145/322047.322054]
• 9: H. Hoffmann, Stream Algorithms and Architecture, Master's thesis, Massachusetts Institute of Technology, 2003.
• 10: NVIDIA, CUDA CUBLAS Library, NVIDIA Corporation, Santa Clara, California, 2008.
• 11: Vasily Volkov , James W. Demmel, Benchmarking GPUs to tune dense linear algebra, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
• 12: A. Kerr, D. Campbell, and M. Richards, GPU VSIPL, in HPEC Workshop 2008, Lexington, MA, 2008, MIT Lincoln Laboratory.
• 13: M. Baboulin, J. Dongarra, and S. Tomov, Some Issues in Dense Linear Algebra for Multicore and Special Purpose Architectures, Technical Report UT-CS-08-200, University of Tennessee, 2008.
• 14: D. A. Schwartz, R. R. Judd, W. J. Harrod, and D. P. Manley, VSIPL 1.3 API, VSIPL Forum, 2008.