FDP (Feedback Directed Prefetching) のベースとなるアイデア

プリフェッチ精度の情報収集：2つのカウンタを用意する

preftotal : メモリに送られたプリフェッチ数。ハードウェア・プリフェッチがメモリに対して送出されると、インクリメントされる。
used-total : 有用なプリフェッチ数。プリフェッチされたキャッシュブロックはプリフェッチ・ビットが設定されており、プリフェッチ・ビット=1のキャッシュブロックを要求した場合はused-totalがインクリメントされ、当該プリフェッチ・ビットがクリアされる。

プリフェッチ精度は、 $\text{used_total} / \text{preftotal}$ で計算される。

プリフェッチ遅延の情報収集：MSHRにプリフェッチ・ビットを追加する。

MSHRでリクエスト途中にオンデマンド要求が発生した場合、これはプリフェッチのタイミングが遅いと判断される。従って、late-totalカウンタをインクリメントする。

プリフェッチ遅延は、 $\text{late_total} / \text{used-total}$ で計算される。

キャッシュ汚染を測定するためには、プリフェッチによって追い出されたL2キャッシュブロックに関する情報を集めておく必要があるが、これをハードウェアで実現するのはかなり負担が大きい。

そこで、ブルームフィルタを用いたデマンドミスの数を近似することを考える。図4に示すように、キャッシュブロックの上位アドレスと下位アドレスをXORする形でハッシュ関数を生成する。

デマンド・ミスにより取り込まれたキャッシュ・ブロックが、プリフェッチにより追い出された場合、Pollution Filterを当該ハッシュ関数を使用して1に設定する。

次にデマンド・ミスが発生した場合、Pollution Filterを使って当該キャッシュが追い出されたかどうかをチェックし、追い出されている場合はpollution-totalビットをインクリメントする。

また、プロセッサによって生成されたデマンド・ミスの総数をdemand-totalによって記録する。最終的に、 $\text{pollution_total} / \text{demand_total}$ によってキャッシュ汚染の比率を計算することができる。

ハードウェアカウンタのアップデートポリシ：

上記のカウンタについて、以下のようにしてカウンタの値を更新する：

$\text{CounterValue} = \dfrac{1}{2} \text{CounterValueAtTheBeginningOfTheInterval} + \dfrac{1}{2} \text{CounterValueDuringInterval}$

eviction-countというハードウェア・カウンタによって、L2キャッシュから退避されたブロック数を追跡し、その値が $\text{T}_\text{interval}$ を超えるとインターバルが終了し値の更新が発生する。

$\text{T}_\text{interval}$ は8192を静的に設定しているが、これはL2キャッシュブロック数の半分である。

上記のメトリクスに応じて、プリフェッチャにおける以下の2つ動作を調整する。

プリフェッチャのアグレッシブ性を調整するための方法：

ベースラインのストリーム・プリフェッチャには、Very ConservativeからVery Aggressiveまで5つの構成を用意している。デフォルトではConfiguration Counterの値を3に設定している。

プリフェッチのキャッシュブロック挿入ポリシの変更：

インターバル毎にプリフェッチャによるキャッシュ汚染度を測定し、2つの閾値を用いて汚染度を3つに分類する：