Towards a Parallel Algorithm for the Many Body Problem

摘要

The paper reports on research that has been done in order to find out whether a known sequential algorithm for the Many Body Problem was suitable for parallelization. The sequential algorithm as a time complexity believed to be O(N log N). The main issue is how to transform the algorithm into an efficient parallel one. The problem of how to distribute the work evenly among the different processors for this particular problem will be considered. Also the data structure plays an important role. Since the structure tends to be very big for a problem like this, special constructs are necessary to manage it while it is distributed among various processors. Some results from tests with not-many-but-still-a-lot-of-bodies on a 16-Transputer System will be shown and suggestions on how to proceed and improve the algorithm will be given. The work presented is just an example of how to approach a large parallel computing task.