With this article we are starting a series of publications, “Parallel Programming for the Little Ones.” The project’s expected audience: schoolchildren, as well as students who are beginning to study parallel programming.
The advantage of a multithreaded application over a sequential one is that several threads do the same amount of work several times faster. In a particular case, a unit of work can be one loop iteration. Students make a typical mistake in parallel programming: they create several threads, each of which does the same amount of work as the sequential program. This does not lead to the desired speedup, and sometimes even slows the application down. A very simple rule applies here: each thread in a parallel application must do N times less work than the sequential program, where N is the number of threads launched.
Let’s consider a simple method of statically dividing the iterations of a one-dimensional loop among several threads. The figure shows a simple loop consisting of 10 iterations. The iteration space is described by the interval [0; 10). In a sequential program, the initial value of the iteration counter is zero, the loop increment is one, i.e., the loop body is executed for every iteration.
As stated above, launching two or more threads that would execute the very same code shown in the figure is a mistake. In this case, the amount of work for one thread will remain the same, while for the whole program it will grow several times over. The work—the loop iterations—must be divided among the threads. The figure below schematically shows static round-robin distribution for two threads.
It is easy to see that thread number 0 starts its work with the zero iteration and executes only the even iterations (the increment is 2): 0, 2, 4, 6, 8, while thread number 1 starts with iteration 1 and does the odd ones: 1, 3, 5, 7, 9. Thus, each thread does half as much work as the sequential program. The theoretical speedup is equal to two. Let’s consider a variant where the work is divided among three threads (see the figure below).
Here thread number 0 also starts with the zero iteration, but processes every third iteration: 0, 3, 6, 9. Thread number 1 starts with iteration 1, and thread number two starts with iteration 2. For all threads, the loop counter increment is equal to three. The theoretical speedup is equal to 3. In this specific case, load balance is disrupted and the actual speedup is 10/4 = 2.5. It should be noted that as the number of iterations grows, the imbalance will be leveled out and will approach the theoretical speedup.
One can observe the pattern that each thread starts by executing the iteration whose number matches the thread number, and the increment is equal to the number of threads. Thus, we can write the general case for an arbitrary number of threads (see the figure below).
The advantages of static round-robin iteration distribution are: a) simplicity of software implementation; b) no overhead for iteration scheduling; c) good load balance with a large number of iterations and the same loop-body execution time for different iterations. The drawback of the approach is the lack of any ability to balance the load if the loop body takes different amounts of time for different iterations.
This drawback was fixed in the OpenMP library. For static round-robin division of loop iterations, the directive shown in the figure below can be used.
For poorly balanced amounts of work, when the loop body takes different amounts of time for different iterations, a dynamic load-balancing algorithm can be used.
The drawbacks of OpenMP include a restriction on the type of the loop iteration variable. The OpenMP 2.5 library supports only signed int.