Automatic synthesis of high performance translation operators and execution plans for the fast multipole method

Fernando, Isuru Dilanka

Permalink

https://hdl.handle.net/2142/121351 Copy

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/121351

Copyright and License Information

© 2023 Isuru Fernando

Owning Collections