6

論文で「誤って予測されたブランチを回避するためにブランチをデータ依存関係に変換する」という文を見ました。（6ページ）

コードをブランチからデータ依存関係に変更する方法を知りたいです。

これは論文です：http ：//www.adms-conf.org/p1-SCHLEGEL.pdf

更新：二分探索で分岐を変換する方法は？

4

2 に答える 2

13

基本的な考え方（私は推測します）は、次のようなものを変更することです。

if (a>b)
    return "A is greater than B";
else
    return "A is less than or equal to B";

の中へ：

static char const *strings[] = {
    "A is less than or equal to B", 
    "A is greater than B"
};

return strings[a>b];

二分探索の分岐について、「通常の」二分探索の基本的な考え方を考えてみましょう。これは通常、（少なくとも漠然と）次のようになります。

while (left < right) {
    middle = (left + right)/2;
    if (search_for < array[middle])
        right = middle;
    else
        left = middle;
}

ここでの分岐のほとんどは、ほぼ同じ方法で取り除くことができます。

size_t positions[] = {left, right};

while (left < right) {
    size_t middle = (left + right)/2;

    positions[search_for >= array[middle]] = middle;
}

left + (right-left)/2[代わりに汎用コードを使用して(left+right)/2ください。]

もちろん、ループ自体の分岐はまだありますが、一般的にはそれほど心配していません。その分岐は予測に非常に適しているため、それを排除したとしても、そうすることで得られるものはほとんどありません。ルール。

于 2012-07-05T17:19:26.793 に答える
1

ブランチの削除は、（特に）このような単純なバイナリ条件であっても、常に最適であるとは限りません。私は以前、さまざまな状況で同様の方法でブランチを削除することを検討しました。ループ内に条件付き分岐があるコードが同等の分岐のないコードよりも高速に実行されるインスタンスに遭遇した後、プロセッサの実行戦略について調査しました。

ARM命令セットには条件付き命令が含まれていることを知っていました。これにより、論文の分岐のないコードの種類よりも条件付き分岐を高速化できますが、私はIntelに取り組んでいました（分岐はcmoveが処理できるものではありませんでした）。 ）。Intelを含む最近のCPUは、通常の命令を条件付き命令に変えることがあります。ブランチの2つのエンドポイントが十分に短い場合、それらは熱心な実行を使用します。つまり、CPUは両方の可能なパスをパイプラインに配置し、両方を実行し、条件がわかった場合にのみ正しい結果を保持します。これにより、配列にインデックスを付けることなく、予測ミスの可能性を回避できます。詳細については、 https：//en.wikipedia.org/wiki/Speculative_execution#Variantsを参照してください。

アセンブリの場合でも、プロセッサに最適なコードを作成するには、プロセッサに関する多くの詳細な知識が必要です。これにより、「ナイーブ」な実装が、特定のCPU特性を見落とす手動で最適化された実装よりも高速になる場合があります。コンパイラの最適化でも同じことが起こり得ます。より複雑な「最適化された」コードを書くと、コンパイラの最適化の一部が壊れ、コンパイラが完全に最適化できる単純な実装よりも実行可能ファイルが遅くなることがあります。

疑問があり、パフォーマンスが重要で時間がある場合は、通常、両方の方法を試して、どちらが速いかを確認するのが最善です。

于 2016-11-03T17:58:29.880 に答える