102

私は、パフォーマンスが非常に重要なコード (モンテカルロ シミュレーション内で何百万回も呼び出されているクイック ソート アルゴリズム) をループ展開によって最適化しようとしています。高速化しようとしている内部ループは次のとおりです。

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

私は次のようなものに展開しようとしました:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

これはまったく違いがなかったので、より読みやすい形式に戻しました。ループのアンローリングを試みたときも、同様の経験がありました。最新のハードウェアの分岐予測子の品質を考えると、ループの展開が依然として有用な最適化になるのはいつですか?

4

9 に答える 9

136

依存関係の連鎖を断ち切ることができれば、ループ展開は理にかなっています。これにより、故障したまたはスーパースカラーの CPU がより適切にスケジュールされ、より高速に実行される可能性が与えられます。

簡単な例:

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

ここでは、引数の依存チェーンが非常に短いです。データ配列にキャッシュミスがあるためにストールした場合、CPU は待機する以外に何もできません。

一方、このコード：

for (int i=0; i<n-3; i+=4)  // note the n-3 bound for starting i + 0..3
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;
// if n%4 != 0, handle final 0..3 elements with a rolled up loop or whatever

より速く実行できます。1 つの計算でキャッシュ ミスまたはその他のストールが発生した場合でも、ストールに依存しない他の 3 つの依存関係チェーンが存在します。順不同の CPU は、これらを並行して実行できます。

( Agner の命令テーブルとは異なり、Haswell で mulss が 3 サイクルしかかからないのはなぜですか? (複数のアキュムレータを使用した FP ループのアンロール)を参照して、レジスタの名前変更が CPU がその並列性を見つけるのにどのように役立つかを詳しく見てください。最新の x86-64 CPU での FP 内積の詳細と、パイプライン化された浮動小数点 SIMD FMA ALU のスループット対レイテンシ特性. FP 加算または FMA のレイテンシを隠すことは、複数のアキュムレータにとって大きな利点です。多くの場合、SIMD スループットは類似しています。)

于 2010-02-27T22:54:50.723 に答える
27

同じ数の比較を行っているため、それらは何の違いもありません。これがより良い例です。それ以外の：

for (int i=0; i<200; i++) {
  doStuff();
}

書きます：

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

それでもほとんど問題にはなりませんが、現在は 200 回ではなく 50 回の比較を行っています (比較がより複雑になると想像してください)。

ただし、一般的に手動でループをアンロールすることは、主に歴史の産物です。これは、重要なときに優れたコンパイラが実行してくれる機能のリストの 1 つです。たとえば、ほとんどの人はわざわざx <<= 1orx += xの代わりに書くことはありませんx *= 2。書くだけx *= 2で、コンパイラーはそれを最適なものに最適化します。

基本的に、コンパイラを再考する必要性はますます少なくなっています。

于 2010-02-27T22:44:29.153 に答える
15

最新のハードウェアでの分岐予測に関係なく、ほとんどのコンパイラはループ展開を行います。

コンパイラがどの程度の最適化を行っているかを調べることは価値があります。

Felix von Leitner のプレゼンテーションは、このテーマについて非常に啓発的であることがわかりました。読むことをお勧めします。概要: 最近のコンパイラは非常に賢いので、手作業による最適化はほとんど効果がありません。

于 2010-02-27T22:48:39.083 に答える
2

ループの展開は、それが手動の展開であろうとコンパイラの展開であろうと、特に最近の x86 CPU (Core 2、Core i7) では逆効果になることがよくあります。結論: このコードを展開する予定の CPU で、ループ展開を使用する場合と使用しない場合のコードのベンチマークを実行します。

于 2010-02-27T23:40:26.700 に答える
2

私が理解している限り、最新のコンパイラはすでに適切な場所でループをアンロールしています - 例として gcc があり、最適化フラグが渡された場合、マニュアルには次のように書かれています:

コンパイル時またはループの開始時に反復回数を決定できるループを展開します。

したがって、実際には、コンパイラが簡単なケースを実行する可能性があります。したがって、必要な反復回数をコンパイラーが判断しやすいように、できるだけ多くのループを作成する必要があります。

于 2010-02-27T22:50:09.437 に答える
1

知らずにやってみるのは得策ではありません。
この並べ替えは、全体の時間の中で高い割合を占めていますか?

ループのアンロールが行うのは、インクリメント/デクリメント、停止条件の比較、およびジャンプのループ オーバーヘッドを削減することだけです。ループ内で実行していることに、ループ オーバーヘッド自体よりも多くの命令サイクルが必要な場合、パーセンテージでの改善はあまり見られません。

以下は、最大のパフォーマンスを得る方法の例です。

于 2010-02-28T16:41:19.333 に答える
1

ループ展開は、特定の場合に役立ちます。唯一の利点は、いくつかのテストをスキップしないことです!

たとえば、スカラー置換、ソフトウェア プリフェッチの効率的な挿入を可能にすることができます... 積極的に展開することで、実際にどれほど便利になるか (-O3 を使用しても、ほとんどのループで 10% のスピードアップを簡単に達成できます) に驚かれることでしょう。

前にも言ったように、ループとコンパイラに大きく依存し、実験が必要です。ルールを作るのは難しいです (または、展開のためのコンパイラのヒューリスティックが完璧でしょう)。

于 2010-03-01T20:38:44.220 に答える
0

ループの展開は、問題のサイズに完全に依存します。サイズをより小さな作業グループに縮小できるかどうかは、アルゴリズムに完全に依存しています。上記で行ったことは、そのようには見えません。モンテカルロ シミュレーションを展開できるかどうかはわかりません。

ループ展開の良いシナリオは、画像を回転させることです。別々のグループの作業をローテーションできるためです。これを機能させるには、反復回数を減らす必要があります。

于 2010-02-27T22:45:37.543 に答える
0

ループの展開は、ループ内とループの両方に多くのローカル変数がある場合でも役立ちます。ループ インデックス用に 1 つ保存する代わりに、これらのレジスタをさらに再利用します。

あなたの例では、レジスタを使いすぎずに、少量のローカル変数を使用しています。

test比較が重い場合 (つまり、命令ではない場合)、特に外部関数に依存する場合、比較 (ループ終了まで) も大きな欠点です。

ループ展開は、分岐予測に対する CPU の認識を高めるのにも役立ちますが、とにかく発生します。

于 2010-02-27T22:49:40.687 に答える