Quinta Disciplima

2011 NASA/ESA Conference on Adaptive Hardware and Systems (AHS-2011)

High Performance Linear Equation Solver Using NVIDIA GPUs
Yoon Kah Leow, Ali Akoglu, Ibrahim Guven, Erdogan Madenci
University of Arizona
{yleow, akoglu, guven, madenci} @email.arizona.edu
specifically, FEM is employed for solving countless
problems that include thermodynamics, magnetic fields,
heat transfer,vibrations, structural analysis, torsion, and
fluid mechanics.
Finding solutions for extremely large problems, such
as ground water flow, can require several months to run
on a high-performance CPU system. GPUs offer
architecture alternatives to CPUs by providing higher
levels of data level parallelism through the use of many
more computational cores and arithmetic units. Current
generation IntelCPUs are limited by a maximum of 6
cores, with the ability to have a total of 12 threads [12]. In
comparison, the latest generation of GPUs (GeForce GTX
480) contains 480 cores, and can have up to 23,040 active
threads [13]. One of the challenges of developing with
CUDA, is the need to maximize the use of available cores
and threads to gain optimal performance. The
computational complexity ofGaussian Elimination
combined with the need to solve very large systems of
linear equations in FEM, makes CUDA compatible GPUs
an excellent candidate for application acceleration. By
leveraging the massively parallel GPU architecture, we
can potentially reduce the computation time for certain
problems from months to a matter of days or even hours.
Such an improvement in execution willprovide scientists
with the tools necessary to solve problems previously
thought unfeasible.
The remainder of this paper is organized as follows:
Section 2 gives a brief introduction to Gaussian
Elimination. Section 3 examines the GPU architecture and
CUDA programming model. Section 4 presents the
parallelization strategies. Section 5 evaluates the
performance on the target platform. The finalconclusions
are drawn in Section 6.

Abstract
The solution of a linear system of equations constitutes
an important part in the field of linear algebra that is
widely used in industries like aerospace, aeronautics,
solid mechanics, fluid dynamics, oil research and
numerous others. A direct method for solving these
equations is Gaussian Elimination, which consists of
forward eliminationand back substitution. We have
tailored this method to take advantage of the massive
parallelism offered by NVIDIA GPU architectures.
Thorough evaluations have been performed for variants
of our implementation that exploit different memory
features on an NVIDIA Tesla C1060 GPU. Compared to a
serial implementation on an Intel Core I7, the execution
time for forward elimination on the GPU isreduced by a
factor of 183X when using both global and shared
memory systems, and by a factor of 185X when using only
global memory.

1. Introduction
Nearly all problems of mathematical physics are
governed by partial differential equations (PDEs). A PDE
involves derivatives of unknown/dependent variables with
respect to independent variables. One of the commonly
used methods for solvingPDEs for practical applications
is the Finite Element Method (FEM). FEM often employs
Gaussian Elimination as a tool for solving for unknowns
in large systems of linear equations [4]. However,
Gaussian Elimination is a major bottleneck in the FEM
due to its computational intensity. This bottleneck is
further increased by large problem sizes. Solving
hundreds of thousands or even millionsof equations is not
uncommon for larger FEM problems.
In this paper, we propose the development and
implementation of a high-performance linear equation
solver for NVIDIA Graphics Processing Units (GPU)
using the Compute Unified Device Architecture (CUDA)
programming model. After carefully modifying the
Gaussian Elimination algorithm to exploit parallelism, we
utilize the GPU as an...