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

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

高性能プロセッサは、メインメモリのレイテンシの影響を軽減するためにハードウェアデータのプリフェッチを使用する。プリフェッチは多くのプログラムで性能を大幅に向上させるが、一部のプログラムでは性能を大幅に低下させることがある。また、プリフェッチによりメモリ帯域の要件が大幅に増加することがある。

本論文では、プリフェッチの性能と帯域へのネガティブな影響を軽減するために、動的フィードバックを取り入れたプリフェッチャの設計メカニズムを提案している。

プリフェッチャの精度、タイムリネス、キャッシュの汚染を推定
データプリフェッチャの積極性を動的に調整する

また、実行時にプリフェッチャによるキャッシュの汚染を追跡する新しい方法や、キャッシュ内のLRUスタックにプリフェッチされたブロックを挿入する場所を動的に決定するメカニズムも紹介する。

従来のストリームベースのデータプリフェッチャ構成に比べて、SPEC CPU2000スイートの17のメモリ集中型ベンチマークで： - 平均性能が6.5%向上 - メモリ帯域が18.7% 削減

従来のストリームベースのデータプリフェッチャ構成と比較して： - 13.6%の性能が高い

Feedback Directed Prefetcherが、プリフェッチによって一部のベンチマークで生じる大きな性能へのネガティブな影響を排除し、ストリームベースのプリフェッチャ、グローバルヒストリバッファベースのデルタ相関プリフェッチャ、PCベースのストライドプリフェッチャに適用可能であることを示している。

Introduction

データ・プリフェッチは、メモリ・アクセス・インテンシブなベンチマークの性能を大きく上げる効果がある一方で、過度なプリフェッチにより逆に性能が落ちてしまう可能性がある。大きく以下の2つの要因がある：

プリフェッチがメモリ帯域幅を増加させる
キャッシュを汚染し、余分なキャッシュミスを発生させる

図1. は、SPEC 2000ベンチマークスイートにプリフェッチの種類を変えながら性能を測定した結果で、アグレッシブなプリフェッチャは全体的な性能を向上させる一方で、ammpやappluといったベンチマークはアグレッシブなプリフェッチによって逆に性能が低下してしまっている。

本論文の目的は、アグレッシブなプリフェッチを許容しつつ、性能とバンド幅への悪影響を低減させることである。このためには、

プリフェッチャのアグレッシブさを動的に調整する
プリフェッチされたデータが挿入されるプリフェッチャ内の位置を動的に調整する

このために、以下の3つのメトリクスをハードウェアによって測定する：

精度
適時性
キャッシュ汚染

これらの測定により、ハードウェア・プリフェッチャの積極性を動的に減少・増加させる。また、キャッシュ汚染を監視することによって提案するメカニズムは、プリフェッチャのキャッシュのLRUスタックのどこにプリフェッチされたブロックを挿入するかを決定する。

これらの機構は、2.54KBのハードウェアコストによって、ストリームプリフェッチャの構成と同等の性能を示すことができる。

従来のストリーム・プリフェッチャについて

従来のストリームプリフェッチャは、以下のようなステートで動作する：

Invalid : トラッキング・エントリはまだ何も割り当てられていない状態
Allocated : デマンドミスにより、トラッキングエントリが割り当てられた状態
Training : プリフェッチャにより、最初のミスの場所から同一範囲内の次のミスの場所までの方向を測定し、ストリームの方向(昇順・降順)の学習を行う。ストリームの次のアクセスが同一方向に関し範囲内で発生した場合、Montiro and Request状態に移行する
Monitor and Request : 開始ポインタ(アドレスA)から終了ポインタ(アドレスP)までのメモリ領域へのアクセスを監視し、そこへのアクセスがあればプリフェッチを行う。
- 開始ポインタから終了ポインタまでの距離はプリフェッチ距離と呼ばれる。
- プリフェッチャはキャッシュブロック[P+1,…,P+N]を要求し、Nはプリフェッチ深度と呼ばれる。

この従来のプリフェッチャにおける、プリフェッチ距離とプリフェッチ深度は固定であり、これをフィードバック機構により動的に調整することでプリフェッチのアグレッシブ性を調整する。

プリフェッチャの有効性の指標

このセクションでは、メトリクスを定義し、従来のプリフェッチャが提供する性能とメトリクスの関係を説明する。

4つの構成を評価する：

プリフェッチなし
Very Conservativeプリフェッチ（distance=4、degree=1）
Middle-of-the-Roadプリフェッチ（distance=16、degree=2）
Very Aggressiveプリフェッチ（distance=64、degree=4）

プリフェッチ精度は、以下の式によって定義される：

$\text{Prefetch Accuracy} = \dfrac{\text{Number of Useful Prefetches}}{\text{Number of Prefetches Sent To Memory}}$

つまり、プリフェッチされたブロックのうち、L2キャッシュ内に常駐している間に要求されたブロックがどれくらい存在しているかというのを示している。

この観点に基づき各ベンチマークでプリフェッチ精度を測ると図2のようになり、これとIPCを比較すると、プリフェッチのアグレッシブ性が向上するにつれてIPCが下がるベンチマークは、プリフェッチ精度も低いことが分かる。

プリフェッチ遅延は、以下のように定義される：

$\text{Prefetch Lateness} = \dfrac{\text{Number of Late Prefetches}}{\text{Number of Useful Prefetches}}$

この指標に基づいて、各ベンチマークにおけるプリフェッチ遅延を測定したものが図3になる。mcfではプリフェッチ精度が100%に近いにも関わらずプリフェッチが性能向上に大きな影響をもたらさないのは、プリフェッチ遅延による影響である。

vortexでは、非常にアグレッシブなプリフェッチャを使用することによってプリフェッチ遅延は大きく削減することができる。

プリフェッチャ生成キャッシュ汚染は、L2キャッシュ内のプリフェッチデータによって引き起こされる妨害の尺度である。次のように定義される：

$\text{Prefetcher Generated Cache Pollution} = \dfrac{\text{Number of Demand Misses Caused by the Prefecher}}{\text{Number of Demand Misses}}$

デマンドミスにおいて、プリフェッチャが存在しなければ発生しなかった場合、プリフェッチャによって引き起こされたと定義される。

プリフェッチャが生成するキャッシュ汚染が高い場合、キャッシュ内の有用なデータがプリフェッチされたデータによって退避される可能性があるため、プロセッサの性能が低下する可能性がある。さらに、キャッシュ汚染度が高いと、メインメモリから退避されたデータを再フェッチする必要があるため、メモリ帯域幅の消費も大きくなる可能性がある。