FPGA開発日記

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

Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers (2. FDPのアルゴリズム

最近はプリフェッチャの論文を読み漁っている。

https://ieeexplore.ieee.org/document/4147648


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つ動作を調整する。

  • プリフェッチ・メカニズムのアグレッシブ性
  • プリフェッチされたブロックを挿入する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の位置に挿入される