MATLAB Implementation of a Multigrid Solver for Diffusion Problems: : Graphics Processing Unit vs. Central Processing Unit

Abstract

Graphics Processing Units are immensely powerful processors and for variety applications they outperform the Central Processing Unit, CPU. The recent generations of GPU’s have a flexible architecture than older generations and programming interface more user friendly, which makes them better suited for general purpose programming. A high end GPU can give a desktop computer the same computational power as a small cluster of CPU’s.

Speedup of applications by using the GPU has been shown in a variety of research fields, including medicine, finance and earth science. 3D seismic imaging is extensively used in oil exploration, and imaging complex geological areas is heavy computational task involving terabytes of data. Seismic imaging software that utilizes GPU’s is being developed by companies such as SeismicCity. They found that 20x performance increase can be achieved by utilizing GPU’s in their computer setup.

In this thesis it is shown that the GPU architecture is well suited for solving partial differential equations on structured grids. A parallel multigrid method algorithm is implemented using Jacket that can harness the computational power of the GPU. Jacket uses MATLAB syntax, which allow for more rapid development of algorithms. This does, however, come at a price, implementations that are developed in high level languages is not as efficient as implementations developed in low level languages such as C.

The ideas used in multigrid have been adapted to solve a broad spectrum of problems that involves structures that do not necessarily resemble any form of physical grid. They can for example be used to solve problems characterized by matrix structures, particle structures and lattice structures. The collection of methods that build on the same ideas as the multigrid method is often called multilevel methods, but there is no official unified term for these methods.

The multigrid algorithm implemented in this thesis efficiently solves Poisson problems for homogenous systems in 2 and 3 dimensions. The GPU implementation is 60 to 70 times faster than the equivalent CPU implementation, and can solve systems of size 2573 in less than a second.

Poisson solvers can be used to solve a variety of physical problems either as a stand alone solver or as a part of another solver. In this thesis it is shown that it can be used in an application where porous convection is simulated. Porous convection can describe migration of ground water and hydrocarbons in the earth’s crust.