早く振り返りを書けと言われたので書きます。最初は作成したコンパイラについて自慢しようと思っていたのですが、思ったより長くなりそうなので、今回は割愛します。また別の記事にまとめるかもしれません（し、まとめないかもしれません）。
tl;dr
- Rustでコンパイラをフルスクラッチした
- 命令数は約42.7億
- CPU実験を、やろう
CPU実験とは
東京大学理学部情報科学科3年秋学期に行われる、この学科の名物となっている実験です。
検索すれば先代のブログが出てくると思いますが、軽く説明します。CPU実験の最終目標は、FPGA上に自作したコンピュータ上で、自作したコンパイラでコンパイルしたプログラムを実行することです。基本的に4人の班に分かれ、分担をしてコンピュータとその上で動くプログラムを用意します。分担としては、コア係、FPU・メモリ係、シミュレータ係、コンパイラ係があります。
私は3Sのハードウエア実験でVerilogとの相性の悪さを感じたため、第1志望にコンパイラ係、第2志望にシミュレータ係を志望しました。班分けの結果コンパイラ係に就任しました。
コンパイラについてわかっていること
これまでの授業でコンパイラの概念に触れる機会としては、3Sの言語処理系論と関数・論理型プログラミング演習（のOCamlインタープリタの部分）があります。ただそれらを受講したからと言って、いきなりコンパイラを作れと言われても、多くの人は何から手を付けたらよいか分かりません。そのため、コンパイラ係はコンパイラ実験でコンパイラのイロハを学びながら、自分たちの班向けのコンパイラを作成していくことになります。（コンパイラ言い過ぎ？）
コンパイラ係の最終目標は、MinCamlというOCamlのサブセットである関数型言語のコンパイラを作成することです。コンパイラ実験ではその雛形として、MinCamlというOCamlで書かれたコンパイラが与えられます1。コンパイラ実験の課題はMinCamlに機能を追加していくようなものであり、その過程でコンパイラの構成や処理の流れを理解していきます。
CPU実験の進捗
10月
まず、初週に作成するアーキテクチャを相談して決めます。私たちの班はとりあえずRISC-Vをベースとしたアーキテクチャを採用することにしました。担当教員は、例年RISC-Vベースのものばかりでつまらないので、なるべく別のアーキテクチャにしてほしいと言っていましたが…
MinCamlの出力するアセンブリのアーキテクチャはPowerPC、SPARC、x86のいずれかなので、これらを選ばない限りはバックエンド（コンパイラのアーキテクチャに依存するフェーズ）を自班向けに書き直す必要があります。どうせ書き直すならバックエンドだけ自作してしまおうということで、バックエンドをRustで書くことにしました。
フロントエンドはOCaml、バックエンドはRustとなるので、その間の橋渡しをする必要があります。当時はとりあえず書いてみるかという気持ちだったため、FFIなどの面倒くさそうなことはせず、フロントエンドの中間結果を文字列でファイルに書き出し、Rustでそれをパースするという形式にしました。コンピュータが出力してコンピュータが読むだけなので中間結果は可読性が終わっていますが（すべて1行で出力される）、文法としては単純なのでパースにはnomというパーサコンビネータを使用しました。
11月
11月はじめには、fibonacci程度の簡単なプログラムならばアセンブラを出せるところまでいきました。ただ、fibとレイトレには複雑さが段違いであり、配列操作やクロージャ呼び出しなどについて理解を深めながらデバッグをするフェーズに入りました。デバッグ中心の作業になってくるのでモチベーションも下がってくる時期です。当然他の授業もあるのでCPU実験にかかりきりというわけにもいかず、あんまり進捗を生めませんでした。
コンパイラ本体以外では、レイトレに必要な三角関数をMinCamlで実装したり、MMIOやグローバル領域の仕様をコア係と調整したりをしていました。
12月
TSGCTF2 向けの作問がうまくいかず、あーだこーだしながらなんとか完成させたはいいものの、気づいたら他の班にシミュ完動で先を越されてしまいました。そのときはほんとーーうに悔しかったため、なんとか頑張って次の週（正確には12/8）にシミュ完動させました。
このときの命令実行数は、約478億命令でした。最終的な命令数と比べてかなり多いですが、これはレジスタ割り当てを一切行わず、すべての変数をメモリに割り当てていたからです。バックエンドの最適化を一切していないため、アセンブリを眺めているととてもバカな操作をしていました。
また、シミュレータ係との認識のずれがあり動作が違うところがあったため、進捗発表会に間に合わせるために自分でシミュレータを直したりデバッグ機能を追加したりしました。（これはシミュレータ係がかなり分かりやすいコードを書いてくれていたおかげです）。しかし、シミュレータはPythonで書かれていて、256×256のレイトレを実行するにはあまりにも遅すぎた3ので、そのころ気になっていたAntigravityを使い、ISAの仕様書からシミュレータをRustで一から作ってもらいました。多少のバグはあったものの、修正も爆速でやってくれるので、大体1日でシミュレータが完成しました。
シミュ完動まで行ったら残るは実機完動だけです。コアの方も完成が見えていたので、シミュ完動の翌週の発表会の前日に班員全員で放課後教室に集まりデバッグ大会をしました。実機完動まではいくつかの罠があるのですが、全員で集まりそれぞれの知見を出し合うことで、罠を一つ一つ超えていき、罰を一つずつ潰していきました。そうしてついに画像が出るようになったのですが、256×256を実行したときに、97%まで出力されてから無限ループに陥るという実機でしか再現できない意味不明なバグを踏みました。そこから夜通し通話しながらデバッグしたのですがバグは発見できず、実機完動は次週に持ち越しになりました。
次の週、バグはあっさり見つかり（BRAMのサイズ設定をミスり、ヒープとスタックが衝突していたらしい）、めでたく12/18の深夜23:30頃に実機完動となりました。コアは30MHzのパイプラインプロセッサで、実行時間は約49分でした。CPIは約1.9と、これだけ見ると結構性能が良いように見えますが、これはクロックが30MHzにもなるとメモリが相対的に速くなるためメモリストールが相対的に軽くなるだけらしいです。
実機完動したあとは、レジスタ割り当てに取り掛かりました。完動したと言っても、さすがに478億命令は多すぎます。もしこれ以降に作ったものがうまく行かなかった場合、最終成果物としてこれを出すのは嫌だったので、もう少しだけ命令数を減らしておきたいという考えがありました。
1月
レジスタ割り当てがうまくいかなくて悲しい気持ちになったので、気晴らしにVersion 2のコンパイラ（v2コンパイラ）をRustで作り始めました。元々フルスクラッチするつもりだったので、フロントエンドから取り掛かりました。とあるコンパイラ係は1週間でコンパイラをフルスクラッチしたらしいですが、私は正月休みの1週間でフロントエンドも書き終わりませんでした。
v1とv2を並行して進めているうちにテスト期間に突入していき、進捗が止まると思いきや、締切の近いものほどやる気が出ないという逆締切駆動開発により、v1コンパイラのレジスタ割り当てが完成します。（このときの命令数は127億でしたが、のちにバグがあることが判明し、156億になります）
そしてなんとかテスト＆レポートの嵐を乗り切り、Aセメ延長戦が始まるのです…
2月
2月の中旬にコンパイラ係だけ面談が行われます。面談では、コンパイラ実験で制作したコンパイラの構成や工夫点をプレゼンをし、その後は先生や研究室の先輩方とおしゃべりをするというものでした。その面談でなんとかv2コンパイラのグラフ彩色を完成させようと頑張ったのですが、結局簡単なプログラムのみしか対応できませんでした。最終的にグラフ彩色レジスタ割り当てが完成したのは2/16で、やっとコンパイラとしてぱっと見でもまともなコードを出すようになりました。
ここから先はいよいよ最適化フェーズへと突入し、コンパイラ実験で提示されていた細々とした最適化を実装しました。ようやくフロントエンドについても改良を施せるようになったため、11月12月あたりからあたためていた、配列のグローバル化やループ変換などの最適化の実装をやっと始めることができるようになりました。
3月
班ではマルチコアにすることを最終目標として、仕様策定にもかなりの時間を割き、コア係やシミュ係にはかなり具体的に動くものを作ってもらっていました。しかし、コンパイラの方で健全性を保証することが難しく実現が困難だと判断し、最後の１週間は切り替えてシングルコアでできる最適化を班員全員で詰めていくことになりました。最終発表会の１週間前の時点での命令数は83億でしたが、そこから最適化を進めていくことで、最終的には42.7億まで命令数を減らすことができました。その過程でコンパイルにかかる時間が20分になりさすがに虚無の時間すぎたので、プロファイラでボトルネックとなっている箇所を特定し改善するなどしました。結果コンパイル時間を10秒にすることに成功しました。
コア係には、コンパイラの出したアセンブリをスケジューリングするプログラムを書いてもらっていたのですが、条件が甘かったのかなかなかサイクル数を減らすことができず、結局は採用を見送ることになりました。
3/10 最終発表会当日
最終的な結果としては、
- コア周波数 85MHz
- 実行命令数 42.7億
- Cycles per Instruction 2.64
- 実行時間 132.8635 s
という結果でした。
私の班は6番目の発表だったのですが、直前の班が76秒という記録をたたき出し、それに次ぐ記録でした。どうやら命令数は1番少ないようなので、このまま2位で終わるのかなと思っていたのですが、、、最後に発表した班が130秒という記録を出し、最終順位は3位になってしまいました😭😭😭😭😭。 正直この班が伸びてくるとは思ってなかったので、このときはほんとーーーーーーーーーーーーーうに悔しかったです。
ちなみに1位の班のコンパイラ係の振り返りや2位になった班のコア係の振り返りも公開されています。
今回はコンパイラの技術的詳細を説明するつもりはないので、代わりに命令数の変遷を貼っておきます。終盤に実装した最適化がかなりハマったことが分かると思います。
全体を通しての所感
この代は全体的に完動するまでの期間が長く、記録もそこまで伸びていないとされています。これは自分自身を振り返ってみてもその通りで、本格的な最適化を始めることができたのが2月下旬であり、圧倒的に試行錯誤の時間が足りませんでした。その結果命令数を減らすための小手先だけの最適化に集中してしまいハードも見据えた最適化まで手が回らず、命令数は少なくてもハードの性能が活かしきれない結果になってしまったと思っています。
この記事を読んでいる未来のISerに伝えたいこととしては、1位を狙いたい、高速化を突き詰めたい、並列化などの格好いいことをやりたい、という熱意を持っている方は、なるべく早く最適化フェーズに突入できるようにしたほうがいいかもしれないということです。もちろん、他の授業もありますし、1人では完動までは行けませんので、班員をいかに焚き付けてうまく連携して進めていくかが重要となります。CPU実験の最初の進捗発表ではプロジェクトの線表を作らされますが、毎週班の進捗を確認しスケジュールを調整していくことは案外大事であるように感じられます。
とまあ色々ネガティブなことを書いてしまいましたが、授業としては本当に面白く知的探究心が満たされる授業で、この半年間はとても楽しかったです。学部の一実験で、どの係もある一つのプロダクトを完成させ磨き上げるという経験は、ほかでは経験できないことです。このCPU実験だけとってみても、理学部情報科学科に進学する意義になり得ます。記事を読んでいる皆さんにもこの感動を味わってほしいので、進路に迷っている方はぜひ東京大学理学部情報科学科に進学しましょう！
おまけ
メイキング的な？もの
CPU実験カスエピソード集
- コンパイラ実験のコンパイラ向け課題として、「グラフ彩色アルゴリズムに基づくレジスタ割り当ての実装」というものがあるのだが、私はグラフ彩色ではないv1コンパイラのレジスタ割り当てを、屁理屈によってグラフ彩色だと言い張って提出した
- 2月上旬にはコンパイラ係だけ面談があり、実際にレイトレプログラムをコンパイルしシミュレータでの動作を見せる。当時私はコンパイラを壊していて命令数がコンパイルごとに変わる上に正しい結果が出てこない場合もあるという状況だった。面談では、シミュレータでジグザグ模様が出るなどして何回もコンパイルをやり直した上、n回目の試行で正しい画像が出力されたときに上振れを引いて50億命令という記録を出した
- 自動並列化機構を実装すると言ってしない
- ループアンローリングだけはやると言ってやらない
- 256×256では正しい画像が出力されるが、128×128や512×512では視点が傾いた画像が出力される（失敗画像集6枚目）
- そしてこれは今に至るまで直していない
- CPU実験の振り返りで、コンパイラを自慢するぞ〜と思っていたら、どこまでネタバレしていいのか分からずエッセイみたいになってしまった
レイトレ失敗画像集
大体時系列順
footnote
言語名とコンパイラの名前が衝突していて紛らわしいが、コンパイラが実質的に言語仕様を規定している側面があるので、そういうものといえばそういうものなのかも
私の所属しているTSGというサークルで開催しているCTFの大会
単純計算で推定96時間。しかも64×64ですらおそらくメモリ不足で落ちる