FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

Alpha EV8の分岐予測機に関する論文を読む(2. 並列分岐予測の難しさ)

Alpha EV8の分岐予測機に関する論文を読み始めた。

ieeexplore.ieee.org

msyksphinz.hatenablog.com

第2章と第3章は適当に人力で日本語化した。つまり並列度が非常に高まった分岐予測は難しいということだろう。 細かい所は英語をちゃんと読もうとしてもよくわからん。


2. Alpha EV8フロントエンドパイプライン

Alpha EV8は高い性能を維持するために、最大で2つの8命令ブロックを命令キャッシュからフェッチすることができる。命令フェッチブロックは連続的な命令を命令キャッシュからフェッチする:命令フェッチブロックは、8命令ブロックアラインの最後もしくは分岐が成立すると予測した制御フロー命令で終了する。分岐が成立しないと予測される分岐命令はフェッチブロックの最後とはならず、したがって1サイクルで最大で16個の条件分岐命令がフェッチされて予測されている。

各サイクルにおいて、次の2つのフェッチブロックが生成されなければならない。これを1サイクルで達成するために非常に高速なハードウェアが動作する。Alpha EV8では、この目的のためにライン予測を使用する。ライン予測器は最近のフェッチブロックのアドレスによってインデックスされた3つのテーブルと、非常に限定されたハッシュ論理によって構成されている。後続の簡単なインデックス論理によって予測の精度が比較的減少する。

低精度な分岐予測器の精度と、分岐解決のレイテンシ(Alpha EV8のパイプラインでは分岐命令の結果は最も早くて14サイクル必要で、より長い場合は20から25サイクル必要となる)を解決するために、ライン分岐予測器をバックアップするための強力なプログラムカウンタ(PC)アドレス生成器を持っている。これは条件分岐予測機と、ジャンプ予測器、リターンアドレススタック予測、ターゲットアドレス計算の条件分岐予測と最終的なアドレスセレクタが含まれている。PCアドレス生成は2サイクルでパイプライン化されており、これは図1に示されている: 最大で4つの動的な後続のフェッチブロックA,B,C,Dが同時にPCアドレス生成器にインフライトとなり、命令フェッチはPCアドレス生成の結果に基づいて再実行される。

3. グローバル・ローカル履歴

Alphaマイクロプロセッサの前世代においては、グローバル分岐履歴とローカル分岐履歴の両方を使用したハイブリッド分岐予測機を使用していた。Alpha EV8では、最大で16個の分岐命令の予測結果(フェッチブロックあたり8命令)を1サイクル辺りに予測する。EV8においてローカル履歴に基づいて実装するのは難しいものがある。

ローカル分岐予測器では、ローカル履歴テーブルを読み込み、予測テーブルを読み込む。16このローカル履歴を同時に読み込むには、デュアルポートの履歴テーブルが必要となる。1ポートで1フェッチブロックを使用するが、16個の分岐予測テーブルを読み込むには、16ポートの予測テーブルが必要となる。

分岐命令がインフライトとなるたびに、より若いインフライトな分岐命令は投機的なヒストリを使用する必要がある。投機的なローカル履歴を使用することにより、すでに十分にプロセッサのフェッチと予測を1サイクル毎に実行するために複雑になっている。Alpha EV8では、移入ライトな分岐命令の数はインフライト可能な命令の数と等しい(つまり256以上となる)。さらに、EV8では分岐予測機が最大で3つのフェッチブロックをインデックスし、(投機的な)分岐の結果は決まっていない(図1を参照のこと)。これら3つのブロックは最大で3つ前の連続的なフェッチブロックを持つ可能性がある。一方で、単一の投機的なグローバルヒストリ(スレッドあたり)は第8節で示すようにより簡単に作ることができ、EV8のグローバル履歴予測の構造の精度は、古いグローバル履歴の3つのフェッチブロックに仮想的に鈍感であると言える。

最後に、Alpha EV8は同時マルチスレッドプロセッサである。独立したスレッドが動作しているときに、予測テーブルエントリを奪い合っている。ローカル履歴をベースとする構造においてこのような干渉は、ローカルヒストリと分岐予測テーブルを汚染するため悲惨な結果を招く。さらに、1つのアプリケーションからいくつかの並列なスレッドが生成されると、PCおよびスレッド番号によってインデックスされる履歴テーブルはより悪化する。一方で、グローバル履歴の構成は、グローバルヒストリレジスタはスレッド毎に構成されるべきであり、同一アプリケーションにおける並列スレッドはconstructive aliasingの恩恵を受ける。