FPGA開発日記

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

Integrating Prefetcher Selection with Dynamic Request Allocation Improves Prefetching Efficiencyを読む (2)

HPCA 2025で発表された以下の論文を読んでみることにした。

www.computer.org

msyksphinz.hatenablog.com


ここからは、幾つかのアルゴリズムの詳細について読み解いていく:

動的デマンド・リクエストの割り当て方法

デマンド・リクエストが割り当てテーブルに入力されると、PCをキーにテーブルを参照して、UIおよびIA_m状態のプリフェッチャがどれであるかを確認する。 - UI状態であるプリフェッチャについては、保守的なdegreeを使用してプリフェッチ・リクエストを生成する - IA_mであるプリフェッチャについては、より積極的なプリフェッチdegree(c+m+1)を設定する

プリフェッチを挿入する先

キャッシュ空間を効率的に使用するため位、保守的なプリフェッチについては、プリフェッチャが所属するキャッシュ(ほとんどの場合はL1Dであろうと思われる)にプリフェッチリクエストを投入する。 一方、積極的に投入するプリフェッチ (m+1)については、次のレベルのキャッシュ(L2キャッシュなど)に投入する

実行時メトリクスの収集

プリフェッチの精度を把握するために、サンプル・テーブルと、サンドボックス・テーブルというものを使用する。

  • サンプル・テーブル: PCをキーにインデックスする
    • 各プリフェッチャが発行したプリフェッチリクエスト数 (例: IssueByP1) および、後続のデマンド・リクエストでヒットした数 (例: ConfirmedP1)をトラックする
  • サンドボックス・テーブル: 発行されたプリフェッチ・リクエストのアドレスとPC情報を保存する
    • 新しいデマンド・リクエストがこれらのタグと一致した場合、同一のPCかどうかを確認し、一致すればサンプル・テーブルの Confirmedカウンタをインクリメントする。
    • サンドボックス・テーブルはハッシュ関数を採用し、PCアドレスにXORのハッシュ関数を適用することでストレージ・オーバヘッドを削減する。

エポック管理とデッドカウンタ

Alectoは十分な情報が集まるまで状態を更新しない。 このため、デマンド・カウンタを使用して一定のエポック(例えば100リクエスト)単位で割り当てテーブルを更新する。

また、AlectoはIA_m状態のプリフェッチャが長期間プリフェッチを生成しない場合に備え、デッドロックカウンタを持っている。 このカウンタがしきい値に到達すると、該当のプリフェッチャの状態はUIに戻される。

重複プリフェッチ・リクエストのフィルタリング

サンドボックス・テーブルは、重複したプリフェッチを除去するフィルタとしても機能する。 プリフェッチャからの新規リクエストがサンドボックス・テーブルと一致した場合、Alecto はそのリクエストを破棄し、無駄なプリフェッチを防ぐ。 一致しない場合のみ、プリフェッチキューに投入し、キャッシュ階層へデータを送る。

Alectoが適切にプリフェッチャを選択できる理由

  1. 適切なプリフェッチャ識別と割り当て Alecto は各メモリアクセス命令ごとに、割り当てテーブル上でプリフェッチャを個別に状態管理することで、どのプリフェッチャが適切かをきめ細かく判断する。 Alecto は、精度が十分に高い(PBを超える)プリフェッチャを IA 状態に昇格させる。 ただし、常に最も精度が高いものだけを残すのではなく、複数のプリフェッチャが十分な精度を持つ場合は併用を許す。 仮に複数の IA 状態のプリフェッチャが重複して同じデータをプリフェッチした場合でも、Alecto は最終段階でサンドボックス・テーブルによる重複除去を行うため、不要なリクエストは排除される。

  2. 不要な学習の排除 Alecto は、適切でないと判定されたプリフェッチャをIB状態に設定し、その間リクエストを一切受け取れないようにする。 これにより、本来関係のないプリフェッチャに無駄な訓練データが流れ込むことがなくなる。

IB状態のプリフェッチャは、完全に無効化されるのではなく、時間経過とともに状態が回復し、再評価される設計となっている。 これにより、アクセスパタンが変化した場合にも適応できる柔軟性を持つ。

時間的プリフェッチにおける Alecto の応用

時間的プリフェッチャ、つまりプリフェッチを発行するタイミングを予測するプリフェッチャは、一部のリクエストのみを使って訓練すれば十分であることが分かっている。

図6の分類では、メモリ・アクセス・パタンを3つに分類している:

  • 非時間的パタン(Non-temporal):

    • 再現性の低い一過性のアクセス列で構成され、時間的プリフェッチには不要である。
  • 時間的パタン(Temporal):

    • 理論上すべてを扱えるが、発生頻度が低すぎる場合は、保存されたメタデータが有効活用される前に置き換えられてしまうため無駄となる。
  • 他のプリフェッチャが扱えるパタン:

    • ストリーム・ストライド・空間プリフェッチャなど非時間的プリフェッチャが低コストで処理できる場合、時間的プリフェッチャで扱う必要はない。

Alecto は、このような不要なリクエストをイベント③(精度が DB を下回る場合)およびイベント①(より上位のキャッシュヒットなど)で効果的にフィルタする。