問題タブ [branch-prediction]

したがって、パイプライン化されたプロセッサの分岐予測で使用される基本的な手法を理解しています-2ビット飽和カウンター、2レベル適応予測器など.

ここに私の質問があります：

1) 分岐ターゲットの予測: なぜこれが重要なのか、またここで使用されているメカニズムにはどのようなものがあるのか​​? 分岐について考えるとき、「bne r2, r3, LABEL」と考えます。これは、r2 != r3 の場合、PC (プログラム カウンター) = PC + LABEL を意味する LABEL に分岐することを意味します。ここでターゲットを予測することの何がそんなに不思議なのですか? コンパイルされた LABEL の値に基づいて、それがどうなるかがわかります。私はおそらくここでポイントを見逃しています。

2) プログラム カウンタ値自体 (例: 0x4001000C)、または少なくともその最後の数ビットが、分岐予測スキームの一部として使用されるのはなぜですか? PC の最後の 4 ビットが (4 ビットの) 分岐履歴レジスタに連結され、その 8 ビットの値がパターン履歴テーブルへのアクセスに使用されるスキームを見ました。PCはかなり恣意的だと​​思います！

これらの問題を理解していただきありがとうございます

以下は、非常に奇妙な動作を示す C++ コードの一部です。奇妙な理由で、(タイミング領域の前に) データを並べ替えると、奇跡的にループがほぼ 6 倍速くなります。

• がなければstd::sort(data, data + arraySize);、コードは 11.54 秒で実行されます。
• 並べ替えられたデータを使用すると、コードは 1.93 秒で実行されます。

(並べ替え自体は、配列を 1 回通過するよりも時間がかかるため、未知の配列に対してこれを計算する必要がある場合、実際には行う価値はありません。)

最初は、これは単なる言語またはコンパイラの異常ではないかと考えたので、Java を試してみました。

同様の結果ですが、それほど極端ではありません。

最初に考えたのは、並べ替えによってデータがキャッシュに取り込まれるということでしたが、配列が生成されたばかりなので、それはどれほどばかげていると思いました。

• 何が起こっている？
• 並べ替えられた配列の処理が、並べ替えられていない配列の処理よりも速いのはなぜですか?

コードはいくつかの独立した用語を要約しているため、順序は重要ではありません。

関連/フォローアップの Q&Aは、異なる/新しいコンパイラとオプションでの同じ効果について:

• ソートされていない配列の処理が、最新の x86-64 clang でソートされた配列の処理と同じ速度なのはなぜですか?
• gcc 最適化フラグ -O3 はコードを -O2 より遅くします

これが私のデモプログラムです：

これは、プログラムの 2 つのバージョンのアセンブリ差分です。1 つはqsortあり、もう 1 つはありません。

アセンブリ出力を理解する限り、並べ替えられたバージョンには に値を渡すため、より多くのコードが含まれていますがqsort、分岐の最適化/予測/その他のものは見られません。多分私は間違った方向を見ていますか？

最近 Epic Answer としてタグ付けされたこの質問とその回答は、私に疑問を抱かせました。CPU 分岐予測の失敗に関して、Windows で実行中のアプリケーションのパフォーマンスを測定できますか? いくつかの静的分析ツールが存在し、分岐予測の状況で優れたパフォーマンスを得るためにコードを最適化するのに役立つ可能性があること、および変更を加えて再テストするだけで手動の手法が役立つことを知っていますが、できる自動メカニズムを探していますWindows アプリケーションの実行中に、一定期間にわたって分岐予測エラーの総数が報告されました。Visual C++ 用のプロファイラー ツールが役立つことを願っています。

この質問のために、問題のアプリケーションは、Visual C++ for Windows などのネイティブ コンパイラでビルドされているか、GCC、FreePascal、Delphi、TurboAssembler などの他のネイティブ コンパイラを使用してビルドされています。実行可能ファイルには、デバッグ情報がまったくない場合があります。おそらく、WMI などの Windows サービスを介して内部 CPU 情報を読み取るか、VirtualBox を使用するなど、Windows を実行する仮想化環境内で完全に実行し、完全にVirtualBox内でテストアプリケーションを使用し、仮想CPUのランタイム分析を行う仮想化Windows環境。または、私が知らない他のテクニック、したがってこの質問。

はい、ググってみました。有望に見える唯一のものは、AMD からのこの PDFです。18ページは、私がやりたいことに非常に近いことを述べていますが、オペレーティングシステムなしで、生の評価用ハードウェアプラットフォームで作業する人向けに書かれているようです:

5.1. 枝。適用性。条件付き分岐の予測ミスは、意思決定ロジックが多いコードでは重大な問題になる可能性があります。

真または偽のパスを選択する可能性がランダムであるか、50-50 の分割に近い場合、条件分岐は誤って予測される可能性があります。分岐予測ハードウェアはパターンを「学習」できず、分岐は正しく予測されません。コレクション。次の表のイベントを収集して、分岐予測のパフォーマンスを測定します。

分岐 次の式を使用して、分岐が行われる割合と分岐あたりの命令数の比率を計算します
。

更新: Intel Core i7 PMU モジュール、または他の CPU の同等の機能を読み取る方法を探していると言えます。Intel VTUNE (Adrian のコメントによる) は、私が求めていたものに非常に近いようです。

