The ART of Cosmological Simulations

We describe the basic ideas of MPI parallelization of the N-body Adaptive Refinement Tree (ART) code. The code uses self-adaptive domain decomposition where boundaries of the domains (parallelepipeds) constantly move -- with many degrees of freedom -- in the search of the minimum of CPU time. The actual CPU time spent by each MPI task on previous time-step is used to adjust boundaries for the next time-step. For a typical decomposition of 5^3 domains, the number of possible changes in boundaries is 3^{84}. We describe two algorithms of finding minimum of CPU time for configurations with a large number of domains. Each MPI task in our code solves the N-body problem where the large-scale distribution of matter outside of the boundaries of a domain is represented by relatively few temporary large particles created by other domains. At the beginning of a zero-level time-step, domains create and exchange large particles. Then each domain advances all its particles for many small time-steps. At the end of the large step, the domains decide where to place new boundaries and re-distribute particles. The scheme requires little communications between processors and is very efficient for large cosmological simulations.