Soohの嘆き呟き

競プロ解説記事をかくぞ。

理情のCPU実験シミュレータ係のはなし。

目次

はじめに

この記事は、東京大学理学部情報科学科の3Aにある名物実験「CPU実験」についてです。前から言われていたことですが、ネットにシミュレータ係に関するブログ記事があまりなく情報量が少ない状態だったので、正直何をすればいいかというイメージがつきにくい担当になっています(僕はイメージがつかないまま3Aを迎えました)。ちゃんと何をやるか把握してから自分の希望する担当を選べると良いのでこの記事を書きます。

ということで、早速中身に入りましょう。

シミュレータ係とは

まずCPU実験は大雑把にいうと

  • 与えられたプログラムを自作コンパイラ(コンパイラ係)によってコンパイルし、

  • コアや浮動小数点演算器やメモリに関するあれこれ(コア係、FPU/メモリ係)のプログラムによって、FPGAという基盤上で配線を行い、

  • これが CPU として動くようにする

ことが目標になります。これだけを見るとシミュレータ係は特に何もしていない気分になります。

ではシミュレータ係の仕事とはなんなのでしょうか。

単刀直入にいうと、CPU の動きそのものをシミュレーションする事を指します。より具体的には、与えられたプログラム(レイトレ)がコンパイルされてアセンブリ/バイナリになるわけですが、これをシミュレータ係の作ったシミュレータで動かした時に、コア係やFPU係の書いたプログラムと同じ動き(fpu演算やメモリ上の値など)になるようにすることです。

なぜこんな事をするのかというと、自作コアや自作コンパイラデバッグをするため という一言に尽きます。*1

命令列を受け取った時にどういう挙動を示すのが正しいのかを言ってくれる絶対的である神のような存在がないと、人間のようなちっぽけな存在は、迷える子羊ちゃんたちのようになります。

よって、シミュレータ係の使命は「神になること」です。

まだよく分からんという人でも安心してください、次の内容で詳述しています。

やること

先に列挙していきます。

  1. ISAの決定(自信がなければ他の係と相談して決めるのも全然OK)

  2. アセンブリ/バイナリのパーサー

  3. パースされた命令を実行するインタプリタのようなものの作成

  4. FPUのエミュレート

  5. シミュレータの機能充実

  6. 統計情報の集計

ざっとこんな感じですが、実際には 5番は正直オプションみたいな感じで単位取得には完成したコアの出力と同じものを吐けばOKです。*2

まず ISAの決定ですが、今年は RISC-V をベースとする班が多かったです。 うちの班だけ PowerPC のISAを用いて†圧倒的成長† をしました。

これを早々に決める理由は、2番目でアセンブリ/バイナリのパーサーを書くことになるからです。命令のフォーマットが決まってないと、シミュレータ係は何もできません。

パーサーを書くというのは、コンパイラ係から渡されるアセンブリ/バイナリの列がどのような命令列かを認識する行為だと考えると良いと思います。

これが完成すると、仕様書に沿った命令を実行するようなプログラムをかくことで、インタプリタができます。1つだけ例を挙げますね。

add r4, r5, r6

これはどのISAにもあるような命令ですが、レジスタ4番にレジスタ5番の中身 + レジスタ6番の中身を代入するという命令です。 今現在、パースによってこのような命令だと分かっている状態です。 シミュレータはコアと同じような内部構造を持っているように構造体などを定義すれば良い*3(レジスタがあって、メモリがあって、...)ので、シミュレータ上でもこの演算を行って、レジスタ4番を更新すれば良いです。

そしてFPUのエミュレートです。FPU係は指定された誤差範囲を超えない範囲で高速化をしていくので、実際のIEEEで規定されている浮動小数点演算とは基本的に異なる値が出てきます。なので、これに関してはちゃんと模倣してテストしてあげないと、どこにバグがあるか分からなくなります。

はい、そうすると大体完成しますが、さっき言ったようにコア/コンパイラ係がこれを使ってデバッグ出来なければ、このシミュレータの存在価値は0です。 よって機能を拡充していきます。 例えば、1ステップずつ実行する/実行巻き戻し/ディスアセンブラの作成/GUIの作成 とかが挙げられます。まあ、ここは好き勝手にカスタマイズしてくれて結構です。他の係の要望を聞いて適宜実装して行きましょう。(GUIとか作るの結構だるいし...)

最後の統計情報は、よく分かりません!よしなにやりましょう。*4

まとめ

大体こんな感じです。

正直どの係になっても楽しい地獄が待っていると思うので、覚悟して臨みましょう。

言い忘れていましたが、使用するプログラミング言語は任意です。 トロいシミュレータは怒りを買うかもしれないので、C/C++やRustを使うと良いと思います。

では。

*1:他の係がバグを一切埋め込まない天才プログラマーだった場合には、シミュレータ係の出る幕はありません。

*2:ただし、21er からキャッシュの模倣および実行時間予測が加わりました。

*3:コアの完全模倣をすることをエミュレートすると言いますが、その必要はなくて、飽くまでコアの動きが再現できる程度でいいのです。

*4:実行時間予測をするなら命令数と実行時間の関係性をむにゃむにゃと...