CPU実験の振り返り (コンパイラ係目線)
昨日CPU実験の最終発表会があり、無事CPU実験を終えることができました。このエントリはその振り返り、感想、ポエムです。 やった内容をつらつらと書いているだけなので真ん中のほうは面白くないと思うので細かい内容に興味無い方は読み飛ばし推奨です。 細かい内容が20er以降の方の参考になれば幸いです。
CPU実験について調べて到達した方は同期のコア係のMisterのブログ、同じくコア係のつばめの余興ブログ(僕が記事をまとめるのも恥ずかしいくらい彼が成し遂げたことはすごいです)もいっしょにご参照ください。
CPU実験の概要
CPU実験は東大理情(東京大学理学部情報科学科)名物と言われることの多い実験で、下の表にある4つの係からなる班を組んで自作コア上で与えられたレイトレーシング *1のプログラムを動作させることを目標にします。 アーキテクチャ等なんでも自分たちで好きなように決めてよい、FPGAボードが配布されるだけでなんの指示もないので自分たちで計画したり勉強しながら進めていく、といったあたりが特徴的な実験だと思います。ちなみに発表会で来年から素材がレイトレでなくなるかも、と教授が仰っていました。
| 係 | 仕事 |
|---|---|
| コア | Verilogでコアを書きます |
| OCamlのサブセットであるMinCamlという関数型言語で書かれたレイトレーシングのプログラムを自班のアーキテクチャをターゲットにコンパイルします | |
| コンパイラ係が吐いたアセンブリをバイナリにするアセンブラを書いたり、コア係やコンパイラ係がデバッグに用いるためのシミュレータを書きます | |
| FPU | VerilogでFPUを書きます |
コンパイラ係についてもう少し詳しく
コンパイラ実験のほうは基本となるMinCamlコンパイラを改造していく形で進んでいくのでこちらの実験もその形で進めていくコンパイラ係が多いですが、2ndあたりから好きな言語でフルスクラッチする人もいます(今年はGo,Haskell,Scalaでフルスクラッチしている人がいました)。僕はC++,OCamlくらいしか書き慣れている言語がない、パターンマッチとかがないのでC++は流石に面倒、という理由で最後までOCamlのままでした。
結果
やったことの詳細などの前に最終結果を記しておくと、総命令数14.18億(akouryyが10.8億で大差で1位)で2位でしたが、コア係*2の爆速コアのおかげで実機で111MHz,16.531秒の19er内最速記録を出すことができました。一応速さコンテスト的側面もある実験なので嬉しかったです。
やったこと
ここからは僕がやったことを時系列順に書いておきます
9,10月
まず初回授業で係を決めました、僕は仕事内容的にはコア係かコンパイラ係をやりたいと思っていたのですが、3Sのハードウェア実験でVerilog,Vivadoに対して苦手意識をもってしまったので半ば消去法的にコンパイラ係を希望しました。班が決まったら、まず1stのISAを決めたり(ぼーっとしていたらいつのまにかMIPSベースにすることが決まっていました)、これからの計画についてなどを話しあいました。
1週目
初週はコアのデバッグのためにも、フィボナッチなどの簡単なプログラムのアセンブリをなるべくはやく生成したいと思い、PowerPC向けのMinCamlコンパイラのemitを変更して自班アーキテクチャ(以下Nikujaga)向けに改造することに専念しました。データセクションなどを用意していないので浮動小数即値テーブルの作成などを変更しました。
2週目
2週目はレイトレをコンパイルすることに専念しました。レイトレを動かすにはいくつかのライブラリ関数(sin,cos,atan,sqrt,floor,ftoi,itof,etc.)が必要なのですが、これらを実装するのも通常コンパイラ係の仕事です。とりあえずはやく動かしたいと思ったのでライブラリ関数は初めは精度を無視して適当に書きました。コンパイルできたと思ったらシミュレータで動かすと永遠に処理が終わらなくてその原因特定に時間を溶かしたりしました(結局自分が書いたライブラリ関数の二分探索が無限ループしていた。画像サイズを2×2とかにしてみても中々実行が終わらないときはほぼ間違いなく何かが無限ループしていると思います)。
3週目
もうすぐコアができそうと連絡があったので「全班内最速で10月中に完動させよう」ということでライブラリの精度を規定を満たすように精度を上げたりしていました。その後コアが出来上がったもののレイトレが動かなかったのでコア係がデバッグしているのを横で応援したりしていました。
11,12月
10月中という目標には間に合いませんでしたが11/5に一番早く完動させることができました。これで一段落ついたのでここからは最適化を頑張るフェーズに入ります。
グローバル変数の導入
レイトレのプログラムは先頭で定義される配列を後ろの関数群がなんども読み書きするような構造になっているので、ほとんどの関数に自由変数があり関数呼び出しはクロージャを介したものになります。そこで初めて関数が定義されるまでに定義される変数たちをグローバル変数として扱うことでオーバーヘッドの大きいクロージャ呼び出しをなくすことができます(これはレイトレのソースの特性上そうなるということです)。具体的には配列やタプルのアドレスをコンパイル時に確定しておいて、それ以降でのアクセスではメモリの定数番地に対するアクセスとして処理するようにします。
覗き穴最適化
特定の命令パターンを等価でより効率的な命令パターンに置き換える最適化です。この最適化パターンのほとんどは自分のコンパイラが吐いたアセンブリを眺めて無駄だなと思ったものを随時追加していきました。別の最適化をかけることではじめて見えてくるパターンもあり2月まで少しずつ増えていきました。
定数畳み込み
仮想マシンコードレベルでの定数畳み込みを実装しました。より前段階の中間表現でも定数畳み込みは行われていますがグローバル配列アドレスが即値に変わっていたりすることで仮想マシンコードでも定数畳み込みが効きます。
不要定義削除
定数畳み込み同様に前段階で行われていますが、仮想マシンコードレベルで再度不要定義削除を行いました。タプルを分解してそのうちいくつかしか使わないと使わなかった変数のロードが無駄に残るのでそういったものが消えます。
これを実装したところレイトレが壊れてしまったのですが何度実装を見直しても原因がわからないしシミュレータで実行してみてもどこが悪いのか見当をつけることが難しく結局導入に3週間近くかかりました。原因は覗き穴最適化が間違っていたからで、不要定義削除自体はバグっていませんでした。
このようにバグった覗き穴最適化だけしてもレイトレは運良くバグらないが、さらに不要定義削除をするとそのバグが顕在化するいうこともあるので最適化は全てモジュールごとに切り分けてバグった際は色んな組み合わせで最適化のオンオフを試してバグの原因である最適化を特定する、ということが有効かもしれません。
2ndへ
ソフトウェア実装していたsqrt,floor,ftoi,itofをFPUが実装してくれることになったので、これらを加えたISAを2ndとしました。この頃に追加命令をMLソースから直接触るためにAsmキーワードを追加してインラインアセンブリ風に書けるようにMinCamlの構文を拡張したりしました。
1,2月
1月のテスト後はコンパイラ係向け課題も兼ねてレジスタ割当の改善に時間を費やしました。
制御フローグラフ作成,生存解析,干渉グラフ作成,グラフ彩色
3Sの言語処理系論のスライドやタイガー本などを読んで設計を考えてから実装をしました干渉グラフの実装をしようとしたあたりからocamlgraphというライブラリを見つけたのでそれを利用しました。ドキュメントが少なくて使い方が若干難しいですが色んなモジュールが備わっていて便利でした。
3rdへ
2月末にコア係がコアを書き直すというので3rd ISAで自分の希望する命令を足してもらいました。ずっとやった最適化が他班より多くてもその班より命令数が多いのはなんでやと頭を抱えていたのですがISAの違いはかなり大きいことがわかりました。1st,2ndのMIPSベースのISAでは分岐命令が貧弱でBranch EQual、Branch Not Equelしかなかったので、2つのレジスタの大小を比較して分岐する際は一旦Set Less Than命令でレジスタに値をセットして、ゼロレジスタと比較して分岐するようになっていました。そこでBranch Less Than命令などを追加してもらいました。他にはデータを扱う際は全てワード単位なので、バイトアドレシングからワードアドレシングへの変更も行いました。
Coalescing
レジスタ割当後のmove命令がなるべく減るようにcoalescingを実装し、実際にmov命令が削減されましたが結局元のレジスタ割当より命令数が減りませんでした。減ったと言っている人も何人かいたので自分の実装が悪かったようです。
余ったレジスタの定数レジスタ化
まずゼロレジスタを有効活用するような最適化をかけるとだいぶ命令数が減ったのでレジスタ割付で使われないレジスタを全てプログラム中にある定数の定数レジスタにして定数をロードしてから演算しているところを定数レジスタと演算させるようにしました。
ジャンプの連鎖の除去
ジャンプしてその先ですぐに無条件ジャンプするときは初めからジャンプ先をそこにしておいたほうが得なのでその最適化をしました。最終発表会の前日にやったのですが3000万命令も減って驚きました。
スケジューリング
アセンブリを見ると浮動小数演算してその結果をすぐ次の命令で使う、という部分が多くストールが起こりそうなところが多かったのでコア係と一緒にアセンブリをながめてこういうパターンはこう置き換えようという議論をしてから実装しました。この命令パターンで何clk分ストールするかというのは僕にはわからないことなのでコア係との初めての共同作業でした。スケジューリングで命令数は据え置きで0.3秒も早くなったので驚きました。これは発表会当日の朝地下でやったのですが「もっと協力するべきやったな〜」って言い合ってました(遅い)。
発表会3日前の時点で19.98秒とかだったのですが色々あって当日の朝までに16.53秒まで持っていくことができました。
反省点、教訓など
Verilogを触りたくないあまりコンパイラ係を志望してしまったので逃げずにコア係やってみるのも良かったのかなぁと未だに思ったりします。20er以降の皆さんは積極的理由で係を選ぶと良い気がします。
データフロー解析による不要命令削除や共通部分式削除、値番号付け、エイリアス解析、タプル平坦化など、時間さえあればやれることはまだまだできることはあったなという思いがあります。
コードレビューとかがなく実質個人開発でスパゲッティソースになりがちで、もっと綺麗にしたいなぁというところが最終状態のコンパイラにも大量にあります。リファクタリングを頻繁にすると良いと思います。
あとで変えようと思って変え忘れる、コピペして変え忘れる、が本当に多かったので少なくとも前者は変えようと思った時点でその場にコメントでtodoを記しておいてpush前にtodoコメントが残っていないかチェックする、という習慣をつければよかったなぁと後悔しています。(つばめがこの習慣を実践しているのを教えてくれた、自分の記憶力を信じてはいけません、忘れます)
コンパイラ係はシミュレータ係に欲しいと思った機能はどんどん実装をお願いしてしまいましょう。途中からコア係の要請で指定命令数だけ実行する機能がついたのですが、それまで自分はバグの場所の二分探索をする時にブレークポイントをかけてそこまでの実行命令数見て...みたいな非効率なことをしてたので自分からお願いするべきだったなぁと感じました。
シミュレータにはアセンブリがinvalidでないかしっかりチェックしてもらうようにしましょう。コンパイラは(なるべくassertをいろんなところにかけてチェックするようにはしているのですが)ちょっといじるとすぐinvalidな命令を吐くようにしてしまいます。例えばレジスタのオペランドがよくわからない文字列になっていたり、符号付き16ビットの即値に範囲外の値が入っていたり、ということがあります。そういうときによしなに解釈されて実行されているとバグフィックスに時間がかなりかかってしまうと思います。
またシミュレータの話になるのですが、シミュレータがメモリリークしており、何度も起動しているうちにパソコンがめちゃくちゃ重くなるということがあったのでC,C++で書かれているならビルドのときに
-fsanitize=addressなどのsanitizerで未定義動作やメモリリークをチェックしておくと安全かもしれません。
感想、その他
つらつらとやったことを書きましたが、20er以降の方には是非ここに書いた程度の最適化はササッと終わらせて歴代最高記録(たしか8.何億命令と聞きました)を越えるような最強コンパイラを作って欲しいないう思いがあります。
初めはコンパイラは意味が変わらないようにアセンブリに落とすだけ、最適化も意味が変わらないように変換していくだけやん、と少し思っていましたが、ちょっと触るだけで本当に面白いくらいバグるのでコンパイラに対するイメージはだいぶ変わりました。普段よくつかう言語処理系を開発してる人たちってすごいんやなぁと今はとても感じています。
何はともあれ無事に終わってよかったです、班員のみなさん、19erのみなさんお疲れ様でした。
