Abstract
An n-body application simulates, at discrete time steps, the evolution of n bodies, each exerting a force on all the other ones. At each time step, n 2 forces are computed, where n belongs to the range from 104 to 106. A hierarchical algorithm recursively partitions the space into subcubes and it approximates the force exerted on a body B by all the bodies on a (sub)cube C as the force exerted by one body, whose position is the center of mass of the bodies in C and whose mass is the sum of their masses. The algorithm may be described as the visit of a tree representing the hierarchical relation among subcubes of the whole space. In a distributed memory architecture, the nodes of the tree may replicated or partitioned in the memories of the processing nodes. We show that to reduce both the execution time and the memory utilization, load balancing should assign bodies to the processing nodes taking locality into account, i.e. bodies close to each other should be assigned to processing nodes close to each other. A set of experimental results of the proposed algorithm is presented.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
J.Barnes and P.Hut. A hierarchical o(nlogn) force calculation algorithm. Nature, (324):446-449, 1996.
J.P.Singh and J.L.Hennessy. Implications of hierarchical n-body methods for multiprocessor architectures. ACM Transaction on Computer Systems, 13(2):141–202, May 1995.
P.Liu. The parallel implementation of n-body algorithms. Master's thesis, Rutgers University, 1994. DIMACS Technical Report 94–27, May 94.
S.Goil. Primitives for problems using hierarchical algorithms on distributed memory machines. In First International Workshop in Parallel Processing, Bangalore, India, 1994.
Y.C.Hu and S.L.Johnsson. On the accuracy of anderson fast n-body algorithm. Technical Report TR-06-96, Harvard University, Division of Engineering and Applied Sciences, January 1996.
L.Greegard and V.Rokhilin. A fast algorithm for particle simulation. Journal of Comput. Physic, (73):325, 1987.
T.Totsuka J.P.Singh, C.Holt, A.Gupta, and J.L.Hennessy. Load balancing and data locality in adaptive hierarchical n-body methods: Barnes-hut, fast multipole and radiosity. Journal of Parallel and Distributing Computing, 27(2):118–141, June 1994.
J.P.Singh. Parallel hierarchical n-body methods and their implications for multiprocessors. Master's thesis, Stanford University, 1993.
Y.Hu and S.L.Johnsson. Implementing o(n) n-body algorithms efficiently in dataparallel languages. Journal of Scientific Programming, 5(4):337–364, 1996.
Y.Hu and S.L.Johnsson. A data-parallel implementation of o(n) hierarchical nbody methods. Journal of Supercomputer Applications, 10(1):3–40, 1996.
S.Goil and S.Ranka. Parallelization requirements for hierarchically structured applications on coarse-grained parallel computers. Technical Report SCCS-688, NPAC, 1995.
M.S.Warren J.K.Salmon and G.S.Winckelmans. Fast parallel tree codes for gravitational and fluid dyamical n-body problems. Journal of Supercomputer Applications, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baiardi, F., Becuzzi, P., Mori, P., Paoli, M. (1998). Load balancing and locality in hierarchical N-body algorithms on distributed memory architectures. In: Sloot, P., Bubak, M., Hertzberger, B. (eds) High-Performance Computing and Networking. HPCN-Europe 1998. Lecture Notes in Computer Science, vol 1401. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0037155
Download citation
DOI: https://doi.org/10.1007/BFb0037155
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64443-9
Online ISBN: 978-3-540-69783-1
eBook Packages: Springer Book Archive