Distributed tree code on cluster of workstations

Abstract EN

In this paper, we design four performance BH algorithm optimization techniques to the distributed versions of the that run on clusters of workstations and use message passing communication model.

the first technique partitions the data and balances the load among the processors so that the algorithm becomes fully distributed with no initialization overhead.

the second method uses pipelining and processor domain partitioning to enhance the overlapping between force computation and processor communication.

it also makes communication asynchronous to minimize processor waiting time.

the third method changes the processor communication model from peerto-peer to master-slave.

this change minimizes the total communication overhead.

the fourth method uses one tree traversal for computing the force on all particles in the processor domain instead of traversing the tree once for each particle.

this method reduces the run time very significantly.

our code is written in C++ and uses MPI (message passing interface) functions.

MPI functions are supported on almost all parallel machines so the code is portable to different platforms.

we use simulation experiments to measure the efficiency of our performance optimization techniques.

from these experiments we measure various performance metrics such as speedup, system efficiency, total execution time, and communication overhead.

the proposed optimization techniques achieve 10-45% of performance optimization compared to the non-optimized distributed bh algorithms.

our code is far more flexible and efficient than the current existing code used to solve the n-body problem.

although our algorithm is not unique, it is a robust, scalable, load balancing and fault–tolerant algorithm.

it complements, enhances and extends the previous work done in this field.