Modularization helps to identify data structures that efficiently work with heterogeneous models where both central processing units (CPUs) and graphics processing units (GPUs) are used. This paper describes a modularized parallelization of the Barnes-Hut algorithm, in which the authors divide the algorithm into a sequence of distinct steps, each of which depends on the outcome of preceding ones.

The paper has several strengths. The background of the problem is clear and well written. Data access patterns, computations, and decisions about CPU or GPU usage for certain steps are described in detail. Three systems with different configurations are evaluated. The results show promising improvements in performance over purely sequential and parallel CPU implementations, especially on System II. A common technique of overlapping the CPU and GPU is used to hide memory latencies to and from the GPU.

The main concern I have with the paper is that the evaluation section is somewhat shorter than expected. There is very little analysis of the reported results and the authors provide almost no evidence or references to back up the proposed explanation. For example, System II achieves speedups of almost 60 times in the best case, while the other two systems improve seven to eight times at most. The authors note that the CPU and GPU are more powerful in those systems, but provide no numerical evidence to support that claim. Furthermore, the GPU in System III is described as highly capable, which makes it difficult to understand why that system cannot show better performance. Another big drawback is that the parallelization of the pure CPU version (CCCCCC) is not described. The N-body computations are highly parallelizable in the sense that streaming single instruction, multiple data (SIMD) extension vectorization can be easily applied for superior parallel CPU performance. Reported results show speedups of less than half of the thread count in CPUs, which makes the parallelization effort questionable for the pure CPU case. For clarification and correction, the last paragraph in Section 3.2 mentions that GPUs use relatively “slow memory.” This statement is unclear and contradicts the CUDA programming guide. I would have appreciated it if the authors had provided references and explained this in more depth.

Based on these contributions and downsides, I give this paper a weak recommendation.