Automatic synthesis of high performance translation operators and execution plans for the fast multipole method
Fernando, Isuru Dilanka
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/121351
Description
Title
Automatic synthesis of high performance translation operators and execution plans for the fast multipole method
Author(s)
Fernando, Isuru Dilanka
Issue Date
2023-07-11
Director of Research (if dissertation) or Advisor (if thesis)
Klöckner, Andreas
Doctoral Committee Chair(s)
Klöckner, Andreas
Committee Member(s)
Olson, Luke
Fischer, Paul
Askham, Travis
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Scientific Computing
Fast Multipole Method
GPU
Abstract
The Fast Multipole Method (FMM) is the leading approach for attaining linear complexity
in the evaluation of long-range (e.g. Coulomb) many-body interactions. The intricacies
of implementing a high performant FMM for different potentials are a major barrier to
the widespread use of the FMM. In the application of the Fast Multipole Method to the
computation of potentials for elliptic PDEs and systems thereof, I present methods that,
given various small amounts of user-supplied problem knowledge automatically exploit this
knowledge to optimize evaluating the potentials.
The first part of the thesis is devoted to the automatic synthesis of translation operators (e.g. multipole-to-local, point-to-multipole, etc.) for arbitrary kernels. I describe the asymptotic cost of variants of our algorithm available given certain pieces of information, as well as the methods by which they are attained. I present theoretical cost bounds as well as numerical evidence that our algorithms attain them.
The second part of the thesis describes my work in extending the first to a system of PDEs. I introduce algorithms to automatically synthesize execution plans for expressions of potential operators involving multiple inputs and outputs, multiple different kernels, as well as source and target derivatives. Given a symbolic description of such an operator, the system outputs a sequence of operations that realizes cost savings through an algebraic procedure based on syzygies.
Finally, I describe the work of using the above algorithms to generate fast code for graphical processing units (GPUs) that achieve near peak performance and explaining the performance characteristics of the different operations in the FMM using a performance model.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
