前回の続き：

msyksphinz.hatenablog.com

UFTQとUDPのポイント

上のジレンマ(timeliness↔汚染、しかもoff-pathは一概に捨てられない)を崩すために、UDP論文は2つの解決方法を提案している。

UFTQ：観測に基づきFTQ深さ(runahead距離)を動的に調整する

• 「どれだけ先読みするか」を固定値にせず、timelinessとutilityを観測してFTQ深さを伸縮する。
• AUR(平均utility)とATR(平均timeliness) をランタイムに計測し、それロの目標を満たすようにFTQの長さを増減する。
  • AUR(Average Utility Ratio): Prefetchが最終的に役に立ったかをカウントする。命令キャッシュのラインごとにprefetch bitを持ち、プリフェッチにより格納されたこと、実際にデマンドで消費されたことを記録する。
  • ATR(Average Timeliness Ratio): Timelyだと、プリフェッチした命令が命令キャッシュでヒットしたことを示し、Untimelyだと、PrefetchがFill Buffer中に存在しているときにヒットしたことを示す。Untimelyだと、プリフェッチがデマンドアクセスに対してお行けていないことを示す。
• 論文内では、上記の統計情報を扱う方法として3種類の方法を試行した。
  • UFTQ-AUR (utulityで深さを調整する)
    • AURを満たすqueue depthを見つける
  • UFTQ-ATR (timelinessで深さを調整する)
    • ATRを満たす queue depthを見つける
  • UFTQ-ATR (複合型、最終提案型)
    • 初期FTQサイズは32とし、まず utility測定で AUR を満たす深さを見つけ、それを QDAUR と呼ぶ。
    • 次にATRを満たすまで深さを増減し、その深さをQDATRと呼ぶ。
    • 最後にQDAURとQDATRから最終FTQの長さを回帰式で求める。
• 必要なハードウェアは、
  • AUR/ATRを計算するための 10-bitカウンタ×4
  • 比率を保持する 32-bit固定小数レジスタ×2
  • FTQサイズを増減する簡単な状態機械(state machine)