A task parallel implementation of fast multipole methods

Kenjiro Taura, Jun Nakashima, Rio Yokota, Naoya Maruyama

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


This paper describes a task parallel implementation of ExaFMM, an open source implementation of fast multipole methods (FMM), using a lightweight task parallel library MassiveThreads. Although there have been many attempts on parallelizing FMM, experiences have almost exclusively been limited to formulation based on flat homogeneous parallel loops. FMM in fact contains operations that cannot be readily expressed in such conventional but restrictive models. We show that task parallelism, or parallel recursions in particular, allows us to parallelize all operations of FMM naturally and scalably. Moreover it allows us to parallelize a ''mutual interaction'' for force/potential evaluation, which is roughly twice as efficient as a more conventional, unidirectional force/potential evaluation. The net result is an open source FMM that is clearly among the fastest single node implementations, including those on GPUs; with a million particles on a 32 cores Sandy Bridge 2.20GHz node, it completes a single time step including tree construction and force/potential evaluation in 65 milliseconds. The study clearly showcases both programmability and performance benefits of flexible parallel constructs over more monolithic parallel loops. © 2012 IEEE.
Original languageEnglish (US)
Title of host publication2012 SC Companion: High Performance Computing, Networking Storage and Analysis
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages9
ISBN (Print)9780769549569
StatePublished - Nov 2012

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'A task parallel implementation of fast multipole methods'. Together they form a unique fingerprint.

Cite this