TY - GEN
T1 - Load balancing n-body simulations with highly non-uniform density
AU - Pearce, Olga
AU - Gamblin, Todd
AU - De Supinski, Bronis R.
AU - Arsenlis, Tom
AU - Amato, Nancy M.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - load balance
KW - parallel algorithm
KW - performance
KW - simulation
UR - http://www.scopus.com/inward/record.url?scp=84903760486&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84903760486&partnerID=8YFLogxK
U2 - 10.1145/2597652.2597659
DO - 10.1145/2597652.2597659
M3 - Conference contribution
AN - SCOPUS:84903760486
SN - 9781450326421
T3 - Proceedings of the International Conference on Supercomputing
SP - 113
EP - 122
BT - ICS 2014 - Proceedings of the 28th ACM International Conference on Supercomputing
PB - Association for Computing Machinery
T2 - 28th ACM International Conference on Supercomputing, ICS 2014
Y2 - 10 June 2014 through 13 June 2014
ER -