最近はプリフェッチャの論文を読み漁っている。
https://ieeexplore.ieee.org/document/4147648
FDP (Feedback Directed Prefetching) のベースとなるアイデア
プリフェッチ精度の情報収集:2つのカウンタを用意する
preftotal
: メモリに送られたプリフェッチ数。ハードウェア・プリフェッチがメモリに対して送出されると、インクリメントされる。used-total
: 有用なプリフェッチ数。プリフェッチされたキャッシュブロックはプリフェッチ・ビットが設定されており、プリフェッチ・ビット=1のキャッシュブロックを要求した場合はused-totalがインクリメントされ、当該プリフェッチ・ビットがクリアされる。
プリフェッチ精度は、 で計算される。
プリフェッチ遅延の情報収集:MSHRにプリフェッチ・ビットを追加する。
MSHRでリクエスト途中にオンデマンド要求が発生した場合、これはプリフェッチのタイミングが遅いと判断される。従って、late-totalカウンタをインクリメントする。
プリフェッチ遅延は、 で計算される。
キャッシュ汚染を測定するためには、プリフェッチによって追い出されたL2キャッシュブロックに関する情報を集めておく必要があるが、これをハードウェアで実現するのはかなり負担が大きい。
そこで、ブルームフィルタを用いたデマンドミスの数を近似することを考える。図4に示すように、キャッシュブロックの上位アドレスと下位アドレスをXORする形でハッシュ関数を生成する。
デマンド・ミスにより取り込まれたキャッシュ・ブロックが、プリフェッチにより追い出された場合、Pollution Filterを当該ハッシュ関数を使用して1に設定する。
次にデマンド・ミスが発生した場合、Pollution Filterを使って当該キャッシュが追い出されたかどうかをチェックし、追い出されている場合はpollution-totalビットをインクリメントする。
また、プロセッサによって生成されたデマンド・ミスの総数をdemand-totalによって記録する。最終的に、 によってキャッシュ汚染の比率を計算することができる。
ハードウェアカウンタのアップデートポリシ:
上記のカウンタについて、以下のようにしてカウンタの値を更新する:
eviction-countというハードウェア・カウンタによって、L2キャッシュから退避されたブロック数を追跡し、その値が を超えるとインターバルが終了し値の更新が発生する。
は8192を静的に設定しているが、これはL2キャッシュブロック数の半分である。
上記のメトリクスに応じて、プリフェッチャにおける以下の2つ動作を調整する。
- プリフェッチ・メカニズムのアグレッシブ性
- プリフェッチされたブロックを挿入するL2キャッシュのLRUスタックの位置
プリフェッチャのアグレッシブ性を調整するための方法:
ベースラインのストリーム・プリフェッチャには、Very ConservativeからVery Aggressiveまで5つの構成を用意している。デフォルトではConfiguration Counterの値を3に設定している。
- 精度:2つの閾値を使って、High/Middle/Lowに分類される
- 遅延:1つの閾値を使って分類される。
- 汚染:1つの閾値を使って分類される。
プリフェッチのキャッシュブロック挿入ポリシの変更:
インターバル毎にプリフェッチャによるキャッシュ汚染度を測定し、2つの閾値を用いて汚染度を3つに分類する:
- 低汚染の場合:キャッシュブロックはLRUスタックの中間に挿入される
- 中汚染の場合:キャッシュブロックのLRU-4の位置(floor(n/4))に挿入される
- 高汚染の場合:キャッシュブロックのLRUの位置に挿入される