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

www.computer.org

Integrating Prefetcher Selection with Dynamic Request Allocation Improves Prefetching Efficiency

日本語訳: 動的リクエスト割当を統合したプリフェッチャ・セレクションを統合することによるプリフェッチ効率の改善

この論文は、ハードウェア・プリフェッチャの最適化に焦点を当てている。従来、ハードウェア・プリフェッチャは複数種類のものが実装され、ハイブリッド型のプリフェッチ構成が採用されている。しかし、この方式にはいくつかの問題点が残されている。

リクエストの入力割り当てが不正確である
プリフェッチャの選択基準が粗粒度である

それぞれの問題については、具体的に後で説明する。

これらの問題を解決するためのプリフェッチャ選択アルゴリズムである Alecto を提案する。各プリフェッチャに対して適切なデマンド・リクエストを割り当てることにより、プリフェッチの効率を最大化する。

評価結果では、Alectoは強化学習ベースの選択アルゴリズムBanditと比較して高い性能を発揮することが判明した。

シングルコアにおいて2.76%の性能向上
8コア環境において7.56%の性能向上
メモリ集約型ベンチマークでは5.25%の性能向上

背景

ハードウェア・プリフェッチャには様々な種類がある。

ストリーム・プリフェッチャ: 連続的なアドレス(ストリーム)を捉える
ストライド・プリフェッチャ: 規則的な間隔(ストライド)を捉える
空間プリフェッチャ
時間プリフェッチャ

課題

様々なメモリアクセスパタンに対応するために、これらのプリフェッチャは併用される。理想的にはそれぞれのプリフェッチャが独立に、自分の専門とするパタンを効率よく処理することである。しかし、それには以下のような課題が存在する。

プリフェッチャのメタデータ領域が無駄に消費される
- あるプリフェッチャが本来の対応範囲外リクエストを受け取ると、無駄にプリフェッチャが学習してしまう。
- 他のプリフェッチャと重複したリクエストが生成されてしまう
プリフェッチャ間で内部リソースを共有することによる干渉
- プリフェッチ・テーブルなどのを複数のプリフェッチャで共有すると、互いに動作を阻害する

既存手法の問題

既存手法は以下の点において不十分である (DOL, IPCP, 強化学習を用いた手法)

デマンド・リクエストの入力割り当てが不正確である
- DOL: コーディネータがどのプリフェッチャにデマンドリクエストを送信するかを決定する
  - プリフェッチャのカバレッジに基づいてリクエストを順番に送信する
  - P1がP2よりも優れていると仮定される場合、P1にリクエストが送られ、だめならばP2/P3と送られる。
  - 問題点1. 静的な優先順位であるため、最適なプリフェッチャの見極めが難しい
  - 問題点2. DOLはすべてのプリフェッチャに順番にリクエストを渡すため、関係ないプリフェッチャのテーブルにも不要なメタデータが残ってしまう。
- IPCP: ストリーム・ストライド・不規則パタンの3種類のプリフェッチャをハイブリッドに構成する
  - すべてのプリフェッチャにデマンド・リクエストを送り、並列に評価と予測を行う。
  - 問題点: すべてのプリフェッチャがデマンド・リクエストに基づいてテーブルを更新するため、汚染される可能性が高い。
- 強化学習ベースの方法 (Banditなど): 報酬 (例えばコミットされた命令数) を使ってプリフェッチャの度合を動的に制御する。
  - 問題点1. プリフェッチャの適性を精密に判断するためのストレージ・コストが高い
  - 問題点2. リクエストの選別が行われないため、すべてのプリフェッチャが平等に学習され、テーブルが汚染される可能性が高い。
プリフェッチャの選択基準が粗い

目標

メモリアクセス命令 (PC)に対して、最も適切なプリフェッチャを細粒度に識別できるようにする。
識別されたプリフェッチャにのみデマンドリクエストを渡すことにより、テーブルの競合や汚染を最小限に抑える。

設計概要

Alectoの設計のポイントは、デマンド・リクエストをどのプリフェッチャに割り当てるかというところである。

重要な観察として、 同じPCから発行されるデマンド・リクエストは、一貫したアクセスパタンを示す ということである。つまり、Alectoは各プリフェッチャが各PCに対してどれだけ有効に動作したかという実績情報を記録し(これをプリフェッチ精度と呼ぶ)、プリフェッチャの選択判断に利用するということである。

