22

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

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

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

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

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

4

4 に答える 4

12

それどころか、ステートメントはジャンプテーブルswitchに変換される可能性があります。つまり、ステートメントはおそらく数秒（範囲チェック用）と1回のジャンプを実行します。悪いオペコードが発生する可能性は低いため、分岐予測で問題が発生することはありません。ジャンプはパイプラインとそれほど友好的ではありませんが、結局、それはステートメント全体の1つにすぎません。ififswitch

switchオペコードの長いステートメントを、パフォーマンスの向上につながる他の形式に変換できるとは思いません。もちろん、これは、コンパイラがジャンプテーブルに変換するのに十分賢い場合です。そうでない場合は、手動で行うことができます。

疑わしい場合は、他の方法を実装してパフォーマンスを測定してください。

編集

まず、分岐予測と分岐ターゲット予測を混同しないように注意してください。

分岐予測は、分岐ステートメントでのみ機能します。分岐条件が失敗するか成功するかを決定します。彼らはジャンプステートメントとは何の関係もありません。

一方、分岐先予測は、ジャンプがどこに到達するかを推測しようとします。

したがって、「分岐予測子がジャンプを予測できる方法はありません」というステートメントは、「分岐ターゲット予測子がジャンプを予測できる方法はありません」である必要があります。

あなたの特定のケースでは、私はあなたが実際にこれを避けることができるとは思わない。操作のセットが非常に少ない場合は、論理回路で行われる操作のように、すべての操作をカバーする式を考え出すことができます。ただし、CPUと同じ大きさの命令セットを使用すると、たとえそれがRISCであったとしても、その計算のコストは1回のジャンプのペナルティよりもはるかに高くなります。

于 2012-07-26T11:31:52.053 に答える
10

256 方向の switch ステートメントの分岐が密集しているため、コンパイラはこれをジャンプ テーブルとして実装します。したがって、このコードを通過するたびに単一の分岐予測ミスをトリガーするという点で正しいです (間接ジャンプとして予測可能な動作は表示されません)。これに関連するペナルティは、最新の CPU (Sandy Bridge) で約 15 クロック サイクル、または micro-op キャッシュがない古いマイクロアーキテクチャでは最大 25 クロック サイクルになります。このようなことについては、agner.org の「ソフトウェア最適化リソース」が参考になります。「C++ でのソフトウェアの最適化」の 43 ページから始めるのがよいでしょう。

http://www.agner.org/optimize/?e=0,34

このペナルティを回避できる唯一の方法は、オペコードの値に関係なく、同じ命令が確実に実行されるようにすることです。これは多くの場合、条件付き移動 (データの依存関係を追加するため、予測可能な分岐よりも遅くなります) を使用するか、コード パスの対称性を探すことで実行できます。あなたがやろうとしていることを考えると、これはおそらく不可能であり、もしそうなら、ほぼ間違いなく、予測ミスの 15 ～ 25 クロック サイクルよりも大きなオーバーヘッドが追加されます。

要約すると、最新のアーキテクチャでは、スイッチ/ケースよりも効率的にできることはあまりなく、分岐の予測を誤った場合のコストは、期待するほど大きくはありません。

于 2012-07-26T11:42:20.507 に答える
7

間接ジャンプは、おそらく命令のデコードに最適です。

1997 年の Intel P6 などの古いマシンでは、間接的なジャンプで分岐の予測ミスが発生する可能性があります。

Intel Core i7 などの最新のマシンでは、分岐の予測ミスをかなりうまく回避する間接ジャンプ予測子があります。

しかし、間接分岐予測子を持たない古いマシンでも、いたずらをすることができます。ちなみに、このトリックは、Intel P6 の時代から Intel Code Optimization Guide に記載されています (だった):

次のようなものを生成する代わりに

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

としてコードを生成します

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

つまり、命令フェッチ/デコード/実行ループの先頭へのジャンプを、各場所のループの先頭にあるコードに置き換えます。

