Nested data parallelism vs. Pipeline parallelism for a N-Body Simulation

摘要

Many problems are characterized because can be divided in terms of a set of independent sub-computation, each strongly associated with an element of a large data structure. Such computations are inherently parallelizable. Data parallel programming is particularly convenient for them. Many techniques have been proposed on the data parallel model, two of them are: nested data parallelism approach and the pipeline parallelism. The nested data parallelism is characterized by dividing the problems into sub-problems that are of the same structure as the larger problem. Further divisions into still smaller sub-problems are usually done by recursion. The pipeline technique is characterized by dividing the problems into sub-problems that must be performed in succession. The input data are broken up and processed one after the other up to complete the solution. N-body problem is a formidable challenge for parallel computation. It is a good problem to apply the data parallel paradigm in its parallel solution. This is possible because some fundamental properties of the problem: The distribution of bodies.the data structure and the need of each bodies to update its position in space. In this paper, we discuss the above two techniques to solve "all pairs" N-body in a data parallel way making emphasis in some performance requirements. Finally, many results are shown.