CVPシミュレータを解読したメモ

新年になりました。今年もよろしくお願いします。

Value prediction(値予測)の世界的な大会、Second Championship Value Prediction @ HPCA'21というのが開催されているそうです。

値予測というのは投機的実行の一種で、レジスタに書き込まれる値を予測するものです。 投機的実行の代表的な例として分岐予測がありますが、これは分岐命令のとび先を予測するものです。

どちらも、あくまで予測による投機的実行なので、実際に実行して予測が正しかったことを確認する必要があります。 予測が間違っていた場合、その予測結果を(直接的にでも間接的にでも)使った命令を全てやり直す必要があります。 特に、値予測の場合は分岐予測と違い、「なんでもいいから適当に予測しておく」のではなく「予測しない」という消極的選択肢を選んだ方が性能を高めることが多いです*1

そういうわけで、値予測器の評価では(正答率やカバー率といった単純な指標ではなく、)実際にプログラムが高速に動作するかで評価を行う必要があります。 そのために作られたシミュレータがCVP simulator(https://github.com/eric-rotenberg/CVP)です。

CVPシミュレータの特徴

CVPシミュレータの特徴は、以下の通りです。

  • Qualcomm社が提供するARM64のトレースを読み込んでシミュレーションする
    • ARM64の命令は最大5つ*2のマイクロ命令に分解されてシミュレーションされる
  • (サイクル単位ではなく)命令単位でどのサイクルに何が起こるかをシミュレーションする
  • L1Iキャッシュをミスしない限り命令フェッチに時間がかからないとしている
  • 分岐予測器にTAGE-SC-LとITTAGEを採用している
    • BTBやRASは実装されていません

CVPシミュレータは、その構造上、以下の本質的な問題が存在します。

シミュレーションが正確ではない

サイクル順ではなくて命令順にシミュレーションしているため、(少なくとも)キャッシュの状態が正しくシミュレーションされません。 具体的には、以下のようなパターンが問題になります。

  1. あるロード命令由来のアクセスが、L1Dキャッシュミスを起こした後L2キャッシュでヒットする。
  2. その次の命令が、L1Iキャッシュミスを起こした後L2キャッシュもミス。L3キャッシュのデータをL2キャッシュに挿入する。

このような場合、「L2キャッシュでヒットする」は「L2キャッシュに挿入する」の後に起こるかもしれず、その場合にはL2キャッシュの状態が変化しているので本当にヒットとは限りません。

命令キャッシュミスはそんなに発生しないので問題ないということなのでしょうか。 しかし、配布されているトレースのうち一部のトレースでは23%も命令キャッシュミスが起きるらしい*3ので、「命令キャッシュミスはそんなに発生しない」という仮定は成り立っていないと思います。

とはいえ、サイクル順のシミュレーションをする場合はたくさんのコードを書かないといけないので、シミュレーションが多少不正確になっても問題ないとすれば、適当な妥協点なのかもしれません。

CVPシミュレータのおかしな点

CVPシミュレータの微妙な点(おそらく簡単に修正可能)は以下の通りです。

マイクロ命令への分解がナイーブ

ベースアドレス書き替え付きのロード命令がマイクロ命令に分解される場合、「ベースアドレス書き替えを実現する整数命令」と「ロード命令」に分けるべきですが、全てがロード命令に分解されます。 意図していないアドレスの読み出しが行われるという問題もあります(aperaisさんも指摘しています→Aperais/cvp2v2 by aperais · Pull Request #3 · eric-rotenberg/CVP · GitHub)。

ベースアドレス更新のレイテンシに支配されているようにシミュレーションされているトレースでストライド予測を行ったらスコアが上がるのかもしれません。実際にはシミュレータの都合で不当に遅くなっているのを高速化しただけで、意味はないのですが……。

その他、フラグレジスタを介した依存関係を正しくシミュレーションできていません(トレースに記録されていないデータが必要なため、シミュレータで推測を行っているようですが、それが使われていません)。

ロード命令のアドレス変換には1cycleかかるのにストア命令のアドレス変換は0cycleで終わる

ロード命令の方はアドレス変換にかかる時間をシミュレーションしていますが、ストア命令の方はやっていません。

典型的にはストアアドレスの計算の方がデータ到着より早く終わるため、アドレス変換にかかる時間をカウントしていないのかもしれません。 単に忘れていただけかもしれません。

ストアフォワーディングが0cycleで終わる

ストアを行ったサイクルにストアフォワーディングを待っているロード命令も終わります。

レジスタファイルの書き込みポート数をシミュレーションしていない

一サイクルに実行を開始できる命令の数(演算器の数)は正しくシミュレーションしていますが、一サイクルに実行を終了できる命令の数(レジスタファイルの書き込みポート数)はシミュレーションされていません。

固定レイテンシの命令だけであれば問題なさそうですが、キャッシュミスしたロード命令やストアフォワーディング待ちのロード命令は可変レイテンシであり、一サイクルに多数の命令が同時に終了します。

これは他のものと比べて実装難易度がやや高いですが、リプレイすべきサイクルを計算してリソース占有の予約を入れればシミュレーションできるはずです。


ここまで変な点をいくつか書きましたが、ChampSim(特にdevelopブランチは完全に壊れてしまっています)に比べたら全然ましです。

*1:実際、 https://www.microarch.org/cvp1/papers/Seznec_Unlimited_2020.pdfによれば、チューニングされた値予測器の正答率は99%を超えます。これは、プログラムの挙動が予測しやすいということではありません。値予測器には「予測しない」という選択肢が存在し、それを選ぶことが性能を高めるため、そうチューニングされているからです。

*2:SIMDレジスタを二つ読み込むload pair命令で、ベースレジスタ書き換え付きの場合に発生します。

*3:The 1st instruction prefetching championshipで使ったトレースはCVPで配布されているトレースを流用しているらしく、それを用いた評価(https://research.ece.ncsu.edu/ipc/wp-content/uploads/2020/05/eip.pdf)ではプリフェッチなしの場合23%も命令キャッシュミスが起こるとしています。