5.3 タスク化の例

次の C/C++ プログラムは、OpenMP の task および taskwait 指令をどのように使うとフィボナッチ数列を再帰的に計算できるかを示したものです。

この例では、parallel 指令は 4 つのスレッドにより実行される並列領域を表しています。並列構文中で single 指令が使用され、1 つのスレッドだけが fib(n) を呼び出す print 文を実行することが示されています。

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

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

taskwait 指令は、fib() の呼び出しにより生成された 2 つのタスクの完了 (すなわち、タスクが i と j を計算) が、fib() の呼び出しが戻る前に行われるようにします。

single 指令と fib(n) の呼び出しを行うスレッドが 1 つだけだったとしても、4 つのすべてのスレッドが生成されるタスクの実行に係わっている点に留意してください。

次の例は、Oracle Solaris Studio の C++ コンパイラでコンパイルしました。

例 5-1 タスク化の例: フィボナッチ数列の計算

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

#define THRESHOLD 5

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