In partial fulfillment of the Requirements for the Degree of
Doctor of Philosophy
Jakub Kurzak
will defend his thesis
Parallelization
of the Fast Multipole Method
for Distributed Memory Machines
Abstract
The fast multipole method (FMM) is the most advanced algorithm to calculate Coulomb force and potential in particle systems and the only one to offer superior O(N) scaling. It is also often referred to as an inherently parallel algorithm. It is however both complex in its serial formulation and challenging in parallelization. This dissertation provides an extensive discussion of algorithmic and pragmatic serial performance optimization techniques which make FMM a fierce competitor with other, more traditional methods for calculating electrostatic interactions. The original contribution of this work is in a comprehensive and innovative approach to the problem of parallelization of the FMM algorithm. New techniques for domain partitioning and load balancing are described. Original algorithm for overlapping communication with computation is presented. Calculations of periodic boundary conditions are included and multiple time stepping is facilitated. Also a new algorithm of data diffusion is proposed for adapting message exchange to the interconnection topology of the communication subsystem.