Merging Similar Patterns for Hardware Prefetching を読む (2. ハードウェアの構成)

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

概要を大きくまとめる。

それでは、実際のPMP(Pattern Merge Prefetcher)の実装に移る。本プリフェッチメカニズムはトレーニングとプリフェッチのプロセスが2つ平行に動作する。

学習フェーズ：
- パタン・マージ戦略を導入することにより、ストレージの必要量を大幅に削減することを考える。
- マージされたパタンから高精度なプリフェッチターゲットを生成することを考える。
プリフェッチ・フェーズ
- デュアルパタンテーブルを提案することによって、プリフェッチ精度をさらに向上させる。

パタンのマージ戦略

まず、どのようにパタンをマージすればよいかを考える。前節ではAND・ORなどの方式を考えたが、結局これが良くない。

本提案手法では、ビット・ベクトル内の各オフセットの出現回数をカウントすることによってビット・ベクトル・パタンをマージすることを考える。このために、各要素がオフセットへのアクセス回数を記録するために「カウンタ・ベクトル」を用意する必要がある。

マージされるビットベクトルパタンに対応するオフセットがアクセスされると、ベクトル内のオフセットのカウンタが並列に増加する。

図6(a)は、メモリ領域Pでアクセス・シーケンスP+2, P+1, P+4が発生した場合のビット・ベクトル $(0,1,1,0,1,0,0)$ をカウンタ・ベクトル $(3,0,3,0,3,0,0)$ にマージする例を示している。

トリガ・オフセットが2であるため、まず最初に左に2要素循環シフトさせる。

$(0,1,1,0,1,0,0)$ → 2要素の循環左シフト → $(1,0,1,0,0,0,1)$ (アンカー付きビットベクトル)
アンカー付きビットベクトルに基づき、カウンタ・ベクトルを増加させる。カウンタ・ベクトルは最終的に、 $(4, 0, 4, 0, 3, 0, 1)$ となる。

時間カウンタが飽和すると、カウンタ・ベクトルのすべての要素を半分にする。古いレコードの影響を軽減しつつも維持することが目的である。上記のカウンタ・ベクトルは、時間カウンタ3である場合、 $(4, 0, 4, 0, 3, 0, 1)$ から $(2, 0, 2, 0, 1, 0, 0, 0)$ に半減される。

この戦略が効果的な理由hあ2つある：

マージされるパタンは類似性が高いため、マージ後も共通の特徴が残る。
AND/OR演算などと異なり、より柔軟なマージを可能とする。

プリフェッチ・パタンの抽出

トリガ・アクセスが来たときに、パタンをトリガすることが目的である。カウンタ・ベクトル方式のトリガ・パタンをどのようにしてプリフェッチ・パタンに変換するかについて考える。

本提案方式において、トリガされたカウンタ・ベクトルの対応する要素をお別に調べることにより、各オフセットにおけるターゲット・キャッシュ・レベルを個別に選択することができる。

アクセス番号ベースの抽出(Access-Number-based Extraction : ANE)：トリガされたカウンタ・ベクトルの対応する要素がある閾値以上であれば、プリフェッチターゲットが生成される。
- この方式の明らかな欠点は、どのターゲット・オフセットもプリフェッチの閾値に達するために必然的なコールド・スタートとなる。
- 閾値がTである場合、オフセットはT回訪れるまでプリフェッチされず、多くのプリフェッチチャンスを失う。
アクセス率ベースの抽出 (Access-Rate-based Extraction : ARE)：トリガされたカウンタ・ベクトルの各要素について、すべてのカウンタの合計に対する比率を、プリフェッチ・ターゲットを生成するための閾値として使用する。
- 例えば、L1Dプリフェッチのしきい値1/4である場合、(?, 2/3, 0, 1/3)となる。トリガ・オフセットは除去されており、比率は無視される。したがって、プリフェッチパタンは $(0, L1, 0, L1)$ となる。
- 半減しても再トレーニングを回避できるため、プリフェッチの処理は継続させることができる。
- しかし、本方式は1回の予測におけるプリフェッチの最大数（プリフェッチの深さ）を制限している。例えば同じ値を持つ64個のカウンタを含むトリガ・ベクトルの場合、しきい値は1/63よりも小さくなければ、どのアドレスもプリフェッチすることができない。
アクセス頻度ベースの抽出 (Access Frequency-based Extraction : AFE) ：アクセス頻度はアクセス比率とは異なり、オフセットがある期間に何回発生するかを示している。オフセットのアクセス頻度をプリフェッチのしきい値と比較することにより、プリフェッチ・ターゲットを生成する。
- L1Dプリフェッチのしきい値が1/4の場合、カウンタ・ベクトル (4, 2, 0, 1)の各カウンタの頻度は、(?, 2/4, 0, 1/4) となるため、カウンタ・ベクトルを(0, L1, 0, L1)としてプリフェッチターゲットとする。
- 半減のメカニズムは、オフセットの頻度に影響を与えない。
- AFEにはコールドスタートの問題がない。もしオフセットが最後のT個のパタンで毎回出現するならば、その頻度は訓練開始時から100%となり、どのしきい値も超えることができる。
このような利点におり、デフォルトのプリフェッチ抽出スキームとしてAFEを導入する。
- AFEを使用するデフォルト構成では、L1Dのデータをプリフェッチするしきい値$T{l1d}$は50%であり、L2Cをプリフェッチするしきい値$T{l2c}$は15%としている。つまり、信頼度がTl2c以上でTl1d以下の場合は、L2Cにプリフェッチが行われる。

