94

この投稿 (StackOverflow の回答) (最適化セクション)を読んだ後、なぜ条件付き移動が分岐予測失敗に対して脆弱ではないのか疑問に思いました。cond move here (PDF by AMD) に関する記事を見つけました。また、彼らは cond のパフォーマンス上の利点を主張しています。動きます。しかし、これはなぜですか？見えません。その ASM 命令が評価される時点では、先行する CMP 命令の結果はまだわかりません。

4

5 に答える 5

76

分岐の予測ミスはコストがかかる

最新のプロセッサは、一般に、問題がなければサイクルごとに 1 ～ 3 個の命令を実行します (これらの命令のデータ依存関係が前の命令またはメモリから到着するのを待ってストールしない場合)。

上記のステートメントは、タイトなループには驚くほどうまく当てはまりますが、これは、サイクルが来たときに命令が実行されるのを妨げる可能性のある追加の依存関係を盲目にするべきではありません: 命令が実行されるためには、プロセッサがフェッチとデコードを開始している必要があります。 15 ～ 20 サイクル前です。

プロセッサが分岐に遭遇したとき、プロセッサは何をすべきか? 両方のターゲットのフェッチとデコードはスケーリングしません (より多くの分岐が続く場合、指数関数的な数のパスを並行してフェッチする必要があります)。そのため、プロセッサは 2 つのブランチのうちの 1 つだけを投機的にフェッチしてデコードします。

これが、予測ミスによる分岐が高くつく理由です。効率的な命令パイプラインのために、通常は目に見えない 15 ～ 20 サイクルのコストがかかります。

条件付き移動は非常に高価になることはありません

条件付きの移動は予測を必要としないため、このペナルティを受けることはありません。通常の命令と同様に、データの依存関係があります。実際、条件付き移動には、通常の命令よりも多くのデータ依存性があります。これは、データ依存性には「条件 true」と「条件 false」の両方のケースが含まれるためです。r1条件付きで に移動する命令の後、r2の内容はの前の値とr2の両方に依存しているように見えます。適切に予測された条件分岐により、プロセッサはより正確な依存関係を推測できます。ただし、データの依存関係が到着するまでに時間がかかる場合でも、通常、到着するまでに 1 ～ 2 サイクルかかります。r2r1

メモリからレジスタへの条件付きの移動は、危険な賭けになる場合があることに注意してください。メモリから読み取った値がレジスタに割り当てられていないという条件の場合、メモリを何も待たずに待機したことになります。しかし、命令セットで提供される条件付き移動命令は、通常、レジスターからレジスターへのレジスターであり、プログラマー側でのこの間違いを防ぎます。

于 2013-01-03T00:15:43.607 に答える
53

命令パイプラインがすべてです。最新の CPU はパイプラインで命令を実行することを思い出してください。これにより、CPU が実行フローを予測できる場合、パフォーマンスが大幅に向上します。

cmov

    add     eax, ebx
    cmp     eax, 0x10
    cmovne  ebx, ecx
    add     eax, ecx

その ASM 命令が評価される時点では、先行する CMP 命令の結果はまだわかりません。

おそらくですが、CPU は、 and命令cmovの結果に関係なく、 に続く命令が直後に実行されることを認識しています。したがって、次の命令は事前に安全にフェッチ/デコードできますが、分岐の場合はそうではありません。cmpcmov

次の命令は、実行する前に実行することもできcmovます (私の例では、これは安全です)。

ブランチ

    add     eax, ebx
    cmp     eax, 0x10
    je      .skip
    mov     ebx, ecx
.skip:
    add     eax, ecx

この場合、CPU のデコーダーが認識したときに、 je .skip1) 次の命令から、または 2) ジャンプ ターゲットから、命令のプリフェッチ/デコードを続行するかどうかを選択する必要があります。CPU は、この前方条件分岐が発生しないと推測するため、次の命令mov ebx, ecxがパイプラインに入ります。

数サイクル後、je .skipが実行され、分岐が実行されます。やばい！私たちのパイプラインは、決して実行してはならないランダムなジャンクを保持しています。CPU は、キャッシュされたすべての命令をフラッシュし、最初からやり直す必要があり.skip:ます。

cmovこれは、実行フローを変更しないため、分岐の予測ミスによるパフォーマンスの低下です。

于 2013-01-03T00:19:50.867 に答える
20

実際、結果はまだわからないかもしれませんが、他の状況 (特に依存関係の連鎖) が許せば、CPU は に続く命令を並べ替えて実行できますcmov。分岐が含まれていないため、これらの命令はいずれの場合も評価する必要があります。

次の例を検討してください。

cmoveq edx, eax
add ecx, ebx
mov eax, [ecx]

に続く 2 つの命令はcmov、 の結果に依存しないため、それ自体が保留中cmovでも実行できます(これをアウト オブ オーダー実行と呼びます)。実行できない場合でも、フェッチしてデコードできます。cmov

分岐バージョンは次のようになります。

    jne skip
    mov edx, eax
skip:
    add ecx, ebx
    mov eax, [ecx]

ここでの問題は、制御フローが変化しており、CPU が、分岐が行われたと誤って予測された場合に、スキップされた命令を単に「挿入」できることを確認できるほど賢くないことです。mov代わりに、分岐後に行ったすべてを破棄し、再起動します。最初から。ここからペナルティが発生します。

于 2013-01-03T00:20:12.170 に答える
3

これらを読むべきです。Fog+Intel では、CMOV を検索するだけです。

Linus Torvald の 2007 年頃の CMOV に対する批判
Agner Fog のマイクロアーキテクチャーの比較
Intel® 64 および IA-32 アーキテクチャー最適化リファレンス マニュアル

短い答え、正しい予測は「無料」ですが、条件付き分岐の予測ミスはHaswellで14〜20サイクルかかる可能性があります。ただし、CMOV は無料ではありません。それでも、トーバルズが怒鳴ったときよりも、CMOV は今の方がはるかに優れていると思います。これまでに回答したすべてのプロセッサで常に正しいものは 1 つもありません。

于 2015-11-17T02:54:32.607 に答える