Urop Report "Parallel Alternating Direction Implicit Solver for the Two-Dimensional Heat Diffusion Problem on Graphics Processing Units"

Parallel Alternating Direction Implicit Solver for the Two-Dimensional Heat Diffusion Problem on Graphics Processing Units

Khor Shu Heng Engineering Science Programme National University of Singapore

Abstract

This paper presents a parallel alternating direction implicit (ADI) solver for the two-dimensional heat diffusion problem on an NVidia Graphics Processing Units (GPU). The first section of the work gives a brief introduction on Compute United Device Architecture (CUDA), the programming interface for parallel programming on an NVidia GPU, whereas the second section describes the implementation details of the tridiagonal system solver and the setup of the corresponding right hand side for implicit solution in and direction. The tridiagonal solver used in this work is based on the parallel cyclic reduction algorithm implemented by Zhang et al. [1]. The original algorithm does not supports system size which is non-power of two and uses 5 shared memory usage, where is the tridiagonal system size. We noticed that the shared memory usage can be reduced to 3 for cases where the tridiagonal system is symmetric with uniform elements on the diagonals. Slight modification has been done to cater for cases where the system size if non-power of two. We have also attempted to make the computation of right hand sides as efficient as possible, especially for the solution in y direction, Using CUDA Visual Profiler, the performance of the GPU ADI solver was compared with the serial implementation in CPU, which was based on Gaussian Elimination Scheme without pivoting. Reasonable acceleration was achieved for both float type computation and double type computation.

1. Introduction

1.1 Parallel computing using Graphics Processing Units

Graphics Processing Units is specially designed for computation tasks exhibit fine grained data parallelism, with high ratio of arithmetic operation to memory operation. In three-dimensional graphics rendering, large set of pixels and...