Introducing nested data parallel in barnes hut algorithm

Abstract

The N-body problem is often characterized by the necessity to interact each of the N bodies with every other one. Its principal problem is the time spent in force computation. Computing the force among a set of N bodies can be done in a straightforward way by computing all N2 pair wise interactions. However, a number of more efficient algorithms have been proposed, these can approximate the forces among N bodies in close to linear time. The Barnes-Hut algorithm is one these. Barnes-Hut algorithm is suitable to be resolve in parallel. Several parallel challenges have been don, most of them for shared memory machine. In this paper, we describe the design of portable and efficient parallel implementation of adaptive N-body method: Barnes-Hut algorithm. Our propose is based on a regular communication pattern and work partitioning scheme that allows to apply nested data parallelism and to obtain portable solution. Finally, our aim is not simply to develop an efficient implementation of one algorithm, but show how a programming model can be applied in problems not suitable to it, in first instance.