私の質問はMysticalの答えから出てきます。私が理解したように、あなたは分岐命令を持っています、それは別の命令に行くことができます、例えばのように、0x123344またはそれは実行を続けることができます。

分岐予測器が過去のパターンからそれらのいずれかから推測した場合、それが間違いを犯したことをどのように認識し、それを元に戻しますか？

私は最近、ここで質問を読みました。ソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか? その答えは非常に魅力的であることがわかり、Data に基づくブランチを扱うときのプログラミングに対する私の見方が完全に変わりました。

私は現在、かなり基本的ですが、C で書かれた完全に機能する解釈された Intel 8080 エミュレーターを持っています。操作の中心は、各オペコードを処理するための 256 の長いスイッチ ケース テーブルです。オペコードのエンコーディングは 8080 命令セット全体で一貫しておらず、デコーディングは多くの複雑さ、不一致、および 1 回限りのケースを追加するため、これが明らかに最速の動作方法であると最初に考えました。プリプロセッサ マクロでいっぱいのスイッチ ケース テーブルは、非常に整然としており、保守が容易です。

残念ながら、前述の投稿を読んだ後、私のコンピューターの分岐予測器がスイッチの場合のジャンプを予測できる方法はまったくないことに気づきました。したがって、スイッチケースをナビゲートするたびに、パイプラインを完全に消去する必要があり、そうでなければ信じられないほど高速なプログラムであるはずの数サイクルの遅延が発生します (私のコードには乗算もありません)。

「ああ、ここでの解決策は簡単です。動的再コンパイルに移行してください」と考えている人がほとんどだと思います。はい、これはスイッチケースの大部分を切り取り、速度を大幅に向上させるようです. 残念ながら、私の主な関心は、古い 8 ビットおよび 16 ビット時代のコンソールをエミュレートすることです (ここでのインテル 8080 は、エミュレートされたコードの最も単純な部分であるため、例にすぎません)。正確な命令を維持するサイクルとタイミングは、ビデオとサウンドとして重要です。これらの正確なタイミングに基づいて処理する必要があります。

このレベルの精度のパフォーマンスを扱う場合、古いコンソールでも問題になります (たとえば、bSnes を見てください)。長いパイプラインを持つプロセッサを扱う場合、これは単なる事実ですか?

これらの 2 つのコード スニペットの間に顕著な速度の違いはありますか? 単純に、2 番目のスニペットの方が分岐命令がはるかに少ないため高速になると思いますが、一方で、分岐予測子はこの問題を解決するはずです。それとも、予測可能なパターンにもかかわらず、顕著なオーバーヘッドが発生しますか? 条件付き移動命令は使用しないものとします。

スニペット 1:

スニペット 2:

これらのケースを自分で最適化するつもりはありませんが、予測可能なパターンであっても分岐のオーバーヘッドについてもっと知りたいです。

私が扱っているアプリケーションには、1 回の実行で 90% の確率で 1 つの分岐のみが実行されるという特性を持つ多数の if ステートメントがあります。

これで、次のようなことを行うことで、特定の CPU の単一の if ステートメントに対する分岐予測の影響をテストできます:-

私の質問は、特定の CPU の実際の大規模なアプリケーションで、複数の if ステートメントを使用して分岐予測のスケーラビリティと影響をテストする方法はありますか?

基本的に、分岐の予測ミスがさまざまな CPU にどれだけのコストをかけているか、およびそれらがアプリケーションに与える影響を把握できるようにしたいと考えています。

だから私はクラスsomeBase{}を持つライブラリを作成しています。これは、多くのクラスのダウンストリームユーザーによって導出されます。

私も持っているのは、someBaseへのポインターのベクトルであり、これを実行しています：-

現在、プロファイリングは、仮想呼び出しでのブランチの予測ミスが、私のコードの（いくつかの）ボトルネックの1つであることを示唆しています。私が探しているのは、どういうわけかオブジェクトのRTTIにアクセスし、それを使用してクラスタイプに従って子のベクトルを並べ替え、命令キャッシュの局所性と分岐予測の両方を改善することです。

これを行う方法に関する提案/解決策はありますか？

覚えておくべき主な課題は次のとおりです：-

1.）someBaseから派生するクラスがどれか、またはいくつになるかはわかりません。仮に、ダウンストリームユーザーが編集して独自のクラスタイプを追加し、それを並べ替えることができる共通ファイルのどこかにグローバル列挙型を含めることができます（基本的には独自のRTTIを実装します）。しかし、それは醜い解決策です。

2.）PiotrNyczは、以下の回答でtype_infoを使用することを提案しています。ただし、そのために定義されているのは！=と==のみです。type_infoで厳密な弱順序を導出する方法に関するアイデアはありますか？

3.）分岐予測と命令キャッシュの局所性を改善することを本当に望んでいるので、別の解決策があれば、それも歓迎されます。

ここから- 分岐予測問題、Python バージョンのプログラムを作成して、Python で並べ替えられたバージョンと並べ替えられていないバージョンの実行時間を確認しました。最初にソートしてみました。

コードは次のとおりです。

私の単純なタイミング方法論の正確さについてはよくわかりませんが、それで十分なようです。arraysize = 32768初めて設定したとき、20分以上待ちました!! 20分以上！しかし、でarraysize = 327、私はの時間を取得し8.141656691sます。

コードのどこかが間違っている場合、または Numpy/Scipy を何らかの方法で使用すると速度が向上するかどうかを修正してください。ありがとう。