4.3 Tasking Example

The C/C++ example in this section illustrates how the OpenMP task and taskwait directives can be used to compute Fibonacci numbers recursively.

In the example, the parallel region is executed by four threads. The single region ensures that only one of the threads executes the print statement that calls fib(n).

The call to fib(n) generates two tasks (indicated by the task directives). One of the tasks calls fib(n-1) and the other calls fib(n-2) The return values of these calls are added together to produce the value returned by fib(n). Each of the calls to fib(n-1) and fib(n-2) in turn generates two tasks, which are recursively generated until the argument passed to fib() is less than 2.

Note the final clause on each of the task directives. If the final clause expression (n <= THRESHOLD) evaluates to true, then the generated task will be a final task. All task constructs encountered during the execution of a final task will generate included and final tasks. Included tasks will be generated when fib() is called with the argument n = 9, 8, ..., 2. These tasks will be executed immediately by the encountering threads, thus reducing the overhead of placing tasks in the pool.

The taskwait directive ensures that the two tasks generated in the same invocation of fib() are completed (that is, the tasks compute i and j) before that invocation of fib() returns.

Note that although only one thread executes the single directive and hence the first call to fib(), all four threads will participate in the execution of the tasks generated and placed in the pool.

Example 3  Computing Fibonacci Numbers Using Tasks

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

#define THRESHOLD 9

int fib(int n)
{
  int i, j;
 
  if (n<2)
    return n;
 
  #pragma omp task shared(i) firstprivate(n) final(n <= THRESHOLD)
  i=fib(n-1);
 
  #pragma omp task shared(j) firstprivate(n) final(n <= THRESHOLD)
  j=fib(n-2);
 
  #pragma omp taskwait
  return i+j;
}


int main()
{
  int n = 30;
  omp_set_dynamic(0);
  omp_set_num_threads(4);
 
  #pragma omp parallel shared(n)
  {
     #pragma omp single
     printf ("fib(%d) = %d\n", n, fib(n));
  }
}

% CC -xopenmp -xO3 task_example.cc

% a.out
fib(30) = 832040