図4にAlectoの基本構成を示す。基本的には、3つのハードウェア構成要素からなる：

割り当てテーブル (Allocation Table)
- メモリアクセス命令毎に、各プリフェッチャがそのPCに対してどの程度有効化を示す状態を記録する。
サンプルテーブル (Sample Table)
- 実行時の情報(例えば、どのプリフェッチャが命中したか)を収集し、割り当てテーブルを更新するための材料とする。
サンドボックステーブル (Sandbox Table)
- 最近発行されたプリフェッチ・リクエストの情報を記録する。このテーブルは2つの役割を持っている。
  - 有効なプリフェッチかどうかを判定するための参照情報の収集
  - 重複したプリフェッチ・リクエストを検出・除去するプリフェッチ・フィルタとしての機能

動作の流れ

デマンド・リクエストが発行されると、そのPCとアドレス情報が割り当てテーブルおよびサンドボックステーブルに送られる (図の①と④)
割り当てテーブルはPCと記録された状態に基づいて、リクエストを受け取るべきプリフェッチャを識別する (図の②)
選ばれたプリフェッチャのみがリクエストを受け取り、プリフェッチ処理を行う。
- これにより生成されたプリフェッチリクエストは、サンドボックステーブルとサンプルテーブルに記録される (図の③)
サンドボックステーブルは、過去のプリフェッチが有効だったかどうかを判定し、その情報をサンプルテーブルに送る (図の⑤)
サンプルテーブルは、プリフェッチの精度をPC単位で集計し、それを割り当てテーブルに反映する
プリフェッチャからのリクエストが再びサンドボックステーブルに送られ、重複していないリクエストのみが下位キャッシュに送られる

割り当てテーブルの役目

メモリアクセス命令(PC)単位に、各プリフェッチャがそのアクセスを処理する適正を表す状態(State)を保持する。これはひとえに、各プリフェッチャが過去にどれだけ高精度にそのPCを処理できたかということを示している。 Alectoは、すべてのプリフェッチャに対して以下の状態を定義している。

UI (Un-Identified)状態
- プリフェッチャの適性がまだ未判定であることを示し、この状態の場合はプリフェッチャの割り当ては慎重に行われ、プリフェッチのdegreeも保守的(例えば2件に抑える、など)である。
IA (Identified and Aggressive)状態
- プリフェッチャが高い適性を示していることを表しており、特定のプリフェッチャに積極的なリクエストを割り当て、プリフェッチのdegreeも大きくする。
- 0~Mまでのサブステートを持ち、数値が大きいほどプリフェッチのdegreeは大きくなる。
IB (Identified and Blocked)状態
- プリフェッチャが当該PCの処理に不適であると判断された場合に設定される。この乗田いでは、プリフェッチャのリクエストが停止される。
- -N~0までのサブステートを持ち、値が小さいほどブロック時間が長いことを示す。

状態遷移のために、以下の2つのしきい値が利用される。

PB (Proficiency Boundary): これを超えた場合、そのプリフェッチャは有効とみなされる。
DB (Deficiency Boundary): これを下回った場合、そのプリフェッチャは不適とみなされる。

状態遷移は以下の手順で行われる。

UI → IA_0 ①
- あるプリフェッチャの精度がPBを超えた場合、そのプリフェッチャはIA(0)状態へ昇格する
- 複数のプリフェッチャが昇格候補の場合、他のプリフェッチャを優先し時間的プリフェッチャをIBに設定する場合がある
UI → IB_0 ①
- PB を超えられなかったプリフェッチャはIB_0に降格される。
IA_0 → UI ②
- IA_0 状態にあるプリフェッチャの精度がPBを下回った場合、UIに戻される
- すべてのプリフェッチャがIA状態を失った場合、IB_0にあるプリフェッチャの一部をUIに戻し、再評価を行う
UI → IB_-N ③
- プリフェッチャの精度が DB を下回った場合、そのプリフェッチャは無駄なプリフェッチを大量に生成していると見なされ、IB_-N に降格される
- この状態では Nエポックの間ブロックされ、徐々に IB_n → IB_n+1 と段階的に戻り、IA状態が空の場合にのみ UIに再昇格される
IA_m → IA_m+1 IA_m 状態にあるプリフェッチャの精度がPBをさらに超えた場合、IA_m+1 に昇格してプリフェッチ度合いが強化される。
IA_m → IA_m-1 逆に精度が低下した場合は IA_m-1に降格し、プリフェッチ度合いを下げる。