Alpha 21264は非常に有名なプロセッサで、コンピュータアーキテクチャ系を生業とする者ならば必ず読んでおかなければならないものの一つに入る論文だと聞いている。が、私はまじめに読んだことが無いのでこの際きちんと理解しようと思う。
コラム：ローカル分岐予測器とグローバル分岐予測器
Alpha 21264の分岐予測器は、局所的な相関を取得するための予測器と、大域的な相関を取るための予測機に分けられる。
- 局所的な相関 : 同じ分岐命令の過去の動作に基づいて分岐予測方向を決定する。通常、プログラムカウンタをインデックスとするテーブルを用いる。
- 1レベルの予測機で阿呆ローカルヒストリテーブルのエントリは飽和カウンタであり、最上位ビットを使って予測を行う。
- 21264が採用する2レベル局所予測機は、パターンベースの予測を利用したものである。本文の図4を参照するとわかる。
- 第1レベル : ローカルヒストリテーブルエントリとして使用される、選択されたブヌン位命令の過去10回の分岐方向を示す10ビットのパタンとなる。
- 第2レベル : 第1レベルの10ビットのパタンを用いて第2のテーブル (Local Predictionテーブル) から予測ビットカウンタを取り出す。
図A(1)は、ローカル予測機を用いて予測可能なかんたんな分岐の例を示している。左側の2番目の分岐 (b==0)は、常に成立しない。これは、ローカルヒストリテーブルが全てゼロになっていることを意味する。この分岐を何度も呼び出すと、ローカル予測テーブルのインデックス0にあるカウンタがトレーニングされ、分岐が正しく予測できるようになる。
一方で左側の最初の分岐 (a % 2 ==0)は、実行されるたびに交互に現れる。これは単純な1レベルのローカルヒストリ分岐予測機では正しく予測できず、ヒストリのパタンとして010101010と101010101が登場する。この分岐をダンド化実行すると、ローカル予測テーブルのこれらのインデックスにある予測カウンタが、1つは成立するように、もう一つは不成立となるように予測され、正しく処理を実行することができるようになる。
もう一つはグローバル分岐予測である。1つの分岐命令の過去の動作だけでなく、以前のすべての分岐の動作に基づいて予測を作成する。21264は、過去のすべての分岐命令の記録を追跡することで、グローバル相関を利用する。過去12回分の分岐命令(インオーダ)における記録を使用している。
図A(2)は、グローバルの相関を使用する例となっており、(a==0)と(b==0)の両方の分岐が取られることを想定している。a==b==0の場合には、a==bの分岐がTakenとなることは容易に想像できる。つまり、分岐履歴においてxxxxxx11(最後の2ビットが1)となっていると、a==bはTakenとなると予測できるはずである。十分に分岐命令を実行することで、21264のグローバルカウンタが学習を行い、このような予測が可能となる。
2種類の分岐予測記述を使用しており、最終的にどちらを使用するかを選択する。この選択論理は、分岐命令の履歴でインデックスされたテーブルで、各分岐命令の呼び出しに対して、ローカルまたはグローバルのいずれかを選択する。命令の実行結果に基づいてどちらも学習を行い、どちらを使用するか決定する。
