FPGA開発日記

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

Merging Similar Patterns for Hardware Prefetching を読む (1. 概要)

論文

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

概要を大きくまとめる。

  • 用語確認：
    • リージョン:アドレス空間上の領域。この論文ではページ(4KB)と同じサイズに設定。
    • ジェネレーション:一定時間に、あるリージョンに対してアクセスされたラインの集合

メモリアクセスパタンの特徴を分析するため、SMS(Spatial Memory Streaming)のフレームワークを使用して、SPEC CPUのトレースからパタンを分析している。

  • FT (Filter Table: 最初にテーブルをフィルタリングするためのテーブル)は4x16のセットアソシアティブ
    • リージョン・アドレスでアクセス、PCとオフセットを記録する。
  • AT (Accumulated Table: ビットパタンを格納するためのテーブル)
    • リージョン・アドレスでアクセス、パタンを記録する。 パタン長は64、64-len x 64B = 4096Bでページと一致するサイズにしている。
図は本論文より引用

観測1. 高い頻度で発生するメモリアクセスパターンはごく少数である。

１リージョンのビットベクタは64bitから構成されており、ステータス空間は2^{64}で巨大となる。しかし、それほど多くのパタンが発生することはない。 125個のトレースの中で - [tex: 6.5\times 106] 個のパタンが出現。 - 合計 [tex: 1.1\times 108] 回出現 - 全体のパタンのうち75.6%は一回しか出現しない。 - 出現頻度の高い上位10%が全体の33.1%を占める。 - 上位100個と上位1000個のパタンは、全体の57.4%および73.8%を占める。

このため、頻度の高いパタンだけを保持する小さなエントリの軽量プリフェッチャを設計することは可能である。

観察2：メモリ・アクセス・パタンを細かい特徴でインデックス化すると、データの冗長性がひどくなる可能性がある

インデックス付きのパタンを保持する機能は、メモリ・アクセス・パタンがそのストレージ内で一意であることを保証できないことが多い。 以下の数値を定義する。

  • ある特徴量に関連する異なるパタンの数をパタン衝突率(Pattern Conflict Rate: PCR)
  • あるパタンに関連する特徴量の数をパタン重複率(Pattern Duplicate Rate: PDR)

このメトリクスに基づいて、インデックスの種類毎に分析を行ってみる（表1)。

図は本論文より引用
  • PC+Address(80bit)に基づいてインデックスすると、PCRは1.7となり、高い解像度でパタンを識別できる。
    • 一方、PDR=608.7と高く、同じようなパタンを多くの場所に保存し冗長性が高い。
  • Address(48bit)を使う場合、PDRは=556.3であるため、多くの同じようなパタンが異なるインデックスで共有されていることがわかる。
    • あまりにも冗長なので、アドレスの上位ビットをカットし、異なる領域の同じパタンを同じ特徴量にインデックスできるようにしている。
  • PC+Trigger Offest(38bit)を使う場合、PCR=269.0と高く、同じインデックスに多数の種類のパタンが集中する。
    • PDR=6.3と小さく、同じパタンが異なるインデックスで共有されることは少なくテーブルの効率が良い。
    • セットアソシアティブキャッシュでは、PCRが高いとパタンの入れ替わりが激しく、プリフェッチの精度が低下してしまう。

観察3：同じトリガーオフセットを持つパターンは非常に類似している

特徴量やパタンをマージするということを考える。あるパタンに関連する特徴値を同じインデックスにマージできれば、冗長性を排除できる。 しかし、一度マージしたものを変化に応じて再度割り当てなおすのは難しい。

類似したパタンをクラスタ化することを考える。効率的にパタンをマージしたいと考える。 パタンのマージの難易度を下げるために、似たようなパタンのアクセスパタンをAND演算でマージした場合でも、全体的な情報損失は小さいことに着目する。

ICDDという指標を使用する。ICDDが小さいほど、クラスタ内のパタンの類似性が高いことを示す。 Trigger Offset / Hashed PC / PC + Trigger Offset / Hashed Address / Hashed PC + Address で6ビット(64クラスタ）化を行った時の平均的なICCD値を図4に示す。 Trigger Offsetを使った場合がICCD値が最も小さく、Trigger Offsetによりパタンをマージする方法が最も効率的だと考えることができる。

図は本論文より引用

例として、いくつかの典型的なトレースにおけるパタンをヒートマップとして描く。 x軸はアクセスしたオフセットを示し、y軸はクラスタのインデックスを示す。値が濃いほど、多くのパタンがそのオフセットのビットを含んでいることを示す。 図5(a)においては、Trigger Offsetの周辺のオフセットに対してアクセスする傾向があるといえる。また、大きなTrigger Offestがある場合は、プログラムは逆方向のアクセスを行う傾向がある。 図5(b)は、Astarのトレースを示しており、Astarはリージョン内において一定のストライド・パタンを持っていることを示している。

図は本論文より引用

このような傾向が現れる理由としては、Trigger Offsetが、プログラムのメモリアクセス動作に関連する特徴を含んでいると考えられる。 MCFの場合は以下のようなループによって構成される：

// ファイル: pflowup.c 
// メソッド： MCF_primal_update_flow
// データは大きな配列に格納される。
for(;iplus!=w;iplus=iplus->pred)
{...}
for(;jplus!=w;jplus=jplus->pred)
{...}

このメモリアクセスはPCによって識別することはできず、PCを使ってのクラスタ化は難しい。 また、ループのPCが2つあるため、それぞれのループが同じアクセスをしていたとしても、異なるPCであるため異なるクラスタに割り当てられてしまう。