Task Decomposition Algorithm Strategies¶

Some threaded programs have some form of task decomposition, that is, delineating which threads will do what tasks in parallel at certain points in the program. We have seen one way of dictating this by using the conductor-worker implementation strategy, where one thread does one task and all the others to another. Here we introduce a more general approach that can be used.

16. Task Decomposition Algorithm Strategy using OpenMP section directive¶

This example shows how to create a program with arbitrary separate tasks that run concurrently. This is useful if you have tasks that are not dependent on one another. However, more sophisticated examples could have some dependence, such as producer-consumer problems.

/* sections.c
      * ... illustrates the use of OpenMP's parallel section/sections directives,
      *      which can be used for task parallelism...
      *
      * Joel Adams, Calvin College, November 2009.
      *
      * Usage: ./sections
      *
      * Exercise: Compile, run (several times), compare output to source code.
      */

#include <stdio.h>
      #include <omp.h>
      #include <stdlib.h>

int main(int argc, char** argv) {

printf("\nBefore...\n\n");

#pragma omp parallel sections num_threads(4)
              {
                      #pragma omp section
                      {
                              printf("Task/section A performed by thread %d\n",
                                              omp_get_thread_num() );
                      }
                      #pragma omp section
                      {
                              printf("Task/section B performed by thread %d\n",
                                              omp_get_thread_num() );
                      }
                      #pragma omp section
                      {
                              printf("Task/section C performed by thread %d\n",
                                              omp_get_thread_num() );
                      }
                      #pragma omp section
                      {
                                      printf("Task/section D performed by thread %d\n",
                                                      omp_get_thread_num() );
                      }
              }

printf("\nAfter...\n\n");

return 0;
      }

In this example we know there are 4 separate tasks, so we added the clause num_threads(4) to the pragma.

Summary Overview¶

This final patterlet example is now added to the diagram under Program Structure Implementation Strategy Patterns as Task Decomposition. We also added the example 5 that used the Conductor-Worker pattern as also being a type of task decomposition.

Note

You might be wondering where the box on the lower right, SIMD architecture, applies. Another parallel computing device, GPU cards, have this type of architecture. We provided a few code examples in the PDC for Beginners book to introduce these and the CUDA programming laguage that goes with them. In future chapters and books we will return to examples for programming on GPUs.