図6(c)のように、新しいプリフェッチ・パタンがプリフェッチ・バッファ(PB)に格納され、トリガ・アクセスの領域アドレスによってインデックスされる。

複数の特徴量に基づく予測

観察3では、トリガ・アクセスとしてPCの特徴値もプリフェッチ・ターゲットの予測に使用できることに気が付く。複数の特徴量を用いる場合、つまりトリガ・オフセットとPCによって分類されるメモリ・アクセス・パタンは、セット内のパタンに大きな分岐を生じされる。

そこで、トリガ・オフセットとPCによってそれぞれインデックスされたパタンをマージするために、デュアル・パタン・テーブルが使用される。

カウンタ・ベクトルは、同じ特徴量でインデックスされたすべてのパタンを収集するため、ダイレクトマップ・テーブルといて格納される。

オフセットパタンテーブル(OPT)：トリガ・オフセットでインデックスされたパタン・テーブル
PCパタンテーブル(PPT)：PCでインデックスされたパタン・テーブル

トレーニング時には、2つのパタン・テーブルが同時に更新される。プリフェッチ時には、トリガ・アクセスが来たときに2つのテーブルによってプリフェッチパタン候補が独立に予測される。この予測をアービトレーションし、OPTが与えるターゲットに含まれない、PPTのターゲットは破棄したほうが良い。

同じターゲットオフセットが、両方のパタン・テーブルがL1Dにデータをプリフェッチすると予測した場合、L1Dに発行される。
同じターゲット・オフセットが両方のテーブルによって予測され、一方のテーブルがL2Cにデータをプリフェッチすると予測した場合、L2Cにプリフェッチされる。
OPTからの予測がない場合、プリフェッチは発行されない。

ハードウェア・オーバヘッド

PMPのハードウェア・オーバヘッドの構成を示す。

OPTは64エントリ、PPTは32エントリである。

Filter Table : 64エントリを含んでおり、各エントリは、リージョンのタグ・ハッシュされたPC、トリガ・オフセット値、LRUを含んでおり、合計(33+5+6+3) = 47bitである。これが64エントリで、3008bit = 376Bytesである。
Accumulation Table : 32エントリを含んでおり、各エントリは、リージョンのタグ、ハッシュ化されたPC、トリガ・オフセット、ビット・ベクトル、LRUを含んでおり、合計 (35+5+6+64+4) = 114bitである。これが32エントリ含まれており、3648bit = 456Bytesである。
Offset Pattern Table : 64エントリを含んでおり、各エントリはカウンタを含んでいる。5b x 64 = 320-bitである。これが64エントリ含まれており、20,480-bit = 2560Byteである。
PC Pattern Table : 32エントリを含んでおり、各エントリはカウンタを含んでいる。160-bitが32エントリ含まれているため、5,120-bit = 640Bytesである。
Prefetch Buffer : 332Bytes である。

よって、合計は4.3kBであり、Bingo Prefetcherよりも30倍小さい。