間接的な予測子がない場合でも、これははるかに優れた分岐予測を行うことがわかります。より正確には、条件付きの単一ターゲットの PC インデックス付き BTB は、後者のスレッド化されたコードで、間接ジャンプのコピーが 1 つしかない元のコードよりもはるかに優れています。

ほとんどの命令セットには特殊なパターンがあります。たとえば、Intel x86 では、ほとんどの場合、比較命令の後に分岐が続きます。

頑張って楽しんでね！

(念のために言っておきますが、業界の命令セット シミュレーターで使用される命令デコーダーは、ほとんどの場合、N ウェイ ジャンプのツリー、またはデータ駆動型デュアルを実行し、ツリー内の各エントリを指して、N ウェイ テーブルのツリーをナビゲートします。他のノード、または評価する関数に。

ああ、おそらく言及する必要があります: これらのテーブル、これらの switch ステートメントまたはデータ構造は、特別な目的のツールによって生成されます。

ジャンプ テーブルのケース数が非常に多くなると問題が発生するため、N ウェイ ジャンプのツリー - 1980 年代に作成したツール mkIrecog (命令認識ツールの作成) では、通常 64K までのジャンプ テーブルを作成しました。つまり、16 ビットでジャンプします。当時のコンパイラは、ジャンプ テーブルのサイズが 16M (24 ビット) を超えたときに壊れました。

データ駆動型、つまり他のノードを指すノードのツリー。(a) 古いマシンでは間接的なジャンプがうまく予測できない可能性があり、(b) 多くの場合、命令間に共通のコードがあることが判明したためです。命令ごとにケースにジャンプし、次に共通コードを実行し、次に切り替えて、2 番目の予測ミスを取得するときの分岐予測ミスでは、わずかに異なるパラメーター (命令ストリームの何ビットを消費するかなど) を使用して共通コードを実行します。ここで、次に分岐するビットのセットは (are) です。

私は mkIrecog に非常に積極的でした。スイッチで最大 32 ビットを使用できるようにすると言っていましたが、実際の制限により、ほとんどの場合 16 ～ 24 ビットで停止しました。最初のデコードは 16 ビットまたは 18 ビットの切り替え (64K ～ 256K エントリ) であることがよくありましたが、他のすべてのデコードははるかに小さく、10 ビット以下でした。

うーん: 1990 年頃に mkIrecog を Usenet に投稿しました 。(親切にしてください: 私は当時若かったです。これが Pascal だったのか C だったのか思い出せません。それ以来、何度も書き直しましたが、C++ ビット ベクトルを使用するようにはまだ書き直していません。)

私が知っているこの種のことを行う他のほとんどの人は、一度に 1 バイトずつ処理を行います。つまり、8 ビット、256 ウェイ、ブランチまたはテーブルのルックアップです。)

于 2013-04-03T22:28:40.453 に答える
2

誰も言及しなかったので、何かを追加すると思いました。

確かに、間接ジャンプが最良の選択肢である可能性が高いです。

ただし、N-compare の方法を使用する場合、次の 2 つのことが頭に浮かびます。

まず、N 回の等値比較を行う代わりに、log(N) 不等値比較を行い、二分法による数値オペコードに基づいて命令をテストすることができます (または、値空間が完全に近い場合はビットごとに数値をテストします)。ハッシュテーブルのように、最終的な要素を見つけるために静的ツリーを実装します。

2 つ目は、実行したいバイナリ コードの分析を実行することです。実行前にバイナリごとに実行し、エミュレータにランタイム パッチを適用することもできます。この分析では、命令の頻度を表すヒストグラムが作成され、最も頻繁に使用される命令が正しく予測されるようにテストを整理します。

しかし、MOV の 99% があり、他のテストの前に MOV オペコードを同等にしない限り、これが 15 サイクルの中程度のペナルティよりも速いとは思えません。

于 2013-01-25T17:02:32.947 に答える