Authors: Olga Pearce, Todd Gamblin, Bronis R. de Supinski, Tom Arsenlis, Nancy M. Amato

Venue: International Conference on Supercomputing (ICS)
DOI: 10.1145/2597652.2597659
Link to Publication

Abstract:
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. 

@inproceedings{Pearce-lbnswh-2014, 
 author = {Olga Pearce and 
Todd Gamblin and 
Bronis R. de Supinski and 
Tom Arsenlis and 
Nancy M. Amato}, 
 bibsource = {dblp computer science bibliography, https://dblp.org}, 
 biburl = {https://dblp.org/rec/conf/ics/PearceGSAA14.bib}, 
 booktitle = {2014 International Conference on Supercomputing, ICS'14, Muenchen, 
Germany, June 10-13, 2014}, 
 doi = {10.1145/2597652.2597659}, 
 editor = {Arndt Bode and 
Michael Gerndt and 
Per Stenstr{\"{o}}m and 
Lawrence Rauchwerger and 
Barton P. Miller and 
Martin Schulz}, 
 pages = {113--122}, 
 publisher = {{ACM}}, 
 timestamp = {Tue, 06 Nov 2018 11:07:02 +0100}, 
 title = {Load balancing n-body simulations with highly non-uniform density}, 
 url = {https://doi.org/10.1145/2597652.2597659}, 
 year = {2014} 
}