Performance Evaluation of Tree Structures and Tree Traversals for Parallel N-Body Cosmological Simulations
Thesis 2006
Publication Type: MS Thesis
Repository URL: amitMSThesis
Modern parallel cosmological simulators are an important component in the study of the formation of galaxies and planetary systems. However, existing simulators do not scale effectively on more recent machines containing hundreds and thousands of processors. The parallel programming lab at University of Illinois, in collaboration with the Department of Astronomy at University of Washington, has developed a new parallel simulator called ParallelGravity which is based on the Charm++ infrastructure. The work on the simulator has been supported by the National Science Foundation. This simulator provides a powerful runtime system that automatically maps computation to physical processors. The simulator scales to a large number of processors with astronomical datasets containing millions of particles using Charm++ features, in particular its measurement-based load balancers. In this thesis, we describe some optimization techniques that have been implemented as part of the simulator. We implement a new scheme for organizing force computation and new techniques for particle space decomposition. The new force computation scheme uses the idea of an interaction list introduced in \cite{stadelThesis}. The performance comparison of particle decomposition techniques is done and the effect of Charm++ features like run-time load balancing is investigated on different types of particle decompositions. By the addition of features like the ones presented in this thesis, we aim to complete a production version of the code and make ParallelGravity a powerful resource for the astronomy community.
Amit Sharma, "Performance Evaluation of Tree structures and Tree traversals for Parallel N-Body Cosmological Simulations", Department of Computer Science, University of Illinois at Urbana-Champaign, 2006.
Research Areas