4.3 タスク化の例

このセクションに記載された C/C++ の例は、OpenMP の task および taskwait ディレクティブをどのように使用するとフィボナッチ数列を再帰的に計算できるかを示したものです。

この例では、並列領域が 4 つのスレッドによって実行されます。single 領域により、スレッドのいずれか 1 つのみが fib(n) を呼び出す print 文を実行するようになります。

fib(n) を呼び出すと、(task ディレクティブで指定された) 2 つのタスクが生成されます。一方のタスクは fib(n-1) を呼び出し、他方のタスクは fib(n-2) を呼び出します。これらの呼び出しの戻り値が加算されて、fib(n) の戻り値が求められます。fib(n-1) および fib(n-2) を呼び出すと、それぞれが 2 つのタスクを生成し、fib() に渡された引数が 2 より小さくなるまでタスクが再帰的に生成されます。

各 task ディレクティブの final 節に注目してください。final 節の式 (n <= THRESHOLD) が true と評価される場合、生成されるタスクは最終タスクになります。最終タスクの実行中に検出された task 構文はすべて、インクルードおよび最終タスクを生成します。fib() が引数 n = 9、8、...、2 で呼び出されたときは、インクルードタスクが生成されます。これらのタスクは、それを検出したスレッドによってただちに実行されるため、タスクをプールに入れるオーバーヘッドが減少します。

taskwait ディレクティブは、同じ fib() の呼び出しで生成された 2 つのタスクが完了 (すなわち、それらのタスクが i と j を計算) してから、fib() の呼び出しが復帰するようにします。

single ディレクティブとそのために fib() の最初の呼び出しを行うスレッドが 1 つだけだったとしても、4 つのすべてのスレッドが、生成されてプールに入れられているタスクの実行にかかわっている点に留意してください。

使用例 4-1  タスクを使用したフィボナッチ数列の計算

#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