東大理情名物のCPU実験で毎週徹夜したお話(技術編)
以前公開した第一部の続きになります。検索等でこの記事にたどり着かれた方は、まず先にこちらを読まれる事をおすすめします。
前回はCPU実験の大まかな概要や昨今の動向について書きました。今回はより掘り下げて、技術的な部分、特に私が担当していたコンパイラにおける各種最適化手法について書いていきたいと思います。前回は一般受けするように書きましたが、今回はたぶんエンジニアの中でも割と限られた層でないと面白くないかもしれません。。。
注意
今から紹介する最適化手法は、あくまでコンパイラ実験課題であるレイトレプログラムに対して有効だった物を紹介しています。そのため、一般的なプログラムに対する最適化としてはあまり効果がない物、そもそも分割コンパイル等の都合上最適化を適用する事が不可能な物等も含まれてあるのでご注意ください。
また学生実験ゆえ、勘違いや間違ってる部分等あるかもしれませんが、そこは生暖かい目で見て頂ければ幸いです。お願いだからマサカリ投げないで(泣)
コンパイラ係のお仕事
技術的な話に入る前に、コンパイラ係がどんな事をやったか（私が何をやったか）について説明させてください。
チーム内での通称コンパイラ係と言われる人は、ocamlに似た構文で書かれているレイトレプログラムを自班のアーキテクチャ向けにコンパイルできるコンパイラを作成します。「作成」とは言っても、もちろんただコンパイルできるだけではダメで、「いかに効率の良いコード生成ができるコンパイラが作れるか」という所まで含めての「作成」です。
まあそういうわけで、コンパイラ作成に終わりはありません。オンラインゲームみたいなものですね。
一番簡単な「効率の良いコード」は、レイトレプログラムを実行した時の動的実行命令数（実際に実行された命令の数）を減らす事です。でも、ただ祈るだけでは命令数は減らないので、的確に最も効果のある施策を行っていく事が重要となります。
周りのコンパイラ係を見ていると、割と行き当たりばったりに「この関数ちょっと減らせるかも～」、みたいな事を話していた印象があるのですが、あまり呼ばれない関数を最適化しても効果は薄いので、きちんとボトルネックを調査してピンポイントで潰していく必要があります。
これを実現するために、私がやった仕事は大きく分けて以下の通りでした。
・動的実行命令数削減のための各種最適化の実装
・レイトレプログラム解析
・コンパイル時間低減のためのアルゴリズム改良
・高速シミュレータの開発
・アーキテクチャ設計
幾つか関係なさそうなのが混ざってますが、それについては追々説明していくので、しばしお待ちを。
まず、コンパイラを作りつつ、ターゲットとなるレイトレプログラムをきちんと読み、各関数を実行した時の命令数を算出しました。
（ここに計測結果をメモった跡があります。例えばこの行は、直後の関数が7.7億命令要したの意。全体の実行命令数が14億とかなので、半分がこの関数に費やされている事になります）
よく呼ばれる関数や重たい関数を最適化する事が効率良く最適化を実装する方法なので、細かなベンチマークを取るのは大変重要です。具体的に書くと、（上のリンクを見てもらえればわかると思いますが）solve_each_element_fast関数、及びその中で呼ばれている関数を重点的に見ていくのが良いかと思います。
ただ、こうやってベンチマークをきちんと取っていくと悲しい事実を突きつけられる事もあります。素人目にはレイトレプログラムのメインの部分って言うと、３Dオブジェクトの描画の部分ではないかと思ってしまうわけですけども、課題のレイトレプログラムだと３Dオブジェクトを描画する部分は実は1億命令もないんですね。
大事な事なのでもう一度説明すると、以下のような画像なら0.5億命令も掛からずに出力できてしまいます。
第一部に載せた画像とは少し光の当たり方とかが違う程度で、正直近視の自分からすると大して変わらないわけですが。この微妙な色合いの変化（間接光計算の有無）によって残りの13億くらいが消費されると考えると、最適化をやる気が失せるわけです。世の中って残酷ですよね。
そんな事言って嘆いても話は始まらないので頑張るわけですけども、次の章ではその頑張って最適化したうちの幾つかを紹介したいと思います。
最適化いろいろ
注意：大事な事なのでもう一度書きますけども、あくまでも学生実験のノリなので、ガチな研究者様方からするとツッコミ所満載かもしれませんが、そこはご容赦ください。
それと、以下の内容の詳しい実装についてはソースをご覧ください。READMEが無いとかテストが無いとかまあいろいろ雑だけど、許して。
インライン展開
超々々基本の最適化です。
関数呼び出しを、その関数の中身で置き換えてしまうというだけ。簡単ですね。
1stの動的実行命令数が最適化を全くかけない状態で120億だったのですが、インライン展開するだけで70億になってしまうくらい、強力な最適化です。
ただ、あんまりやり過ぎるとバイナリサイズが肥大化してしまいます。またインライン展開するかどうかをきちんと判定してやらないと再帰関数によっては、無限に（or 指数関数的に）インライン展開してしまって収集がつかなくなってしまいます。
一番良い判定方法だと、再帰関数はインライン展開しない＆あまりバイナリサイズが大きくなるようなら最適化を抑制する、といった所でしょうか。
定数畳み込み
2 + 3 は5です。当たり前ですよね。であれば、プログラムの中に2 + 3が出てきたら5に置き換えてしまう、これが定数畳み込みです。
この発展形として、関数呼び出し中の引数のいずれかが定数の場合、該当する引数を潰した（その変数を関数内で定数として定義する）新しい関数を生成するというものも実装しました。これが実装できると、以下のような事ができます。
ここに数字出力があるじゃろ？
print_int 32; (* print_intの中では3と2を出力するためにループを回す *)これを
( ＾ω＾)
⊃) (⊂
こうじゃ
( ＾ω＾)
≡⊃⊂≡
output 51; (* asciiの3 *)
output 50; (* asciiの2 *)見事にループを含む関数呼び出しがただの２つI/O命令になりました。バンザイ！
この最適化は最新のコードで入った別の最適化に対応してない都合上、最新版のコードでは動かないのですが、一昔前のコードだと当たり前のように動いてました。これができると結構自慢のネタになって良いです。
とはいえ、こう書くと簡単そうですが、実はこれはアンチパターンを潰すのが結構面倒です。
例えば、我が班のアーキテクチャは掛け算割り算がライブラリ関数として実装されており、その実装は素朴な筆算なのでループが回るわけです。ここで上述のような最適化ができると掛け算も以下のようになります。
mul x 10これは
(x lsl 3) + (x lsl 1)x * 10 = x * (8 + 2)なので、左シフト２回と足し算１回に潰せました。
これは問題ないでしょう。しかし、これが x / 10 という割り算になると、そう話は簡単にならないのです。（これはdivの実装によるとは思うのですが、素朴な実装の場合）実際に同様の最適化を行うと、2の32乗回のインライン展開（指数的にインライン展開される）が発生し、とてもではないですが動きません。
これを回避するためには、コンパイル時に展開可能性を判断するというプログラム解析が必要になります。こいつが結構面倒で、実装に苦労しました。それなりに満足できる物は作れたのですが、やはり完璧な物を作るのは難しく、実際の私の実装では、展開可能にも関わらず展開できないと判断されてしまうパターンがあるような気がします。（特に最新のコードでは別に実装した構文がこの最適化に対応してないため、うまく動かないです）
ぶっちゃけると、真面目に解析するよりも展開後のコードサイズが一定以上にならないように最適化を抑制する方が、計算量的にも実用上も一番良いです。頑張って展開可能性を判断しても、展開後のコードサイズが大きかったら結局話にならないので。
ヒープ領域コンパイル時割り当て
課題のレイトレプログラムを動かすにはmalloc的なヒープ割り当てコードが必要となります。
レイトレプログラムを読むと、まず最初に必要となる配列を一気にmallocする事が分かります。この配列はそれなりの数がある上、全てサイズが決まっているので、コンパイル時に事前にヒープ領域を割り当ててあげる事ができます。
Array.create 10 1 (* 1で初期化された10要素の配列を作成 *)
Array.create 5 0.0 (* 0.0で初期化された5要素の配列を作成 *)上述のようなコードがプログラムの先頭にあれば、
・ヒープの先頭10要素分に対して1を書く
・ヒープの先頭10要素目から14要素目までに0.0を書く
・次にArray.createされたらヒープの先頭値として15を返す
みたいに最適化できるわけです。この最適化を行うと、事前割り当てされた配列についてはポインタの値が定数値になるので、先述の定数展開が捗ってめっちゃ便利です。
クロージャ潰し
クロージャは凄いのですが、デバッグしたり、最適化する際に邪魔であります。出力されたアセンブリを読むのも、クロージャがあると、プログラムの流れがわかりにくくて萎えてしまうわけです。
全てのクロージャを完全に潰す事はできないのですが、幸いレイトレプログラムはクロージャを潰せるような書かれ方しかされていないので、遠慮無く潰すのが良いです。
潰し方は、単純に引数に渡すようにするだけ。簡単ですね。
まあぶっちゃけこれを実装しなくても上述のヒープ領域コンパイル時割り当てをすれば（レイトレプログラムだと）全てのクロージャは生まれる前に死ぬのですが。
全ライブラリ関数min-caml化
レイトレプログラムをコンパイルするには幾つか補助関数を自前で実装してあげる必要があります。いわゆるライブラリですね。殆どの班はアセンブリを使ってライブラリを実装するのですが、私はmin-camlコードとして全て実装しました。（正確には、幾つか独自拡張構文を導入して、その構文を用いて実装しました）この方がインライン展開等が捗って最終的に命令数を減らせるので。
コンパイラが吐くコードよりもアセンブラの方が綺麗に書ける、等と一般的に言われますが、アセンブラなんて人間が書く物なのだから、その時に人間が頭の中で施した最適化をコンパイラにも実装すれば、コンパイラだって綺麗なコードを吐けますよね（暴言）
パターンマッチングによる最適化
個人的に関数言語の素晴らしさを最も実感したのがこれです。
if condition {
true
} else {
false
}みたいなパターンはcmpという一命令に変更した方が余計なジャンプ等が無くなって有り難いのですが、こういった「Aというパターンが現れたらBに変換して欲しい」みたいな物を凄く簡単に書けるようにしました。
これはコードを見るのが一番早いですね。
let pat = [
(fun env -> function
| If(c, x, y, Ans(Li(C(1))), Ans(Li(C(0)))) -> Ans(Cmp(c, x, V(y)))
| _ -> raise Unmatched);
]これだけの事がこんなにシンプルに書けるのは、関数型言語様々という感じです。（コンパイラ自体がOcamlで書かれている）
実装した時にあまりにも感動してしまって、これは一番最初に実装すべきだったと後悔しましたが。
While構文の実装
末尾再帰関数はアセンブラ上ではwhileと同等になるという話がありますが、フロントエンド内で末尾再帰関数をWhile構文に変換する最適化はやった方が良いです。これができるとLoop Unrollingとかインライン展開が捗るので。ですが私の場合、それらの効果を引き出す前に時間切れになってしまいました。。。ごく簡単なもの（変数のSaveを外に出すとか、ループが回る際に、無駄なSave,Restoreになってる部分を潰す等）は実装しており、１億命令くらいは減ったのですが、大幅に減らせるポテンシャルを持つと考えられるだけに、これだけで終わってしまったのが悲しいですね。
ちなみにここではあまり詳しくは書きませんが、Whileの実装はめちゃくちゃ大変です。そもそもWhile自体が関数型言語の構文ではなく、手続き型言語の構文なので相性が悪いのです。
変数再代入をどうするかとか、レジスタ割り当ての都合上、変数の生存区間を考えてなければいけれないけれども、continueでループ先頭に戻るケースで生存区間をどうやって判断するの、とかとか。
一応上手く実装する事はできるのですが、バグを埋め込みやすく茨の道です。
アーキテクチャ最適化
正直これが一番効果絶大です。
1stが最適化を頑張っても実行命令数60億という割と悲惨な結果になってしまったのですが、これに簡単な命令、特に即値演算系の命令を足すだけで20億まで減りました。（加算命令として２つのレジスタの値を足すadd命令しか無かったのを、addi命令を追加し、レジスタと整数値を直接足せるようにする等）
ldwi（整数インデックス修飾つきメモリアクセス命令）とか、cmpi（整数比較命令）とか、実装すると効果的な命令は幾つかあって、それらを実装すると面白いように減ります。
他に追加した面白い命令はというと、浮動小数点加算(fadd)と浮動小数点絶対値取得(fabs)を一度に行える命令や、レジスタの値が0であったら、！！別のレジスタに0をセットして！！、特定のアドレスにジャンプする命令等というのも作りました。
後者については、以下のようなパターンがレイトレプログラム内に頻出する事を念頭においたものです。
if flag then
(* hogehoge *)
(* hugahuga *)
else
falsethen節内ではいろいろな処理をするけれども、elseの場合はすぐfalseを返してしまうというパターンでは、「別のレジスタに0をセット」する事で戻り値にfalseを代入できるというメリットがあります。
とまあこんな感じでいろいろな命令を追加してみて思ったのは、真面目に最適化を頑張るよりもレイトレプログラムでよく使う命令を見つける事に全力を尽くした方が効果があるかもしれません。身も蓋もないですが。
CPU実験の正式名称が「プロセッサ・コンパイラ実験」にも関わらず略称でコンパイラが抜けてしまうのは、結局コンパイラ係といえどCPUのアーキテクチャを考えなければならないという意味でCPU実験だからなのでしょうか。うーん、深い。
ちなみに、第一部では冗談めかして「アーキテクチャ設計をコア係から奪い取った」等と書いたものの、こういう経緯もあるので、命令数を減らしたいのであればレイトレプログラムをきちんと読み込んでいるコンパイラ係が命令セットを設計するのが良いのではないかと思います。
個人的には、「コンパイラ係に命令体系の設計を任せるとロクな事がないよね～」と仰っていたTAさん（元コア係）が、最終成果報告会での私の上述の発表を聞いて、「そこまできちんと研究できるならコンパイラに任せるのも有りかもしれませんね」と仰ったのが凄く印象的でした。頑張った甲斐があるというものです。環境改善話を元に戻して、コンパイラ係の仕事という話でいうと、いくつか環境改善も行いました。
まず一つ目に高速なシミュレータをコンパイラ係で（シミュレータ係が作った物とは別に）作りました。
普通シミュレータというとインタプリタ的にバイトコードを解釈して実行するのが一般的なのですが、自班のアセンブリコードをx86のアセンブリに変換してそのままネイティブ実行してしまうという物です。考え方としてはJITに近いのかなぁ、といった感じです。（JITはいろいろ面倒なので、手軽で同等のパフォーマンスをと考えたらこうなりました）
1stがどんなに頑張っても60億命令だったので、シミュレーションに時間が掛かってしまい、中々デバッグが捗らなかったのを改善したかった、というのが主な動機です。こいつのお陰で60億命令でも3秒程度で実行が完了するようになり、大変助かりました。（割と手抜き実装だったので、きちんと実装すればもっと早くなるはずです）
これに加え、コンパイラ係が自由にできるシミュレータがあるというのは割と便利で、2ndの命令セットを考える時に勝手に命令を追加してあーでもないこーでもないとできたので、想定外な所で役に立ってくれました。
またこれとは別に、コンパイラのコンパイル時間（自作コンパイラがレイトレプログラムをコンパイルする時間）の改善も行いました。
私はコンパイル時間が長いのがとにかく嫌いで、（その意味で言うとC++のboostライブラリなんぞはマジでストレスでハゲそうになるのですが）最適化をいろいろ実装していくとどんどんコンパイル時間が長くなっていってしまいます。
最初は一瞬だったコンパイルが６分とかになっていく惨状を見て、これはどげんかせんといかん、と。
min-camlのコンパイル時間で一番のボトルネックになっているのは、レジスタ割り当て等のコードで、直後のコードの自由変数を列挙するコードで、毎回ゼロから列挙していく事によりO(N^2)になってしまっています。これはインライン展開等により関数サイズが増えるとNが大きくなってコンパイル時間の増大に繋がってしまうため、上手く列挙した変数を再活用してあげる事でO(N)にする必要がありました。総評いろいろと最適化について書いてきたものの、上述の最適化の多くは最初の２ヶ月間によって実装されたもので、結局12月辺りに命令数が14億台になってから1月2月は殆ど進捗はなく（いろいろと実装はしていたのですが、結果を出す前に別プロジェクトに時間を吸われてしまいました）、最終的な動的実行命令数は14.3億という所で落ち着きました。ちなみに、12月からサボってた割には命令数自体は今年度最小でした。CPUに優しくない命令を沢山追加すれば、もっと簡単に命令数を減らす事ができると思うのですが、もちろんそういうズルは抜きにしてそれなりに命令数を減らせたかと。
とはいえ、過去の歴史の中で一番命令数が少なかった例が8億だそうなので、頑張る余地は沢山残っています。精進が足りてませんね。最後に「コンパイラを書く」と聞くと少しおっかなく思う方がいるかもしれません。実は私もその一人でした。一応軽くLALRパーサーを書いたり、C言語コンパイラを途中まで書いたりした事はあるのですが、CPU実験でコンパイラ担当をできるだけの自信は無かったです。
でも、実際やってみて分かったのは、コンパイラなんて意外と簡単に書けるものです。もちろんmin-camlのコードがベースとしてあった、というのは凄く大きかったです。０から設計するより、ある程度大枠が固まっていた方が絶対に楽ですから。あとは言語構造がOcamlベースで、比較的作りやすかったという点もありました。C++コンパイラとか誰も作る気になりませんよね。
なので、コンパイラを書く事自体はそんなに難しくはないです。でも一番の醍醐味は、自分なりに考えた様々な最適化を実装し、実際に数値で改善結果を得る事だと私は思っています。自分が実装した最適化によって高速化されるのは楽しいものですよ？
ただ、もしかしたらこのように思う人もいるかもしれません。「どうせコンパイラなんて書いたって、gccやLLVMには勝てっこないから、書いても意味ないだろ」
それはある意味現実的な考え方かもしれません。でも、例えばCPU実験におけるレイトレプログラムのような、ちょっと変わった環境に特化するのであれば、gccやLLVMに勝つのは簡単です。むしろ、そういう状況であれば最後は自分との戦いになってくるので、gccやLLVMに勝ったくらいで喜んでいるようではいけません。いずれにせよ、「どうせ勝てやしないよ」と言い訳して手を動かさない人よりかはずっと良いと思います。
この記事を読んで、「自分もコンパイラを書いてみたい」と思う人が出てきて欲しいな、という願いを込めた所で、この記事を終わりにしたいと思います。二部に渡って長々とお付き合い頂き、ありがとうございました。
