RISC-VのアウトオブオーダコアであるBOOM (Berkely Out-of-Order Machine) について勉強を進めている。以下のドキュメントを日本語に訳しながら読んでいくことにした。

分岐予測

f:id:msyksphinz:20210505220143p:plain — BOOM Front-end

この章では、BOOMがどのように分岐を予測し、その予測を解決するかについて説明します。

BOOMは、高速なNext-Line Predictor (NLP) と、より遅いが複雑な Backing Predictor (BPD)という2つのレベルの分岐予測を使用します 1 。この場合、 NLPは、Branch Target Bufferで、BPDは、GShare Predictorのようなより複雑な構造です。

The Next-Line Predictor (NLP)

BOOMコアのフロントエンドは命令をフェッチし、次の命令をどこでフェッチするかをサイクルごとに予測します。 BOOMのバックエンドで予測の間違いが検出されたり、 BOOM自身のBacking Predictor (BPD)がパイプラインを別の方向に向かわせたいと考えた場合、フロントエンドにリクエストが送られ、新しい命令パスに沿ってフェッチを開始します。

Next-Line Predictor (NLP)は、命令をフェッチするために使用されている現在のPC(Fetch PC)を取り込み、次のサイクルでどこに次の命令をフェッチすべきかを組み合わせて予測します。予測が正しければ、パイプライン・バブルは発生しません。

NLPは、完全に関連付けられた BTB (Branch Target Buffer)、 Bi-Modal Table (BIM)、 RAS (Return Address Stack) を組み合わせたもので、高速かつ適度に正確な予測を行うことができます。

NLP予測

フェッチPC は、まずタグマッチを実行して、一意に一致するBTBエントリを見つけます。ヒットした場合、BTBエントリはRASと連携して、フェッチパケットで見つかった分岐、ジャンプ、リターンがあるかどうか、フェッチパケットt のどの命令が原因かを予測します。 BIM<Bi-Modal Table (BIM)> は、その予測されたものが、分岐が取られたものか、取られなかったものかを判断するために使用されます。 BTBのエントリーには予測されたPCターゲットも含まれており、これは次のサイクルでフェッチPC として使用されます。

The :term:`Next-Line Predictor`

BIM のヒステリシスビットは、BTBエントリ hit のときと、予測される命令が分岐のときにのみ使用されます。

BTBエントリに return 命令が含まれている場合、RASスタックは予測されたリターンPCを次のフェッチとして提供するために使用されます。実際のRASの管理(いつスタックを使用するか)は外部で管理されます。

面積効率を上げるために、PCタグとPCターゲットの高次ビットは圧縮ファイルに格納されます。

NLPの更新

パイプラインを通過した各分岐は、自分のPCだけでなく、そのフェッチPC ( フェッチパケットの先頭命令のPC) も記憶しています。2

BTBの更新

BTBは、フロントエンドが、分岐ユニット (実行ステージ)または BPD (Fetch ステージの後半)によって、分岐またはジャンプを取るようにリダイレクトされたときにのみ、更新されます。3

分岐成立した分岐命令やジャンプに対応するBTBエントリがない場合は、新しいエントリが割り当てられます。

RASの更新

RASは、フェッチ段階で、フェッチパケットに含まれる命令がデコードされると更新されます。命令が関数呼び出し 4 の場合は、リターンアドレスがRASにプッシュされます。命令がリターンであれば、RASはポップされます。

スーパスカラの分岐予測

NLPが予測を行う場合、実際にはBTBを使用して、予測されたブランチのフェッチPC に対してタグマッチを行っており、分岐命令自体のPCではありません。 NLPは、多くの可能性のある分岐命令のうち、どの命令がPCをリダイレクトする支配的な分岐になるかを、フェッチパケット全体にわたって予測しなければなりません。このような理由から，BTBタグマッチでは，あるブランチのPCではなく，そのブランチのフェッチPC を使用します。5

2:実際には、上位のビットは同じであるため、最下位のビットのみを保存する必要があります。

3:BTBでは、ちょっとした工夫をしています。分岐予測失敗によりPCをリダイレクトする際、この新しいフェッチPC は、新しいBTBエントリのターゲットPCフィールドに書き込まれる必要のあるアップデートPCと同じものです。この「偶然の一致」により、PC圧縮テーブルは単一の検索ポートを使用することができます。つまり、次の予測のためにテーブルを読むと同時に、新しいアップデートPCに適切な高次ビットがすでに割り当てられているかどうかを確認します。

4:RISC-Vには専用のコール命令はありませんが、x1(別名：リターンアドレスレジスタ)へのライトバック先を持つJALまたはJALR命令をチェックすることで、コールを推測することができます。

5:各BTBエントリは、単一のフェッチPC に対応していますが、フェッチパケット全体を予測するのに役立ちます。しかし、BTBエントリは、1つの制御フロー命令上でメタデータとターゲットデータしか格納できません。この設計では、確かに性能に悪影響を及ぼす病的なケースもありますが、フェッチパケット内のどのブランチが :term: フェッチPC に対して支配的なブランチであるかという相関関係があることが前提となっており、少なくともナローフェッチの設計においては、この設計の評価では、性能に目立った損失がなく、非常に複雑になりにくいことが示されています。他のいくつかのデザインでは、代わりにフェッチパケットの各命令に対してBTBのバンク全体を提供することを選択しています。