3

openMP を使用して、クイックソートを並列に動作させようとしています。openMP の実装後、クイックソートの動作を高速化しようとして失敗し、クイックソートのソート配列がほぼ 2 倍遅くなりました。openMP 実装を使用した私のコード:

void quickSort( int a[], int l, int r) {
    int j;
    if( l < r ) {
#pragma omp parallel
        {
            j = partition( a, l, r);
#pragma omp sections
            {
#pragma omp section
                {
                    quickSort( a, l, j-1);
                }
#pragma omp section
                {
                    quickSort( a, j+1, r);
                }
            }
        }
    }
}

全体の並べ替えはメソッド パーティションで行われ、それがどのように機能するか興味がある場合は、ここにコードが表示されます。

int partition( int a[], int l, int r) {
    int pivot, i, j, t;
    pivot = a[l];
    i = l; j = r+1;     
    while(1) {  
        do ++i; while( a[i] <= pivot && i <= r );
        do --j; while( a[j] > pivot );
        if( i >= j ) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
    }
    t = a[l]; a[l] = a[j]; a[j] = t;
    return j;
}

QuickSortを呼び出す前にメインで時間を取り、メインでprintfの前にタイマーを停止します。スレッド数は 10 に定義されています (PC で 4、2、および 1 で試しました)。0 から 100 までの 1 000 000 個のランダムな整数でリストをソートした後の結果:

時間 (openMP なし) は 6.48004 ～ 5.32001 の間です

openMP の時間は 11.8309 から 10.6239 の間です (2-4 スレッドの場合)。

4

1 に答える 1

3

クイックソートの一般的な考え方は次のとおりです。

[......................]

その要素のリストは2つのタスクに分割されます。

[..........][..........]

そして、各「タスク」は何度も何度も分割されます。

[..][..][..][..][..][..]

現在、CPUは密接に連携しているデータを処理するのが好きです。ただし、各コアがデータPRETTYに密接に連携して動作する場合、1つのコアが別のコアのデータと同じキャッシュラインにあるデータのチャンクに書き込む場合があります。コアが相互にデータを書き込みたくないので、最初の書き込みは他のコアのデータを無効にし、したがって他のコアはRAMのチャンクを再度フェッチする必要があります。

|--- cache line ---|
[..][..][..][..][..][..]
 ^   ^   ^   ^
 |   |   |   |
 c1  c2  c3  c4

したがって、そのキャッシュラインに属するデータに書き込むコアは、最初に他のすべてのコアのデータを無効にします。小さなタスクを[..]かなり近くにすると、無効なキャッシュラインがたくさんあり、メモリからデータが再フェッチされる可能性が高くなります。効果はここではるかによく説明されています

http://fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share

http://lwn.net/Articles/252125/、特に「3.3.4マルチプロセッササポート」もお読みください。

invalidating the cache非並列バージョンでは、データをアクティブに処理しているコアが1つしかないため、この全体は（それほど頻繁には）発生しません。

したがって、考えられる解決策は、コアで効果的に作業するには小さすぎるまでタスクを分割しないことです。考慮しなければならないもう1つの効果：OpenMPはmanagement overheadタスクごとに少し実行する必要があります。タスクが小さすぎる場合は、overhead vs work比率も増やします。

Googleが吐き出したOpenMPベースのクイックソートは次のとおりです。

http://berenger.eu/blog/c-openmp-a-shared-memory-quick-sort-with-openmp-tasks-example-source-code/

それがあなたにインスピレーションを与えますように。

于 2013-02-08T13:14:30.363 に答える