1

私は OpenMP を調べ始めたばかりで、タスクについて調べています。ここでの Sun の例は、実際にはシーケンシャル バージョンよりも遅いようです。これは、タスクの作成と管理のオーバーヘッドに関係していると思います。これは正しいです？もしそうなら、アルゴリズムを変更せずにタスクを使用してコードを高速化する方法はありますか?

int fib(int n)
{
  int i, j;
  if (n<2)
    return n;
  else
  {
    #pragma omp task shared(i) firstprivate(n)
    i=fib(n-1);

    #pragma omp task shared(j) firstprivate(n)
    j=fib(n-2);

    #pragma omp taskwait
    return i+j;
  }
}
4

2 に答える 2

6

唯一の賢明な方法は、並列処理を特定のレベルでカットすることです。これを下回ると、オーバーヘッドが実行中の作業よりも大きくなるため、意味がありません。それを行うための最良の方法は、2つの別々のfib実装（たとえば、シリアル実装fib_serとパラレル実装）fibを用意し、指定されたしきい値の下でそれらを切り替えることです。

int fib_ser(int n)
{
  if (n < 2)
    return n;
  else
    return fib_ser(n-1) + fib_ser(n-2);
}

int fib(int n)
{
  int i, j;

  if (n <= 20)
    return fib_ser(n);
  else
  {
    #pragma omp task shared(i)
    i = fib(n-1);
    #pragma omp task shared(j)
    j = fib(n-2);
    #pragma omp taskwait
    return i+j;
  }
}

ここで、しきい値はn == 20です。これは任意に選択され、その最適値はマシンやOpenMPランタイムによって異なります。

ifもう1つのオプションは、次の句を使用してタスクを動的に制御することです。

int fib(int n)
{
  int i, j;
  if (n<2)
    return n;
  else
  {
    #pragma omp task shared(i) if(n > 20)
    i=fib(n-1);

    #pragma omp task shared(j) if(n > 20)
    j=fib(n-2);

    #pragma omp taskwait
    return i+j;
  }
}

これにより、2つの明示的なタスクがオフn <= 20になり、コードがシリアルで実行されますが、OpenMPコード変換によるオーバーヘッドが発生するため、個別のシリアル実装を使用した以前のバージョンよりも実行速度が低下します。

于 2013-02-07T11:38:03.500 に答える
3

おっしゃるとおり、スローダウンはタスクの作成と管理のオーバーヘッドに関係しています。

if(n > 20) を追加することは、タスク ツリーを整理する優れた方法であり、2 番目のタスクを作成しないことで、さらに最適化を行うことができます。新しいタスクが生成されると、親スレッドは何もしません。さらにタスクを作成する代わりに、親タスクが fib 呼び出しの 1 つを処理できるようにすることで、コードを高速化できます。

int fib(int n){
  int i, j;
  if (n < 2)
    return n;
  else{
    #pragma omp task shared(i) if(n > 20)
        i=fib(n-1);

    j=fib(n-2);

    #pragma omp taskwait
    return i+j;
  }
}
于 2013-02-12T23:08:33.773 に答える