Efficiently Prefetching Complex Address Patterns (VLDP)の論文を読む (2. 予測のための各テーブルについて)

ちょっと調べなければならなくなったので、メモ：

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

• Efficiently Prefetching Complex Address Patterns

VDLPのポイントは、上記のようにデルタ・ヒストリ・バッファ(Delta History Buffer: DHB) を元に次のプリフェッチを生成することだ。

VLDPに使用されるテーブルをまとめてみる。

• アクセス履歴を格納するためのテーブル
  • DHB : 各ページでのアクセスを、それぞれのアクセスの差分の情報を使って保存している。各エントリはページ単位での情報を保持している：
    • ページ番号
    • 最後のアクセスのページ内オフセット・アドレス
    • 過去4回のアクセスの差分(デルタ)
    • 最近の予測に使用したDPTのレベル
    • このページテーブルが使用された回数
    • 最近の4回のプリフェッチされたオフセット情報
  • これらの情報を利用して予測がトリガされる(PAE : Prefetch Activation Event)

• 予測するためのテーブル (Prediction Tables)
  • OPT (Offset Prediction Table) : 複数回のパタンが必要なDPTを補うために使用するテーブル。全アクセスで共通のテーブルを使用する。
    • 64エントリのダイレクト・マップ・ページを使用する
    • 最初のページアクセスでOPTを検索し、ヒットかつaccuracyビットが設定されている場合は、プリフェッチ・デルタを使用して次のプリフェッチアドレスを生成する。
    • 同一ページに2回目のアクセスがあった場合、デルタが計算される。
    • 以降で同一ページにおいて同一デルタが検出されれば、accuracyビットが1に設定される。
    • OPTでの観測が、実際のデルタとマッチしなかった場合、accuracyビットが0に戻される。
  • DPT (Delta Prediction Table)
    • DHBの結果に基づいて予測を行うのがDPTの役割となる。DPTはDHBとは違いページ単位での管理ではなく、ページを跨いで共通の表が使用される。
    • 幾つかの長さに基づいて予測を行っており、もっとも優先度が低いのが1つの差分を使用するもの、最も優先度が高いのが3つの差分を使用したものだ。
      • 最大3つまでの差分情報
      • ヒット・ミスを示すAccuracy
      • 最近使用されたわけではないことを示すnMRUカウンタ。
    • 幾つか接続されたDPTのうち、最も長いヒストリのものを最優先として予測をすることで、精度を最大化することができる。