Scalable Distributed Fast Multipole Methods

Qi Hu, Nail A. Gumerov, Ramani Duraiswami
University of Maryland Institute for Advanced Computer Studies (UMIACS)
14th IEEE International Conference on High Performance and Communications (HPCC-2012), 2012


   title={Scalable Distributed Fast Multipole Methods},

   author={Hu, Q. and Gumerov, N.A. and Duraiswami, R. and Fantalgo, LLC and Elkridge, MD},

   journal={14th IEEE International Conference on High Performance and Communications (HPCC-2012)},



Download Download (PDF)   View View   Source Source   



The Fast Multipole Method (FMM) allows O(N) evaluation to any arbitrary precision of N-body interactions that arises in many scientific contexts. These methods have been parallelized, with a recent set of papers attempting to parallelize them on heterogeneous CPU/GPU architectures [1]. While impressive performance was reported, the algorithms did not demonstrate complete weak or strong scalability. Further, the algorithms were not demonstrated on nonuniform distributions of particles that arise in practice. In this paper, we develop an efficient scalable version of the FMM that can be scaled well on many heterogeneous nodes for nonuniform data. Key contributions of our work are data structures that allow uniform work distribution over multiple computing nodes, and that minimize the communication cost. These new data structures are computed using a parallel algorithm, and only require a small additional computation overhead. Numerical simulations on a heterogeneous cluster empirically demonstrate the performance of our algorithm.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: