Accelerating the Jacobi Iteration for Solving Linear Systems of Equations using Theory, Machine Learning, and High Performance Computing

High fidelity scientific simulations modeling physical phenomena typically require solving large sparse linear systems of equations which result from the discretization of a partial differential equation (PDE) by some numerical method. The solution of these linear systems often takes a vast amount of computational time to compute. Solving these linear systems efficiently requires the use of massively parallel hardware with high computational throughput (such as GPUs), as well as the development of linear solver algorithms which respect the memory hierarchy of these hardware architectures to achieve the best performance. This thesis offers two key components towards the development of a memory efficient linear solver algorithm tailored towards high performance computing (HPC) systems. Firstly, starting with the Jacobi iteration (a parallel linear solver algorithm well-suited for HPC), we develop a family of relaxation schemes which greatly improve the convergence of the method. These schemes, termed Scheduled Relaxation Jacobi (SRJ) schemes, provide acceleration for both symmetric and nonsymmetric linear systems of equations. In the symmetric case, a data informed heuristic is developed to aid scheme selection in a practical implementation without user intervention. Secondly, we develop a high-performance GPU implementation of the Jacobi iteration method. The main characteristic of the linear solver is that it utilizes on-chip shared memory for improved memory efficiency. This is enabled by the unstructured swept rule, an algorithm for space-time decomposition which enables efficient stencil computations in parallel on unstructured grids. The shared memory Jacobi linear solver demonstrates improved performance over a classical GPU implementation which relies solely on global memory for solving two-dimensional unstructured problems. These contributions provide the basis for an efficient GPU linear solver for the solution of (potentially unstructured/nonsymmetric) linear systems arising from PDEs. This provides a step towards efficient simulation of physical phenomena, and augmenting the role of simulation in scientific discovery and the engineering design process.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Islam, Mohammad Shafaet

Advisor dc:contributor.advisor

• Wang, Qiqi

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/150137

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/150137