2018年10月4日

分岐予測の簡単な歴史 – Part 3

A brief history of branch prediction（2017-08-22）

本記事は、原著者の許諾のもとに翻訳・掲載しております。

その他

今回、取り上げなかった方法も沢山あります。皆さんの予想どおりかと思いますが、紹介しなかった方法の方が、紹介したものよりずっと多いのです。紹介しなかった方法については、いくつか簡単に説明し、参考サイトを紹介しますので、さらに学びたい場合はそちらを確認してください。

取り上げなかった主要な概念の１つに、分岐先を予測する方法が挙げられます。これは、無条件分岐（必ず分岐が成立するため、方向の予測が不要な分岐）にも行う必要がある点に注意してください。なぜなら、（いくつかの）無条件分岐は分岐先が分からないからです。

分岐先予測はコストが高くなるため、初期のCPU は”常に分岐は不成立だと予測する”という概念を用いていました。なぜなら、分岐が不成立だと予測すれば、分岐先は不要だからです。”分岐は不成立”と常に予測する方式は精度が落ちますが、それでも全く予測しないよりマシです。

干渉低減方式の中で取り上げていない予測器に、 bi-mode 、 gskew 、 YAGS があります。端的に説明すると、bi-modeは方向によって分岐を区別しようとする点が、多少agreeに似ています。しかしbi-modeの仕組みは、複数の予測テーブルを保持して分岐アドレスに基づく第3の予測器を使い、特定の分岐と分岐履歴の組み合わせに対し、どの予測テーブルを使うか予測するというものです。bi-modeの方がagreeよりも汎用性が高く、成功しているように思われます。gskewは、少なくとも3つの予測テーブルを保持し、異なるハッシュ値で各テーブルにインデックス付けします。つまり、2つの分岐がエイリアスされたとしても、これらの分岐は1つのテーブルにエイリアスされるだけです。そのため、残りの2つのテーブルを使って多数決で予測することができ、テーブルにエイリアスすることで生じる潜在的な悪い結果をオーバーライドできます。YAGSについては、短く説明する術が分かりません。

速度（レイテンシ）の説明はしていないので、小さい/速い予測器を使う予測方法については触れていません。小さい/速い予測器は、遅くて精度の高い予測器が結果を計算するとオーバーライドされる可能性があります。

現在のCPUには、全く異なる分岐予測器を使うものもあります。AMD Zen （2017）や AMD Bulldozer （2011）といったチップはパーセプトロン分岐予測器を使っているようです。パーセプトロンは単相のニューラルネットワークです。

Intel Haswell （2013）は TAGE予測器の一種を使っていると言われています。TAGEは「TAgged GEometric history length predictor」の略語です。ここまでに説明した予測器を使ってプログラムを実行し、正しく予測できない分岐を調べると、主要な分岐は長い履歴を必要としていることが分かります。かなりの数の分岐が数十～数百ビットの履歴を必要とし、いくつかの分岐は1,000ビット以上の分岐履歴を必要とします。単一の予測器や複数の異なる予測器を組み合わせるハイブリッド予測器で1,000ビットの履歴を保持するのは好ましくありません。なぜなら、比較的短い履歴を必要とする大多数の分岐の予測に悪影響を与えるからです（特にコストと比較して）。TAGE予測器の概念は、履歴長が等比数列になるようにし、各分岐が適切な履歴を使えるようにするというものです。これが”GE（GEometric）”の意味です。”TA（TAgged）”の部分は”分岐がタグ付けされている”ことを指しています。この仕組みについては述べませんが、どの分岐が、どの履歴を使うべきかを追跡するために利用されています。

現在では、多くのCPUに専用予測器が備わっています。例えば、一般的な分岐予測器が十分な履歴を格納できず、ループの繰り返しを完璧に予測できない場合も、ループ予測器があれば正確に予測できます。

トレードオフについても全ては語っていません。使う領域と予測性能はトレードオフの関係にあります。テーブルサイズが変わると予測器の性能が向上するだけでなく、予測器の相性も変わってきます。

ワークロードによって影響を受ける分岐予測器が違うことも取り上げませんでした。予測器の性能はテーブルサイズだけでなく、実行するプログラムにも左右されます。

