Dynamic load balancing of the adaptive fast multipole method in heterogeneous systems

Robert E. Overman, Jan F. Prins, Laura A. Miller, Michael L. Minion

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

7 Scopus citations

Abstract

Simulations of colliding galaxies or fluid dynamics at immersed flexible boundaries are most accurately and efficiently accomplished using the adaptive fast multipole method (AFMM) to solve an underlying n-body problem whose localized density varies with the time-dependent evolution of the system under study. Parallelization of the AFMM presents a challenging load balancing problem that must be addressed dynamically as the system evolves. We consider parallelization of the AFMM for time dependent problems using a heterogeneous shared memory compute node consisting of multi-core processors and GPU accelerators. OpenMP task parallelism is used within the CPU cores to parallelize the construction and maintenance of the adaptive spatial decomposition tree and its traversal to compute far-field interactions at each leaf node in the tree. Concurrently, GPUs evaluate all near-field interactions using all-pairs computations. In addition to accurately resolving many physical phenomena out of reach using the uniform FMM, the more complex AFMM permits the number of bodies in leaf cells to be globally and locally varied in order to minimize the CPU and GPU time. We present a cost model and incremental adjustment strategy to load balance the AFMM on a heterogeneous system. We demonstrate using these techniques that a simulation can maintain load balance over hundreds of time steps on a heterogeneous system with 10 CPU cores and 4 GPUs with less than 2% overhead, while achieving a 98X speedup over a serial computation using a single CPU core.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013
PublisherIEEE Computer Society
Pages1126-1135
Number of pages10
ISBN (Print)9780769549798
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 IEEE 37th Annual Computer Software and Applications Conference, COMPSAC 2013 - Boston, MA, Japan
Duration: Jul 22 2013Jul 26 2013

Publication series

NameProceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013

Conference

Conference2013 IEEE 37th Annual Computer Software and Applications Conference, COMPSAC 2013
Country/TerritoryJapan
CityBoston, MA
Period7/22/137/26/13

Keywords

  • accelerators
  • adaptive fast multipole method
  • CUDA
  • dynamic load balancing
  • hybrid computing
  • OpenMP task parallelism

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Dynamic load balancing of the adaptive fast multipole method in heterogeneous systems'. Together they form a unique fingerprint.

Cite this