0

クイックソートの順次バージョンと並列バージョンの両方を実装しました。

私の実装では、クイックソートの最悪のケースで高速化を確認するために使用しました。ソース配列は既にソートされており、私の場合、ピボットは常に配列の最初の要素です。

したがって、パーティションは、ピボットよりも小さい要素を含むセットと、ピボットよりも大きい要素を含むセット、つまり n - 1 要素を含む 2 つのセットを生成します。ここで、n は、クイックソート関数の引数として渡される配列の要素の数です。再帰の深さのサイズは N -1 です。N は、クイックソート関数の引数として渡された元の配列の要素の数です。

Obs: セットは実際には、要素がピボットよりも小さいか、要素がピボットよりも高いかのいずれかに対応する、配列部分の初期位置と最終位置を含む 2 つの変数によって表されます。分割全体がその場で行われているため、処理中に新しいアレイが作成されることはありません。並列のシーケンシャルの違いは、並列バージョンでは、要素がそれらの間で均等に分割される複数の配列が作成されることです (シーケンシャル ケースとしてソートされます)。並列の場合の要素の結合には、アルゴリズムのマージが使用されました。

得られたスピードアップは理論値よりも高く、つまり、2 つのスレッドで達成されたスピードアップはシーケンシャル バージョンと比較して 2 倍以上 (より正確には 3 倍) であり、4 スレッドではスピードアップは 10 倍でした。

私がスレッドを実行したコンピューターは、Ubuntu Linux 10.04、64 ビットを実行している 4 コアのマシン (Phenom II X4) です。コンパイラは gcc 4.4 であり、並列実装用のライブラリ pthread を含めることを除いて、コンパイラにフラグは渡されませんでした。

では、超線形の高速化が達成された理由を知っている人はいますか? 誰かが何か指針を教えてもらえますか？

4

2 に答える 2

2

2つのスレッドと1つのスレッドで3倍のスピードアップが見られ、4つのスレッドと1つのスレッドで10倍のスピードアップが見られる場合は、何か怪しいことが起こっています。

アムダールの法則によれば、スピードアップは1 /（1-P + P / S）です。ここで、Pはアルゴリズムの並列部分であり、Sは並列部分のスピードアップ係数です。4つのコアに対してS=4（可能な限り最良の結果）であると仮定すると、P = 2.5であることがわかります。これは不可能です（0から1の間でなければなりません）。

言い換えると、4コアで10倍の改善が得られる場合は、1つのコアを使用して4つのコアをシミュレートし、2.5倍（またはその前後）の改善を得ることができます。

別の言い方をすれば、1秒間に4つのコアを実行すると、10秒間に1つのコアよりも少ない操作が実行されます。したがって、並列バージョンは実際に実行する操作が少なくなります。その場合、シリアルバージョンも実行する操作が少なくなる理由はありません。

考えられる結論：

  • シーケンシャルバージョンに問題がある可能性があります。おそらく、最適化が不十分です。

  • 並列バージョンに問題がある可能性があります。それらは正しくない可能性があります。

  • 測定が正しく行われない可能性があります。これは非常に一般的です。

不可能な結論：

  • このアルゴリズムは超線形にスケーリングします。
于 2012-06-25T03:41:24.517 に答える
2

パフォーマンス アナライザーを使用してこれをより詳細に調べるのが実際には最善ですが、私の最初の推測では、この種の超直線的な速度向上は、スレッドを追加するとより多くのキャッシュ スペースが得られるという事実によって引き起こされるということです。そのようにして、より多くのデータがキャッシュから読み取られます。メモリ転送のコストは非常に高いため、これによりパフォーマンスを簡単に向上させることができます。

アムダールの法則を使用して最大スピードアップを評価していますか?

お役に立てれば。

于 2012-06-25T03:35:10.127 に答える