誤予測のコストは是正されるかのように説明しましたが、実際は違います。また、非分岐命令のコストはワークロードによってかなり差が出ます。

できるだけ説明の必要な用語の紹介を避けたので、文献を読むと多少異なる用語が出てくるでしょう。

まとめ

古くからある様々な分岐予測器について説明し、新しい予測器をいくつか端的に紹介しました。ここで説明した昔ながらの予測器のいくつかは、現在のCPUにも使われています。今回の講演が30分ではなく1時間なら、最新の予測器についても語れたでしょう。多くの人がCPUはミステリアスで理解し難いと考えていますが、実際はソフトウェアを理解するよりも簡単だと思います。私はCPUの開発に携わっていたので、先入観があるかもしれません。しかし、私の先入観からではなく、根本的な部分で簡単だと思うのです。

ソフトウェアを複雑にする主な制限要因は想像力です。詳細まで想像することができ、それをプログラミングできれば、ソフトウェアは作れます。もちろん、想像力ではなく、もっと実質的な問題が制限要因となっている場合もあります（大規模なアプリケーションの性能など）。しかし、大多数の人が最も時間を費やすのは、創造力と複雑性の管理能力が制限要因となるプログラミングでしょう。

ハードウェアでは全く異なり、複雑化を避けようとする力が働きます。実装する度に費用がかかるため、できるだけハードウェアを減らそうと考えるのです。さらに、多くのハードウェアで重要視される点は性能です（性能そのもの、または金額や電力などのコストに対する相対的な性能）。そして、複雑になるほどハードウェアは遅くなり、性能が制限されます。今では、5GHzにオーバークロックされた市販のCPUを300ドルで購入できます。5GHzだと、1ユニットオブワークが1/5ナノ秒で終わります。参考までに、光が30センチ進むのにかかる時間が1ナノ秒です。たまにCPUが完璧に作動しない時があると、人々が大慌てしてしまうことも制限要因の1つです。 CPUにもバグはありますが、バグが発生する割合は大概のソフトウェアより非常に少なくなっています。つまり、検証やテストの基準が、かなり高いということです。複雑になるとテストや検証は難しくなります。CPUは普通のソフトウェアより精度の基準が高く設定されているので、複雑性が増すとテストや検証でCPUにかかる負担が非常に大きくなります。そのため、同程度の複雑性を加えた場合のコストは、他の要因を無視したとしても、ハードウェアの方がソフトウェアよりずっと高くなります。

チップの複雑化を避けようとすることで生じる副次的な効果は、任意の”ハイレベル”な汎用CPUの機能は、通常かなり単純な概念でできていて、30分や1時間で語り尽くせてしまうということです。多くのプログラマが考えているより、CPUは簡単です。ところで、”ハイレベル”と言ったのは、かなりの量のローレベル（物理またはソリッドステート）のバックグラウンドがないと理解できないトランジスタや回路の設計を除外するためです。

CPUの内部シリーズ

講演草稿に意見をくれたLeah Hanson、Hari Angepat、Nick Bergson-Shilcockと、投稿原稿のタイピングミスを見つけてくれたFred Clausen Jrに感謝を捧げます。いささか雑な投稿になってしまったことをお詫びします。講演に出席された方が、すぐに講演原稿や参考サイトを見られるよう急いで書き上げたため、通常よりミスが増え、普段の投稿より構成の質が落ちてしまいました。具体的には、講演でアニメーションを使って説明した部分の詳細を、同じレベルで表現できていません。ざっと見たところ、それぞれの予測器がどんな種類の分岐に不適切かという説明が少なく、各予測器を使う動機付けが足りないようです。もう一度見直して、動機付けとなる要素を加えるかもしれませんが、投稿を一から構成し直したり、概念をよりよく伝えるためにテキストの下に載せる図を新しく用意したりすることはないでしょう。大急ぎで書いたこの投稿のタイピングミスを見つけてくれたJulien Vivenot、Ralph Corderoy、Vaibhav Sagar、Mindy Preston、Uri Shakedに感謝の意を表します。