In order to parallelize a program, it is necessary to divide the problem into subunits that can run independently (or almost independently) from each other.
A problem where the subunits are totally independent from each other is called embarrassingly parallel. An element-wise operation on an array is a typical example--the operation needs to only know the element it is handling at the moment. Another example is our particle simulator. Since there are no interactions, each particle can evolve independently from the others. Embarrassingly parallel problems are very easy to implement and perform very well on parallel architectures.
Other problems may be divided into subunits but have to share some data to perform their calculations. In those cases, the implementation is less straightforward and can lead to performance issues because of the communication costs.
We will illustrate...