(437c) Iterative Methods for Solving PDEs On a Graphics Processing Unit

The arithmetic solution of partial differential equations (PDE) is a computationally demanding problem that appears in many scientific disciplines. Although until recently direct methods were preferred for the solution of such systems because of their robustness and predictable behavior, recent development in iterative solvers have shifted the focus towards their direction [1].

The main driving force behind the use of iterative solvers is their computational efficiency for solving very large linear systems on high-performance computers, and in this work we present the use of Graphics Processing Units (GPUs) for the efficient solution of PDEs by various iterative methods. The nine test problems studied arise from computational fluid dynamics, heat transfer and structural mechanics applications and are commonly used in a wide variety of industrial and engineering problems. In [2] it is shown that for these problems the most robust and efficient iterative algorithm on a 16-node Linux cluster is CARP-CG which is a conjugate gradient parallel variation of the Kaczmarz algorithm.

GPUs have been made available for general purpose computing since the introduction of the Compute Unified Device Architecture by nVidia, and they have been used in many areas of scientific computing [3]. This work presents comparisons between GPU, CPU, and cluster implementations of several well-known iterative methods, including Kaczmarz's, Cimmino's, component averaging, conjugate gradient normal residual, preconditioned conjugate gradient, and conjugate-gradient-accelerated component-averaged row projections, for solving the nine aforementioned problems. It is shown that the CGNR is the most efficient on the GPU and it is 5 to 21 times faster than a CPU implementation, and 1 to 3 times faster than a 16-node Linux cluster.

The use of GPUs for general purpose computing offers an inexpensive hardware platform for accelerating many computationally demanding problems, but requires the careful migration of an algorithm to this new architecture and the exploration of the design space to identify the method that produces the best performance.

1. Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, 2000.

2. D. Gordon, R. Gordon, ?CARP-CG: A robust and efficient parallel solver for linear systems, applied to strongly convection-dominated elliptic partial differential equations,? Tech. rep., Department of Computer Science, University of Haifa, Haifa, Israel, submitted for publication (April 2008).

3. A. Gottlied, K. Hwang, S. Sahni (eds.), ?Special Issue on General-Purpose Processing Using Graphics Processing Units,? Journal of Parallel and Distributed Computing, Vol. 68, No.10, pp. 1305?1402, 2008.