Load balancing n-body simulations with highly non-uniform density

Olga Pearce, Todd Gamblin, Bronis R. De Supinski, Tom Arsenlis, Nancy M. Amato

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


N-body methods simulate the evolution of systems of particles (or bodies). They are critical for scientific research in fields as diverse as molecular dynamics, astrophysics, and material science. Most load balancing techniques for N-body methods use particle count to approximate computational work. This approximation is inaccurate, especially for systems with high density variation, because work in an N-body simulation is proportional to the particle density, not the particle count. In this paper, we demonstrate that existing techniques do not perform well at scale when particle density is highly non-uniform, and we propose a load balance technique that efficiently assigns load in terms of interactions instead of particles. We use adaptive sampling to create an even work distribution more amenable to partitioning, and to reduce partitioning overhead. We implement and evaluate our approach on a Barnes-Hut algorithm and a large-scale dislocation dynamics application, ParaDiS. Our method achieves up to 26% improvement in overall performance of Barnes-Hut and 18% in ParaDiS.

Original languageEnglish (US)
Title of host publicationICS 2014 - Proceedings of the 28th ACM International Conference on Supercomputing
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)9781450326421
StatePublished - 2014
Externally publishedYes
Event28th ACM International Conference on Supercomputing, ICS 2014 - Munich, Germany
Duration: Jun 10 2014Jun 13 2014

Publication series

NameProceedings of the International Conference on Supercomputing


Other28th ACM International Conference on Supercomputing, ICS 2014


  • load balance
  • parallel algorithm
  • performance
  • simulation

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Load balancing n-body simulations with highly non-uniform density'. Together they form a unique fingerprint.

Cite this