プリフェッチ機構の原理 ─ ストライド検出から相関予測まで

なぜ「先読み」が必要か

CPUコアの動作周波数に対して、主記憶（DRAM）へのアクセス遅延は桁違いに大きく、メモリ階層の最下層をミスすると数百サイクル待たされます。アウトオブオーダ実行はこの待ち時間に独立した命令を詰め込んで隠そうとしますが、隠せる量には限界があり、メモリ律速のコードでは命令ウィンドウがロード待ちで埋まって停止します。

そこでプリフェッチは、プログラムが実際にそのデータを要求する前に、将来アクセスしそうな番地を予測してキャッシュへ運んでおきます。需要アクセス（demand access）が来たときには既にキャッシュにある状態を作り、ミス遅延そのものを消すのが狙いです。鍵は「何を」「いつ」運ぶかの2点に集約されます。

ストリーム／ストライド検出 ── 等差な番地列を当てる

最も基本的で効果が高いのが、規則的な番地の進み方を捉える方式です。

• ストリームプリフェッチ：連続したキャッシュラインへの単調なアクセス（番地が +1ライン ずつ進む）を検出し、その先のラインを順に先読みする。配列の線形走査やストリーミング処理に強い。
• ストライドプリフェッチ：同じ命令（同じロードPC）が毎回**一定の差分（ストライド）**で番地を進める場合に、その差分を学習して次の番地を予測する。例えば構造体配列を a[i].x のように飛び飛びに舐めると、ストライドは要素サイズになる。

ストライド検出は**RPT（Reference Prediction Table）**でロードPCごとに状態を持つのが定石です。各エントリは「前回の番地」「直前に観測したストライド」「確信度（信頼カウンタ）」を保持します。

ロード命令 PC でRPTを索引:
  delta = 今回の番地 - 前回の番地
  if delta == 記録済みストライド:
      確信度++（飽和）
      確信度が閾値以上なら 次番地 = 今回 + ストライド を先読み
  else:
      新しいストライド候補として記録、確信度をリセット
  前回の番地 = 今回の番地

確信度を挟むのは、たまたま一致した差分で誤った先読みを始めないためです。安定したストライドが続いて初めて発行する設計が、無駄な先読みを抑えます。

プリフェッチ距離とタイムリネス ── 「いつ」が成否を分ける

正しい番地を選んでも、間に合わなければ意味がありません。需要アクセスの直前に発行したのでは、結局DRAM遅延を待つことになります。逆に早すぎると、使う前に他のデータで追い出されたり、まだ価値のないラインでキャッシュを埋めたりします。この「ちょうど良いタイミングで届く」性質をタイムリネスと呼びます。

タイムリネスを決めるのがプリフェッチ距離（prefetch distance）――需要アクセスの何個先まで踏み込んで先読みするか、です。必要な距離は概算できます。

距離を稼ぐ別の手段がプリフェッチ次数（degree）――1回の検出で複数ラインをまとめて発行する量です。距離と次数を上げるほど深い遅延を隠せますが、後述の汚染リスクと引き換えになります。

相関（マルコフ）・空間プリフェッチ ── 不規則だが再現するパターン

ストライドが当たるのは等差な番地列だけです。連結リストや木の走査、ハッシュ表の探索のようなポインタ追跡では、番地の差分はバラバラで、しかし同じアクセス系列が繰り返し再現します。ここを狙うのが相関系です。

• 相関（マルコフ）プリフェッチ：「番地Aの次にBが来た」という遷移を表に記録し、次にAを見たらBを先読みする。アクセス系列を一種のマルコフ連鎖とみなす方式。再現するポインタチェーンを当てられる一方、遷移表が大きくなりがちで、訓練に時間がかかる。
• 空間プリフェッチ（spatial）：ある領域（ページや数KBのリージョン）に初めて触れたとき、過去に「同種の領域でどのオフセットが一緒に使われたか」のビットパターンを呼び出し、その領域内の関連ラインをまとめて運ぶ。SMS（Spatial Memory Streaming）が代表で、構造体内の散在アクセスに効く。

実機の高性能コアは単一方式ではなく、L1にストライド、L2にストリーム＋空間、といった具合に階層ごとに複数のプリフェッチャを併置し、確信度で発行量を調停します。

帯域汚染とキャッシュ汚染 ── 先読みの代償

プリフェッチはタダではありません。当たれば遅延を消すが、外れれば資源を浪費する賭けです。代償は主に2つの「汚染」として現れます。

このトレードオフは3つの指標で評価します。精度（accuracy）＝発行した先読みのうち実際に使われた割合、カバレッジ（coverage）＝本来のミスのうち先読みで消せた割合、タイムリネス＝間に合った割合です。精度を上げれば汚染は減りますが保守的になりカバレッジが落ち、攻めればカバレッジは上がるが汚染が増える――この緊張関係が設計の核心です。

現代の実装は静的な設定で妥協せず、フィードバック制御で動的に調整します。プリフェッチの的中率やキャッシュ汚染の兆候を実行時に観測し、次数・距離・発行可否（スロットリング）をループごとに上げ下げします。帯域が逼迫すれば自動的に控えめになる、という適応が要点です。

ソフトウェアプリフェッチ ── コンパイラと明示制御

ハードウェアが苦手なパターンは、ソフトウェアから明示的に指示できます。x86の prefetcht0/t1/t2/nta や、__builtin_prefetch（GCC/Clang）が代表です。コンパイラやプログラマが、需要アクセスより前にプリフェッチ命令を挿入します。

// 配列を走査しつつ、distance 要素先を先読みする
for (int i = 0; i < n; i++) {
    __builtin_prefetch(&a[i + distance], 0 /*read*/, 1 /*局所性ヒント*/);
    process(a[i]);
}

ソフトウェアプリフェッチの強みは、ハードウェアが学習しにくい間接アクセス（a[index[i]] のようなギャザー）やポインタ追跡で、アプリ側の知識を使って正確に先を指せる点です。一方で弱点もあります。プリフェッチ命令自体が命令スロットとデコード帯域を消費し、distance を手で調整する必要があり、世代が変わると最適値がずれます。

まとめ

• プリフェッチは需要アクセス前にデータをキャッシュへ運び、メモリ遅延を隠す。ストリーム／ストライド検出が規則的な番地列を、相関(マルコフ)・空間方式が不規則だが再現するパターンを当てる。
• 成否はタイムリネスで決まり、プリフェッチ距離（おおよそ メモリ遅延 ÷ 反復時間）と次数が深い遅延を隠す鍵になる。
• 先読みは帯域とキャッシュ容量を消費するため、過剰だと帯域汚染・キャッシュ汚染で逆効果。精度・カバレッジ・タイムリネスを動的なフィードバック制御で調停する。
• ハードウェアが苦手な間接アクセスやポインタ追跡には、__builtin_prefetch などのソフトウェアプリフェッチでアプリの知識を使って明示的に先を指せる。