UDP: Utility-Driven Fetch Directed Instruction Prefetchingという論文を読んで、FDIP (Fetch Directed Instruction Prefetching) について学ぶことにした。

FDIP (Fetch Directed Instruction Prefetching)とは何なのか

FDIPというのは、CPUにおけるフロントエンドのフェッチ効率を上げるための技術だ。名前の最後に「Prefetching」とついている通り、フロントエンドで命令をプリフェッチするための技術である。

このFDIPの前提として、フロントエンドの「命令アドレスを予測する」という動作と「命令をフェッチする」を分離する「Frontend Decoupling」という技術が一緒に説明されることが多い。この2つを分離し、FTQ(Fetch Target Queue)で互いにつなげる。「命令アドレス予測」(命令フェッチのフロントエンド)の処理が、「実際の命令フェッチ」(命令フェッチのバックエンド)よりも先に進むことができる、というのがこの構造の特徴で、命令フェッチのフロントエンドが、命令フェッチのバックエンドに影響されることなく、さらに「先読みのための」時間的余裕を作る、というのが目的だ。

逆に言うと、もし命令アドレスの生成と実際のフェッチ動作を分離していないと、命令フェッチ処理のストールが命令アドレスの生成処理にも影響を与えてしまうことになる(次のアドレスの命令予測を止めてしまう、など)、それを防ぐために、ある程度余裕のあるFTQを間にかませることで、フェッチアドレスの予測を止めないようにするのが、Decoupled Frontendの特徴だ。

Decoupled Frontendにより、命令フェッチフロントエンドは命令フェッチバックエンドよりも先に進める。典型的には、実フェッチ側のスループットには上限がある一方、予測側はより先の fetch block 列を先行して生成できる。ここでいう命令フェッチブロックというのは、「固定サイズの命令バイト列(32Bなど)」で「ブロックの終端が最初のtaken予測」というものである。

命令フェッチフロントエンド（分岐予測器側）は、予測で生成した fetch block を FTQ の tail に次々 enqueue していく。一方で、実際の命令フェッチは FTQ の head から順にエントリを消費していく。

FDIPは FTQ の将来エントリをスキャンし、対応する fetch block が I$ に存在するか（あるいは既に取得中か）をプローブする。存在しなければプリフェッチを発行する。もし存在していなければプリフェッチを発行する。これにより、実際にそのアドレスが必要になる前に、プリフェッチを発行することで、命令フェッチのレイテンシを隠ぺいすることができるという訳だ。

FTQの深さで、timelinessが変わる

ここで、FTQの深さによってプリフェッチのtimelinessが変わるというポイントがある。極端に言えば、FTQが深ければ、より未来にアクセスするブロックを先に見つけてプリフェッチできるというものだ。

しかし一方で、より深いFTQも考え物になってくる。FTQが深くなり、より多くの命令アドレスを格納できるようになったとしても、それが正確であるかどうかとは別物であるからだ。つまり、不正確なアドレスを予測し命令をプリフェッチしてしまうことで、命令キャッシュを汚染してしまう可能性があるということになる。

これにはいくつかの要因がある

BTBミスの場合、「このブロック内のどこに分岐があるか／どこでブロックを切るか」が見えなくなる。その結果、分岐で止まるべきところで止まれず、fall-through方向に直進して“巨大な基本ブロック”のように振る舞ってしまう。
分岐予測ミスの場合、つまり分岐命令であることが認識できても、分岐予測ミスをした場合である。実際問題分岐予測がミスしたかどうかはCPUパイプラインのバックエンドまで命令が到達しないと判断できず、それまでは予測に基づいて誤ったプリフェッチを出し続ける可能性がある。

ここで、「じゃあBTBミスだったらFDIPの積極性を下げればいいじゃん」と思うかもしれないが、これもまた難しい。このポイントは、「FTQを深くすることにより発生するoff-pathは命令キャッシュを汚染する可能性があるが、すべてが悪ではない」というものである。特に、誤予測後でも制御フローが merge point（合流点）で再び合流する場合、off-path側で取ってきた命令が後でon-path側で再利用され、結果的にtimelyなprefetchになることがある。

useful: on-path demandが、そのprefetchに（I$またはfill-buffer/MSHRで）ヒットする
unuseful: 需要に使われないままI$から追い出される（汚染に近い）

これらのoff-pathの状況はワークロードにより極端に異なることが分かっている。

verilator: off-pathが約90%でも utility ratio が 0.6（=60%は有用）
xgboost: utility ratio が 0.1（=ほとんどが汚染）

ということになり、FDIPの積極性を調整することが、すべての最適解になるとは限らない。