If not task farming then what?

When I decided to apply for the EPCC project of the Summer of HPC I knew that my project will be related to some outreach events and it will have educational purposes too.  It has to display how parallelism works in a concise way using  the parallel programming model of Task farming, one of the most common approaches to parallelization of applications. Why did we choose this model? Task farming is the simplest way to parallelize an application and by the way that it works as a technique, it is easy for someone to understand the concept of parallelism.  Task farming (master-slave model) is a model according to which the processing that must be done is divided into smaller independent tasks. The word ”independent” is a key word for task farming as the communication is generally limited.

Get a message with the task, process the task and send the result to the master

There is one master process that distributes the tasks and  the slave nodes that do the processing. The workers continually claim jobs  until all the processing is done. Every time a worker is done the master gathers the partial result in order to produce the final result of the computation. This technique can be applied to problems that can be split into independent pieces as usually the communication takes place only between the master and the slaves and not between the slaves. So task farming is not an option for every problem. What other options are there?

Well, different problems require different approaches depending on the range of parallel computing and the dependencies of the data. Another programming technique is the Geometric parallelism or SPMD (Single Problem Multiple Data).

Basic structure of SPMD/MPMD technique.
SPMD->same code
MPMD->different code

In this case each process executes basically the same piece of code but on a different part of the data and communicates with neighboring processes. Sometimes, periodic global synchronization among all processes may be needed as this technique is sensitive to the loss of any process and a deadlock may occur.

Is this not enough for you yet? Well,  you can try Algorithmic parallelism or MPMD (Multiple Program Multiple Data) then. In this case, the main problem is divided into smaller sub-problems (in fact each of them is an instance of the original one) so every process executes different piece of code on different data. Well, if you are good enough and the problem is so well divided then no communication is needed between worker processes. In any case communication will be needed for  recombining the results.

What is the best option then? Well, there is no answer to that question. No technique is always the best choice regardless the problem. It always depends on the job that needs to be done.  The best option is the simplest that can be applied to the existing problem. In my case the aim is the development of a smartphone application that the final result will be a fractal image. Every part of the image will be processed by a different device so task farming works fine. In a large scale, a parallel implementation of a program can be very tricky by itself so no need for further complexity!

Typical example of a parallel application