FPGA開発日記

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

Fetch Directed Prefetchingの論文を読む

色々分け合ってプリフェッチの論文を読んでいる。

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

arxiv.org

Fetch Directed Instruction Prefetchingは、命令のプリフェッチのための機能。

  • FDP : Fetch Directed Prefetching
  • FDIP : Fetch Directed Instruction Prefetching

命令プリフェッチを駆動するために、分岐予測器を使用するという方法。

分岐予測器を使用しないプリフェッチの場合：

  • Next Line Prefetching
  • Streaming Buffer

フェッチした命令およびアドレスを使用して次のプリフェッチアドレスを指定するということになる。これに対して、FDPは命令フェッチがストールしても、分岐予測の情報をもとにプリフェッチを出し続けることができるので、プリフェッチの性能を向上させることができる。

さらに本論文では、L2のバンド幅を節約するために、

  • 命令キャッシュから追い出されたフェッチブロックをマーキングすることで、正確にプリフェッチできるようにする
  • プリフェッチ要求をフィルタリングするためにキャッシュのあいているポートを使用する

という提案手法がなされている。

Fetch Target Queue (FTQ)について

分岐予測器は、予測したアドレスをFetch Target Queue (FTQ)に格納する。

これにより、命令キャッシュがミスを発生してストールが発生したとしても、プリフェッチのリクエストを生成し続けることができる。

Fetch Target Buffer (FTB)について

Branch Target Buffer (BTB)と似ているが、より大きなフェッチブロックを予測することができるもの。

Fetch Directed Prefetchingのアーキテクチャ

図1がFDPのアーキテクチャを示している。

  • 分岐予測器と命令キャッシュを分離
  • 分岐予測器は、FTQに命令キャッシュにフェッチしてほしいブロックのアドレスを格納する。
    • FTQは最大で3つのキャッシュ・フェッチ・ブロック・エントリを含むことができる
    • 1つの予測からのフェッチ・ブロックは、3つのキャッシュ・ブロックにまたがる可能性がある
    • フェッチ・ブロックは、以下を含む。
      • 有効ビット
      • プリフェッチ候補ビット：キャッシュ・ブロックがプリフェッチの候補であることを示す
      • エンキューされたかを示すビット：キャッシュ・ブロックがすでにPIQないでプリフェッチされるようにエンキューされていることを示す
      • キャッシュ・ブロック・アドレス
  • FTQのエントリからFIFOで取り出され、PIQに空きがあるときに挿入される。
    • PIQ (Prefetch Instruction Queue)

プリフェッチ・バッファの機能について

  • L2から取得したキャッシュブロックは、プリフェッチ・バッファに格納される。
    • Streaming Bufferに似ているが、プリフェッチアドレスをFTQから取得するところが異なる。
    • キャッシュ・ブロックがPIQに挿入されると、プリフェッチ・バッファも確保される。
    • プリフェッチ・バッファが満杯の場合、これ以上プリフェッチは発生しない。
  • 命令キャッシュのフェッチが行われる際、プリフェッチ・バッファも同時に検索される
    • Oldest Entryに対してヒットすると、そのエントリはエントリから削除され、命令キャッシュに挿入される
  • 分岐予測が発生すると、プリフェッチ・バッファはフラッシュされ、FTQも同様にフラッシュされる。
    • 別のアイデアとしては、プリフェッチ・バッファのエントリに置き換え可能ビットを追加し、分岐予測ミスの際はそのビットを立てる
    • 分岐ミスが発生したとしても、短い順方向分岐の際に誤ったプリフェッチが再利用できるのではないかという考察
    • その分、回路が複雑になる可能性はある。

プリフェッチのやりすぎ危険：フィルタリング

フェッチ・ブロック数のトレードオフ

  • FTQエントリが多ければ多いと、ミス予測したパスをプリフェッチする可能性が高い。
  • 無駄なプリフェッチになる可能性がある

FTQ内のフェッチ・ブロック・エントリをフィルタリングすることを考える

  • 実行サイクルのうち30％で16個以上のフェッチ・ブロックを含んでいる
  • 実行サイクルのうち60%で4個以上のフェッチ・ブロックを含んでいる

結論：

  • FTQエントリの2番目のエントリからプリフェッチを開始する
    • 理由：命令キャッシュからフェッチされる間際にプリフェッチとして開始しても、ほとんどメリットがない
  • FTQエントリを32本用意した場合、10エントリでプリフェッチを停止することで、良好なパフォーマンスを実現できる
    • FTQのかなり遠い部分でプリフェッチをしても、プリフェッチが有用である確率が低下する

キャッシュ・プローブ・フィルタリング (CPF)

キャッシュのアイドル時間を使用して、プリフェッチ要求がキャッシュ内にあるかどうかをチェックする。

キャッシュ・プローブ・エンキューイング (Enqueue CPF)

アイドルキャッシュポートを使用して命令キャッシュをプローブし、命令キャッシュに存在しない場合のみプリフェッチをFTQからPIQに移す。

保守的な手法といえる。

リムーブ・キャッシュ・プローブ・フィルタリング (Remove CPF)

キャッシュ・ポートが空いている場合に限り、キャッシュ・タグをチェックして命令キャッシュに存在しているかをチェックする。

命令キャッシュ内に存在している場合、プリフェッチの候補から外される。

キャッシュ・ポートが空いていない場合は、命令キャッシュをチェックをせずにそのままプリフェッチする。

キャッシュ・ミス・フィルタリング

命令キャッシュでミスする可能性が高いフェッチ・ブロックをプリフェッチすることを考える。

あるキャッシュセットにコンフリクト・ミスが多い場合、そのキャッシュセットにマップされるすべてのブロックをプリフェッチして、フェッチ・バッファに置いておく。

  • キャッシュ・セットに信頼度カウンタを設置し、どのキャッシュセットが最も頻繁にミスするを調査する。
    • 各命令キャッシュ・セットに対して2ビットの飽和カウンタを設置した
      • キャッシュ・ミス発生：セット・カウンタをインクリメント
      • キャッシュ・ヒット：セットカウンタを変更しない
      • 信頼度カウンタは100万サイクル毎にクリアされる

フェッチ・ブロックの退避プリフェッチ

FTBエントリにEvictedビットを追加し、対応する分岐のキャッシュブロックが命令キャッシュから対比された場合にセットする。

Evictedが設定されたエントリは、次のプリフェッチ候補となる。

性能測定結果

図2の測定対象：

  • フィルタリングなし (NoFilt)
  • Remove Cache Probe Filtering (Remove CPF)
  • 2ビットのキャッシュ・ミス・テーブルを使用しながらRemove CPF (Cache Miss + Remove CPF)
  • Cache Probe Enqueueing (Enqueue CPF)
  • プリフェッチをガイドするために退避ビットを使用 (Evict)
  • 退避ビットとEnqueue CPF（EnqCPF＋Evict）
図は論文より引用

FDPだけでも、30％程度性能を向上させることができる。しかし、同様にバスの使用率が大幅に増加する。

これらのバス幅の利用率の増加を、各種フィルタリングの手法によって低減することができている。