CPU実験でコンパイラの改造でハマったところ

この記事はCPU実験 Advent Calendarの1日目の記事である。

1日目なので(?)、とりあえずCPU実験について説明する（とはいえどもこの記事を見ている人でCPU実験を知らない人がいるのかどうかという点については怪しいところだが）。
CPU実験というのは東京大学理学部情報科学科の学部3年の後期に半年間かけて行われる演習のことであり、この学期の授業コマ数11分の6を占めるという、まさに名物演習だ。
受講者（ほぼ情報科学科の3年生）は4人1班に分かれて、それぞれコア係、コンパイラ係、シミュレータ係、FPU係に分かれてレイトレーシングプログラムが動くように自作アーキテクチャを設計してFPGA上でレイトレーシングプログラムを動作させ、その実行速度を競う。

最終的に次のような画像が作られる。

f:id:levelfour:20151127175126j:plain

僕はコンパイラ係になった。コンパイラ係は最近はMinCamlというOCamlのサブセットであるコンパイラを改造して、自作アーキテクチャに対応させる流れになっている（講義でもMinCamlが推奨、というかデフォルト）。
基本的にはMinCamlにPowerPC、SPARC、x86向けのアセンブラを吐くモジュールがあるので、それを流用してMinCamlの中間表現をうまく自作アーキテクチャのアセンブラに変換することがコンパイラ係のメインの仕事。
なのだが、思った以上にいろいろなところでつまづいたり、他の仕事もあったりで結局開発をはじめてから2ヶ月弱かかることになってしまった。

コンパイラ係の仕事

自作アーキテクチャ向けのアセンブラを吐けるようにMinCamlを改造する
レイトレに必要なライブラリを実装する
レイトレをコンパイルできるようにコンパイラを適切に改造する

あたりがコンパイラ係の仕事になる。そして、意外とあと2つが重い。というか非本質的な点が多い。

自作アーキテクチャへの対応

僕の班ではMIPS32を改造して（というよりもほとんど流用して）Carinaという1stアーキテクチャを設計した。
MinCamlにはアーキテクチャごとにx86、SPARC、PowerPCというディレクトリが切ってあり、それぞれにemit.mlというアセンブラを出力するファイルが入っている。
基本的にはどれか一つを選んでコピーして、emit.mlを書き換えていくことになる。

ここでまず一つ。x86を選ぶべきではない。

なぜかというと、x86はアドレッシングモードが煩雑であり、自作アーキテクチャへの対応が面倒だから。
他の2つはRISCなので比較的改造が楽だが、x86にはdisplacementとbase registerに加えてindex registerがアドレッシングモードで使える。
index registerは一般的にはアセンブラで配列アクセスする際に配列の要素サイズを指定しておくことによってループごとに簡単にアクセスできるというシロモノだが、CPU実験ではまずindex registerが必要になる場面はない（よっぽどの物好きでない限り）。
その理由は、実験で使うFPGA基盤(Virtex-5)に乗っているSRAM(メインメモリ)のアドレス幅が32bit（1つのアドレス番地と32bitの記憶領域が対応している）になっているため、浮動小数点数をすべて単精度で実装するため。
MinCamlでは浮動小数点は倍精度で扱う実装になっているが、CPU実験では単精度で十分だ。
SRAMのサイズも2^20なのでアドレス変数も32bitで十分。
さらにこれらのデータがSRAMの1cellにちょうど入るので、データにしろ命令にしろ32bit単位にしてセルに1つずつ詰めるのが最も単純。
そのため、配列アクセスする際もindex=1が基本となるので、x86ほどの複雑なアドレッシングモードを必要としない。

レイトレ用ライブラリを用意する

レイトレを動かすために必要なライブラリは

sin
cos
atan
abs
float_of_int (intからfloatへの変換)
int_of_float (floatからintへの変換)
floor
sqrt
print_int
read_int
read_float
その他雑多な関数群

主にクリティカルになるのが実数算術系のはじめの8つ。sinやcosなど、このあたりは実験のレギュレーションでどの程度まで誤差を抑えないといけないかが決まっている。
この誤差がちゃんと抑えられていないと

f:id:levelfour:20151127175052j:plain

こんな悲しい画像になる。
（「床がバグるときはfloor関数を見なおせ」という格言があるくらいこれはCPU実験では有名なバグの一つのようだ。ちなみにこの時点ではfloorが切り捨てではなく四捨五入になっていた）

実装するときはアセンブラで実装するかOCamlで実装するかというオプションがある。
OCamlの方がインライン展開がきくので後々最適化をゴリゴリかけられたり、human-friendlyといったメリットがある。
アセンブラだとコンパイラのバグの影響を受けないとか、意図しないコンパイル結果にならないというメリットがあるのかもしれない。なんでアセンブラで実装したんだろう・・・

実装した後はこんな感じでx87のFPUで計算した結果と自分たちのシミュレーション結果との誤差検証を行う。

f:id:levelfour:20151127175540p:plain

ulpというのはunit in last placeの略で、最下位ビットを単位としていくらずれているか、という誤差指標だ。
例えば正しい計算結果が1.53(単精度で0x3fc3d70a)なのに得られた計算結果が1.5300009(単精度で0x3fc3d712)だった場合、誤差は

0x3fc3d712-0x3fc3d70a=0x8 ulp

となる。

だいたいの誤差はアセンブラの書き間違いとか、些細な計算式の間違い（符号違いとか多かった）とか、係数間違い（アセンブラだと浮動小数点数を16進数で書かないといけないのでそこの変換ミス）だったりした。
あとは、10年ほどまえに誕生したFPU神資料というやつが代々受け継がれて浮動小数点回りの計算でよく参照されるが、それに微妙な間違いがあって、そこに引っかかることもある（ex. レギュレーションの解釈が間違っていて実装が若干間違っている、逆数の参照テーブルの計算式が微妙に間違っている等）。

