TitleA Hybrid Method for Solving Tridiagonal Systems on the GPU (In Book)
inGPU Computing Gems
Author(s) Yao Zhang, Jonathan Cohen, Andrew Davidson, John D. Owens
Editor(s) Wen-mei W Hwu
Year October 2011
PublisherMorgan Kaufmann
Abstract Tridiagonal linear systems are of importance to many problems in numerical analysis and computational fluid dynamics, as well as to computer graphics applications in video games and computer-animated films. Typical applications require solving hundreds or thousands of tridiagonal systems, which takes a majority part of total computation time. Fast parallel solutions are critical to larger scientific simulations, interactive computations of special effects in films, and real-time applications in video games. In this chapter, we study the performance of multiple tridiagonal algorithms on a GPU. We design a novel hybrid algorithm that combines a work-efficient algorithm with a stepefficient algorithm in a way well-suited for a GPU architecture. Our hybrid solver achieves 8 and 2 speed-up, respectively, in single precision and double precision over a multithreaded highly-optimized CPU solver, and a 22.3 speedup over a basic GPU solver.