問題タブ [branch-prediction]

私はずっと前にこの質問に出くわしました

並べ替えられた配列の処理が、並べ替えられていない配列の処理よりも速いのはなぜですか?

自分で試してみたいと思いました。さまざまな配列サイズを試してみると、驚くべき結果が得られました。

これがテストコードです。(Microsoftコンパイラを使用したC#、他の言語はテストしていません)

これが出力です。

相対的な結果のタイミングは、通常、リリース モードとデバッグ モードで同じです (デバッグは約 2 倍遅くなります)。

最後の 2 つの結果は、私にとっては理にかなっています。上記でリンクした質問のロジックに従い、ソートされたものは、分岐予測であると想定しているため、より高速に実行されます。ただし、最初の 2 つの結果には混乱しています。なぜほぼ同じ時間なのですか？また、最後の 2 つよりも大幅に高速ではないのはなぜですか? 配列が小さいほど、より近いキャッシュに配置されるため、全体がより高速に実行されると思います。(ループ サイズ * 配列サイズ = 最初の 2 つと最後の 2 つの間で一定であるため、内側の反復回数は同じです)

この質問をするのはこれで 2 回目です。初めて誰かが返信しましたが、返信に時間がかかりすぎたため、完全に理解できませんでした。

私がやろうとしているのは、最新のアーキテクチャの命令フェッチ部分についてもっと学ぶことです。命令フェッチユニットが予測に従ってフェッチするために、すべての命令が分岐予測子によって予測されると仮定します。

予測された命令と一緒に送信されている「分岐命令」について言及するのを手伝おうとした他の紳士。この「分岐命令」は、分岐予測子の予測が正しかったかどうかの条件をテストします。また、これらの分岐命令は分岐実行ユニットに送られ、メモリからのロードは必要ないと仮定します。

私が理解していないのは：

• 分岐実行ユニットは、この命令で推測が正しかったかどうかをどのように知ることができますか?
• それが正しいことを知ったらどうなりますか？
• 分岐命令は予測ごとに発行されますか (基本的には...予測が行われるたびに発行されますか?)
• 分岐予測は、予測された命令の前または後に行う必要がありますか?
• 分岐命令では、メモリからデータをロードする必要がありますか? もしそうなら、それは何ですか？

ありがとう！

Fortran と C でプログラミングを行っていますが、C プリプロセッサは、前処理定数を使用してコードを追加または非表示にする柔軟性が非常に優れていると思います。Fortran でこれを行う方法はわかりませんが、興味があります: Fortran コンパイラは、コンパイル時に削除できるコードを検出しますか?

これを例にとります：

echo の値が変わることはありませんが、コンパイラがこれを認識しない場合でも、実行可能ファイルにデッドで到達不能なコードを含めるだけでなく、毎回分岐をチェックします。明らかに、これは特に分岐予測ではそれほど大きな違いではありませんが、そのような式を追加して、文字通り何も費用がかからないかどうか疑問に思っています。これを行う最適化設定はありますか、それともデフォルトで行われる可能性がありますか?

copy_bit以下の関数を次のように簡略化できますout[out_bit] = in[in_bit]か? (つまり、ifステートメントを使用しない)

更新:明確にするために、これは宿題や提案std::bitsetが質問に答える XY 問題ではありません。

Wavefront が実行されると、きめ細かなマルチスレッドが提供されます。この結果の 1 つは、次のスライドに示すように、分岐予測の要件がないことです。

しかし、私はこれを理解することができません。誰かがこれを簡単に説明できますか？

レイトレーシング衝突テスト カーネル (Cuda、Opencl) で GPU コンピューティング用のカスタム分岐予測アルゴリズムを試した人はいますか?

低深度(2-5)のパフォーマンスについても心配する必要がありますか?

例：

これはハードウェア レベルの予測を超えることができますか? これにより、合計トレース時間を改善できますか?

この疑似コードの「if」文には、「if」を含めないでください。したがって、予測値に応じてゼロまたは実際の値を計算するだけです。

ありがとう。

私はいつも、予測データがどこにどのように保存されているのか疑問に思っていましたか? 制限はありますか？最近のブランチだけですか？私は主に Intel のアーキテクチャに関心がありますが、アーキテクチャについて学べることは何でも歓迎します。

この記事に出くわしました:分岐せずに 2 つの整数の最小値または最大値を計算する

それは「[o]n 一部のまれなマシンでは分岐にコストがかかる...」から始まります。

私は以前、分岐はプロセッサに実行パイプラインのクリアと再起動を強制することが多いため、常にコストがかかると考えていました (たとえば、並べ替えられた配列を処理する方が、並べ替えられていない配列よりも速いのはなぜですか? を参照してください)。

これにより、いくつかの質問が残ります。

• 記事を書いた人はその部分を間違えましたか? それとも、分岐が問題になる前にこの記事が書かれたのでしょうか (日付はわかりません)。
• (x < y) ? x : y最新のプロセッサには、パフォーマンスを低下させることなく、 のような最小限の分岐を完了する方法がありますか?
• それとも、最新のコンパイラはすべて、このハックを自動的に実装するだけですか? 具体的には、Java は何をするのでしょうか? 特にそのMath.min(...)機能はその三項ステートメントであるため...

何度も実行されているループがあります。そのループ内のロジックは、プログラムのモードに依存します。パフォーマンスを向上させるために、関数ポインタの配列 functionPtr[] を初期化できると考えていたので、正しいロジックを実行する functionPtrmode を呼び出すだけです。ループは何サイクルも同じモードに留まります (数は前もって不明ですが、数千に上ります)。このプログラムは intel x64 マシンでのみ実行され、移植性は必要ありません。

CPU が分岐予測を利用することを望んでいましたが、私の分岐は (アセンブリ レベルで) 条件付きではありませんが、分岐の場所は変数 (functionPtr+mode) に依存するためです。CPU は functionPtr+mode を計算し、パイプライン中にそれらの命令を取り込み始めますか?