Parallel computing has become an important subject in the field of computer science and has proven to be critical when researching high performance solutions.

There was a period in history in which the processors worked in a sequentially manner. At that time a more powerful processor basically meant an increase in the clock frequencies and a higher transistor density, which together derived in a higher computing power. The Moore’s law says that the transistor density doubles approximately every two years. Nowadays, this law is still being fulfilled; however it is no possible to increase the programs performance in an automatic manner as it was at some moment in history, since the clock frequencies reached their limit. Following this problem arises what we call parallel computing, which has become an essential tool for science and in a strong branch of research for computing science.

The evolution of computer architectures like CPUs and GPUs towards a higher number of cores can only confirm that parallelism is today an effective approach for speeding up an algorithm. For some computational problems, sequential CPU-based algorithms are not fast enough to give a solution in a reasonable amount of time. Sometimes these problems can become large to the point that not even a multi-core CPU-based algorithm is fast enough. Problems such as these can be found in science and technology; natural sciences (Physics, Biology, Chemistry), information technologies (IT), geospatial information systems (GIS), structural mechanics problems and even abstract mathematical/computer science (CS) problems. In the article by Cristóbal Navarro, from the Physics Laboratory of CECs, it is indicated that using the parallel computing many of the solutions to these problems can now be computed (calculated) in a reasonable period of time.

Figure 1. Difference between the CPU (left) and GPU (right) architecture.

Parallel computing is the act of solving a problem of size n by dividing its domain into k ? 2 (with k ? N) parts and solving them with p physical processors, simultaneously. Being able to identify the type of problem is essential in the formulation of a parallel algorithm. Let P D be a problem with domain D. If P D is parallelizable, then D can be decomposed into k sub-problems:

P D is a data-parallel problem if D is composed of data elements and solving the problem requires applying a kernel function f (...) to the whole domain:

P D is a task-parallel problem if D is composed of functions and solving the problem requires applying each function to a common stream of data S:

Data-parallel problems are ideal candidates for the GPU, while task-parallel problems are best suited for the CPU. Computational physics problems, such as n-body, are mostly data-parallel, therefore they are good candidates for a massive parallelization on GPU. The n-body problem is an interaction problem where n bodies, or particles, are affected by the gravity of the other n ? 1 ones, in a k-dimensional space (usually k = 2 or k = 3). What is interesting about the n-body problem is that for a system of just three particles no analytical solution exists. For this reason, the n-body is one of the emblematic data-parallel problems found in computational physics, and the goal is to simulate the system through time.

The n-body problem states that for each particle its force is given by its interactions with the other particles:

A classic simulation requires an O(n ^2 ) algorithm since it is an all-with-all type of problem. A GPU solution can process particles in parallel, resulting in a O( n^2 / p ) algorithm, where p is the amount of processors. Research on n-body simulations have found that faster methods exists when sacrificing some numerical precision. The argument is based on the fact that contributions of the summation terms decrease quadratically with the distance between two bodies. As a result, bodies very far from a certain body make an insignificant contribution to its final force, while bodies close to that same body make most of the contribution to its final force. This significance of contributions is the key for designing a faster n-body algorithm. The Barnes-Hut tree-code algorithm is a well known spatial partitioning solution that achieves O(nlog_k(n) ) average time per time step. It uses a quad-tree for k = 2 or equivalently an oct-tree for k = 3. The tree is used for storing average measures of cluster of points far from the reference point (Figure 2).

Figure 2. A quad-tree applied on two clusters of points.

When the simulation is run on GPUs, one can make many particles use the tree in parallel. This improvement in compute time allows one to study much larger systems in the order of millions of particles. Many other physical problems can be treated in parallel using GPUs. The only initial requirement for the problem is to offer enough data-parallelism. However the final performance will also depend on the memory access patterns and the communication between data-elements. Access patterns that keep locality within data-elements incur in high performance, while scattered access patterns present an additional challenge of rearranging the data in a different way, or use the manual caches of the GPU.

---

Reference: C. A. Navarro et al. (2014) A Survey on Parallel Computing and its Applications in Data-Parallel Problems Using GPU Architectures. Commun. Comput. Phys. doi: 10.4208/cicp.110113.010813a