Abstract | ||
---|---|---|
Particle simulations in fields ranging from biochemistry to astrophysics require the evaluation of interactions between all pairs of particles separated by less than some fixed interaction radius. The applicability of such simulations is often limited by the time required for calculation, but the use of massive parallelism to accelerate these computations is typically limited by inter-processor communication requirements. Recently, Snir [M. Snir, A note on N-body computations with cutoffs, Theor. Comput. Syst. 37 (2004) 295-318] and Shaw [D.E. Shaw, A fast, scalable method for the parallel evaluation of distance-limited pairwise particle interactions, J. Comput. Chem. 26 (2005) 1318-1328] independently introduced two distinct methods that offer asymptotic reductions in the amount of data transferred between processors. In the present paper, we show that these schemes represent special cases of a more general class of methods, and introduce several new algorithms in this class that offer practical advantages over all previously described methods for a wide range of problem parameters. We also show that several of these algorithms approach an approximate lower bound on inter-processor data transfer. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.jcp.2006.06.014 | J. Comput. Physics |
Keywords | Field | DocType |
m. snir,e. shaw,parallel evaluation,molecular dynamics,general class,inter-processor communication requirement,particle simulation,n -body problem,molecular simulation,parallel computing,zonal method,inter-processor data,distance-limited pairwise particle interaction,parallel execution,j. comput,pairwise particle interactions,n-body computation,range-limited n-body simulation,lower bound,parallel computer,n body problem,data transfer,molecular dynamic | n-body problem,Pairwise comparison,Many-body problem,Data transmission,Computer science,Upper and lower bounds,Massively parallel,Algorithm,Mathematical model,Computation | Journal |
Volume | Issue | ISSN |
221 | 1 | Journal of Computational Physics |
Citations | PageRank | References |
24 | 2.28 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kevin J. Bowers | 1 | 189 | 15.30 |
Ron O. Dror | 2 | 439 | 40.56 |
David Elliot Shaw | 3 | 890 | 139.33 |