2

ランダムな整数の大きな配列をソートする、3 の中央値の標準クイックソート実装を作成しました。少なくとも 1 億要素、できれば 10 億要素まで増やしたいと考えています。速度を上げるために、Cilk++ でアルゴリズムを並列化しようとしています。アルゴリズムは二重再帰を使用し、Cilk タスクを生成して各再帰ソートを実行します。

私のアルゴリズムは、サイズが 10 000 000 までの配列に対して機能します。Cilk キーワードがなければ、シーケンシャル アルゴリズムは 1 億要素を簡単に処理できますが、Cilk を使用しようとすると、プログラムがデスクトップにクラッシュします。その理由をこれから探っていきたいと思います。生成する Cilk タスクが多すぎますか?

Windows 7 64 ビット、Intel++ コンパイラ、および Visual Studio 2010 に統合された Intel Parallel Studio XE 2013 を使用しています。プログラムは 32 ビット アプリケーションとしてコンパイルされています。ランダム データが格納されるメモリは、malloc への単一の呼び出しとして割り当てられ、ポインターがチェックされます。中央値の計算では、中間要素の計算時に整数オーバーフローも防止されます。

これは、ほとんどの場合、バッファ オーバーランの問題です。

これは私のパーティションです:

int pivotvalue = medianOf3(data, low, high);
// pivot is placed next to the last element

int left = low;
int right = high - 1;
while (left < right) {
    while (data[left] < pivotvalue) {
        left++;
        if (left > high) {
            break;
        }
    }
    while (data[right] >= pivotvalue) {
        right--;
        if (right < low) {
            break;
        }
    }

    if (left < right) {
        swap(data, left, right);
    }
}

// restore pivot
swap(data, left, high - 1);
return left;
4

3 に答える 3

3

Cilk がどのように機能するかはわかりませんが、再帰によってスタックがオーバーフローする可能性がある組み込みプラットフォームでのクイックソートの実装を修正する必要があったことを思い出します。修正は、データの小さい方の「半分」に再帰呼び出しを使用し、大きい方の「半分」を関数内で処理することでした (末尾再帰)。コール グラフの深さがリスト内の要素の数に等しいため、並べ替えられた (または逆に並べ替えられた) リストは常にオーバーフローを引き起こします。

デバッガーを使用して、クラッシュの原因を特定できますか? へのエントリごとにデータをログ ファイルにダンプしswap()、クラッシュ前の関数呼び出しを確認できますか? 各呼び出しでスタックのサイズをダンプすることは可能ですか? 各 Cilk タスクには独自のスタックがあり、Cilk 以外のバージョンで使用されるスタックよりも小さい可能性がありますか?

スタックアドレスを使用してパラメーターを追加することにより、スタックの使用状況を追跡できswap()ます。最初の呼び出しと新しい Cilk スレッドは NULL を使用します。各再帰呼び出しは、そのパラメーターが NULL でない場合はそのパラメーターを使用するか、そのローカル変数の 1 つのアドレスを使用して、そのスタックがどこにあるかを確立します。アドレスの違いをダンプするか、グローバルで追跡して、以前の最大値を超えた場合にのみ報告します。

于 2012-11-08T18:39:10.963 に答える
2

両方のサブ問題に対して再帰するN個のアイテムのクイックソートには、（最悪の場合）再帰の深さO（N）があります。通常の修正は、「tomlogic」によって提案されたものです。小さいサブ問題で繰り返し、大きいサブ問題で繰り返します。これにより、再帰の深さがO（lg N）に減少します。

修正は並列バージョンに引き継がれます。シリアルプログラムがスタックスペースSを使用する場合、CilkPlusバージョンは最大でスタックスペースPSを使用します。（このプロパティは、他の多くの並列フレームワークには当てはまりません。）したがって、小さいサブ問題を生成し、大きいサブ問題を反復処理すると、合計スタックスペースがO（P lg N）内に保たれます。

私は、CilkPlusとTBBでのクイックソートの並列実装について説明している本StructuredParallelProgrammingの著者の1人です。クイックソートの例（完全再帰と半再帰の両方）は、http：//parallelbook.com/studentから無料でダウンロードできます。

Arch D. Robison
Intel Corporation
于 2013-02-13T16:39:21.540 に答える
2

Intel Cilk Plus (cilk++ はサポートされていない別の製品です) では、スポーンの深さが 1024 に制限されています。

再帰ツリーでスポーンする深さを決定することは、バランスを取る作業です。作業を盗むことができるように十分な数のスポーンが必要ですが、あまりにも多くのスポーンを使用するとオーバーヘッドが増加します。cilk_spawn は安価ですが、無料ではありません。クイックソートにチェックを追加し、ソートする要素の数がしきい値を下回っている場合は再帰呼び出しを生成しないことをお勧めします。

cilk_for の利点の 1 つは、実行しているワーカーの数に基づいてスポーンの深さを最適化できることです。

- Barry Tannenbaum
  Intel Cilk Plus Runtime Development
于 2013-02-13T15:08:23.567 に答える