3

OpenMPでのクイックソートに関連するコードを次のように記述しました。

#include <iostream>
#include <ctime>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
#include <omp.h>

void ParallelQuickSort(int *begin, int *end)
{
    if (begin+1 < end) 
    {
        --end;
        int *middle = partition(begin, end, bind2nd(less<int>(), *end));
        swap(*end, *middle);
        #pragma omp task shared(begin) firstprivate(middle)
            ParallelQuickSort(begin, middle);
        #pragma omp task shared(end) firstprivate(middle)
            ParallelQuickSort(++middle, ++end); 
    }
}

int main()
{
    int n = 200000000;

    int* a = new int[n];

    for (int i=0; i<n; ++i)
    {
        a[i] = i;
    }

    random_shuffle(a, a+n);
    cout<<"Sorting "<<n<<" integers."<<endl;

    double startTime = omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single
            ParallelQuickSort(a, a+n);
    }
    cout<<omp_get_wtime() - startTime<<" seconds."<<endl;

    for (int i=0; i<n; ++i)
    {
        if (a[i] != i) 
        {
            cout<<"Sort failed at location i="<<i<<endl;
        }
    }

    delete[] a;
    return 0;
}

私がコードで抱えている問題は、ParallelQuickSort関数内のタスク構成のデータ属性です。変数middleは、2つのタスクを実行するスレッドによって変更される可能性があるため、firstprivate代わりに使用する必要があります。sharedただし、コードに示されているように変数の開始と終了を設定するとshared、プログラムは失敗します。なぜ彼ら（beginと）はの代わりにendすべきなのだろうか。私の見解では、2つのタスクを実行するスレッドはそれぞれ変数とを保持するため、相互に影響を与えることはありません。一方、関数は再帰的であるため、変数またはfirstprivatesharedbeginendParallelQuickSortbeginend（たとえば、親関数と子関数で）。変数が異なる関数（親関数と子関数）にあるため、この容疑者についてはよくわかりません。

4

1 に答える 1

2

まず、特定の領域にあると判断された変数privateは自動的firstprivateに明示的なタスクに含まれるため、明示的にとして宣言する必要はありませんfirstprivate。次に、コードにが含まれ++end;、--end;の値が変更され、がの場合はend他のタスクに影響します。ここでの正しいデータ共有クラスです。各タスクは、の値を保持するだけであり、タスクが作成されたときにそれらが持っていた値を保持します。endsharedfirstprivatebeginendmiddle

あなたParallelQuickSortはこれと同じくらい単純でなければなりません：

void ParallelQuickSort(int *begin, int *end)
{
    if (begin+1 < end) 
    {
        --end;
        int *middle = partition(begin, end, bind2nd(less<int>(), *end));
        swap(*end, *middle);
        #pragma omp task
            ParallelQuickSort(begin, middle);
        #pragma omp task
            ParallelQuickSort(++middle, ++end); 
    }
}

このコードは機能しますが、シングルスレッドバージョンよりもはるかに遅いことに注意してください。大きなXeon X7350（Tigerton）ボックスで2スレッドを使用した場合は88.2秒であるのに対し、シングルスレッドを使用した場合は50.1秒です。その理由は、タスクの作成は、2つの配列要素を交換するという非常に単純なタスクまで続くためです。タスクを使用するオーバーヘッドは非常に大きいため、サブアレイのサイズが1024要素に達した場合など、タスクを無効にするための適切な上限しきい値を設定する必要があります。正確な数は、OpenMPランタイムの実装、CPUタイプ、およびメモリ速度によって異なるため、1024の値は多かれ少なかれランダムに選択されます。それでも、最適値は、同じキャッシュラインに含まれる要素を処理する2つのタスクを作成するべきではないため、要素の数は16の倍数（キャッシュラインあたり64バイト/整数あたり4バイト）である必要があります。

void ParallelQuickSort(int *begin, int *end)
{
    if (begin+1 < end) 
    {
        --end;
        int *middle = partition(begin, end, bind2nd(less<int>(), *end));
        swap(*end, *middle);
        #pragma omp task if((end - begin) > 1024)
            ParallelQuickSort(begin, middle);
        #pragma omp task if((end - begin) > 1024)
            ParallelQuickSort(++middle, ++end); 
    }
}

この変更により、コードは同じボックス上の2つのスレッドで34.2秒間実行されます。

于 2012-11-19T08:44:51.130 に答える