レイトレをコンパイルする

ここまできたらあとはレイトレをコンパイルするだけなのだが、意外とすんなりといかせてくれない。
そもそも、配布されたレイトレプログラムはデフォルトのMinCamlの文法では以下の理由により受理できない。

整数乗算/除算演算子が使われている
create_arrayという未定義関数が使われている（Array.createにエイリアスすればよい）
継続演算子（名称合ってるのか？）; (セミコロン)が文の最後についている
評価部(let x = C1 in C2のC2)が存在しないlet文
プログラムの最後に評価される値がunitではない

ざっとこんなところだろうか。以上の記法はすべてMinCamlの文法では違法である。
（他にもあるかもしれないが、先生が今年度中に直すと仰っているので、直っていなかったら文句を言っていいと思う）

さらに、文法的には違法ではないが、「クロージャレジスタがSave/Restoreされていない」というバグ(?)がある。
簡単に説明すると、コンパイルの過程で変数のレジスタ割り当てをしなければならないが、"生きている変数"が割り当てられているレジスタに他の変数を割り当てるときは元の値を破壊しないようにスタック上に退避(Save)する必要があるし、一度退避した変数を使うにはスタックから復元(Restore)する必要がある。
クロージャレジスタの方が一般的な用語ではないので説明すると、MinCamlは（一応）関数型言語なので高階関数や関数のネストができる（部分適用はできない）。
nested functionを実際に機械語で実現するためには、呼び出し前に通常の引数に加えてヒープ上にnested functionで使われる自由変数をわたしたり、nested function自体のアドレスを確保しておく（クロージャ変換という操作だ）。
このときnested functionのアドレスを入れておくレジスタがクロージャレジスタなのだが、なぜかこのレジスタのSave/Restoreが行われない。
この点も直す必要がある（レイトレでは大量のクロージャが生成される）。

ざっと以上の変更を加えてはじめてレイトレをMinCamlでコンパイルすることができる。

つまらないハマリポイント

個人的にハマってしまったポイントを挙げる。

OCamlの比較演算子を勘違いする

OCamlのnot equal演算子には<>と!=がある。<>は値の比較、!=はオブジェクトアドレスの比較だ。
ここでうっかり!=を使っていたがために全くバグの原因がわからず1週間溶かしてしまうという悲劇を引き起こした。
そもそもOCamlでアドレス比較をしたいということはまずないと思って良いので、OCamlのnot equalは<>演算子という点を強調しておきたい。

デバッグ用の存在しない命令を吐いていた

上述のとおり、レイトレでは整数乗算と整数除算が使われる。僕は当初、コンパイラ/アセンブラ/シミュレータすべてで面倒だったので整数乗算/除算命令を実装していた。
しかし、FPGA上では乗算回路はかなり配線量を消費する。除算回路はなおさらだ。
配線遅延は起きるわ、回路規模は圧迫するわで非常に大変。おまけに乗算は×4、除算は÷2しか登場しない（除算はスクリーンサイズの計算に2回使われるだけだ）。
そのため、これらはシフト演算命令を使って実装されるのが定番だ。
ところが、僕は面倒だったので普通に乗算/除算命令を吐いていた。これをコア係に伝え忘れていたため、コア係の時間を3日ほど潰してしまった（本当にごめんなさい…）

まとめ

CPU実験で素早く完動するにはいかにバグの起こらなそうな方法で素早く実装するかにかかっていると思う。
ISA(Instruction Set Architecture)をいかに簡単なものに設計するかも重要なポイントだと思う。シンプル・イズ・ベストというやつだ。

また、いかに早くバグの原因を特定するか、というのも重要だと思う。僕は特に11月、2つの原因がわかりづらい大きなバグに悩まされて、それぞれ1週間ずつくらい溶かしてしまっている。
まずは班員の役割分担がコア・コンパイラ・シミュレータ・FPUと分かれているのだから、どのセクションにバグがあるのかを明確にすること。また、明確になるように目的意識を持ってデバッグすること。
コンパイラ係はコア係の次に原因不明のバグに悩まされることが多いポジションだと思うので、精神衛生を保つことも大切です。
あまり深く考え過ぎないように、別の課題やったり散歩したりご飯食べにいって気分転換してる間にふっと解決することもあります。

これから

1st完動ということで2ndで何をやりたいかなのだけれども、我々の班はとりあえずコア・FPUがパイプライン非対応なので、まずは1stをパイプライン化することから恐らく始まる。
そのため、コンパイラ係の僕は暫くは最適化以外やることのない暇な時間が訪れる（と期待される）。
その間にコンパイラ基盤をフルスクラッチしたいと考えている。MinCamlだとどうにも自分のやりたいことがうまくできない感じがある。これからやっていきたいのは

MLコンパイラのフルスクラッチ(MinCamlより広範な、独自拡張文法も含めた文法を扱う)
lambda liftingなど、クロージャ変換よりも実行効率のよいクロージャの実現
その他有名な最適化の実装(レジスタ割り付けの整数最適問題への帰着など)
LLVM

あたりかな。あと、これは余興という形で班員とも相談になるけれど、独自拡張構文を導入して行列演算をはじめとした数値計算構文を導入して、バックエンドではSIMD命令を吐いて独自アーキテクチャ上で楽々Machine Learningみたいなことができたら面白いかなあと思う。面白いだけで性能は期待できないけど。