suztomoの日記

2008-03-11

CPU実験発表終了

10月から約半年をかけてFPGAの班独自のCPUを作成し、OCamlのサブセットでかかれたレイトレーサ(3Dレンダリングと言ったほうがわかりやすいかな)のコードをそのCPUが実行できる命令セットに変換するコンパイラ、そしてデバッグのためにCPUと同じ動きをするシュミレータを作成するという情報科学科伝統(16年目だとか)の実験です。この学年で全部で5班あるうち、僕の所属する3班は6人で構成され「ハードウェア」二人・「コンパイラ」一人・「ソフトウェア」二人、「基板」一人、という担当に分かれて作業を進めました。

結果としては、今日のデモの時点で残念ながら完璧でないCPUで挑むことになってしまいました(公式記録になるのかは「?」)。FPU*1の誤差によって最適化/非最適化実行の誤差(目では見えないぐらい)があると気づいたのが発表前日になった昨日であったのが悔やまれます。

僕はコンパイラを担当しました。コンパイラは東北大学の住井先生が未踏プロジェクトの際に作成したMinCamlコンパイラに最適化をいくつか追加する形で実装しました。前述のとおりハードウェアでの誤差なしの完動はしなかったのですが、シミュレータで実行した結果、総実行命令数は約16.47億命令となりました。何も最適化を行わない場合が50億命令ぐらいで、1位の1班も実行命令数は14億命令なので、かなり頑張ったように見えますしが、実際はインライン展開という最適化による効果が殆どで、インライン展開を終えてからの最適化に壁があります。


良かったところ・悪かったところ

CPU実験を終え、記念に良かった点・悪かった点など今回僕が作成したコンパイラ、そして僕の所属していたチームについていくつか書き連ねてみます。

自作コンパイラ:よかった点
  • 動いた。
  • ベースとなるコード(MinCamlコンパイラ)があったので作成が早かった。
  • いくつか最適化を加えられた。
  • Subversion(秋まで知らなかった)を使ってソースコードを管理・共有できた。

CPU実験では「とりあえず動かす」ということが第一目標となります。CPUのパイプラインによる高速化やコンパイラによるコードの最適化は動いてから考えるものです。そのためまず既にあるコード、MinCamlコンパイラをベースとして、それを班のCPUに合わせる、という方法をとりました。ほかの2つの班も同様にMinCamlコンパイラを改造したものを使っていたと思います。ほかにも班によってはコンパイラをC++で実装しようとしている人やHaskellで実装している人がいましたが、それでもMinCamlコンパイラを読んでいたり、まずMinCamlコンパイラを改造して最初にコンパイラを作成していたようです。MinCamlコンパイラはコードが約2000行程度で、コンパイラが実行時に行っていることをわかりやすくコンパクトにまとめたものなので、コンパイラの初学者にはありがたいコードでした。

そのMinCamlコンパイラの行う処理に加えて班のCPUに合わせて独自の最適化を施しました。少しだけ速くなったし、何千万行という単位で実行命令数が削られてゆくその変化を見るのは楽しかった。ただ、後述するようにもうちょっとドラスティックな変更を加えるべきだったと思います。

また、今回班ではSubversionでのソースコード管理を行いました。チームで作業をするいあたって今考えればソースコード管理システムを使うのは当たり前ですが、10月の時点でSubversionを使ったことがある人が班に誰もいなかったので、もしかしたらソースコード管理システムなしで進めていた可能性が...怖いですね。結局、僕の部屋にあった使っていなかったパソコンをSubversionレポジトリとして利用しました。ちなみに、ソフトウェア係の一人を除いて結局学外からの利用は滅多になかったので、学科の地下室からのみ接続できる学科共有サーバにsubversionレポジトリを配置してもよかったかも。


コンパイラ:悪かった点
  • MinCamlコンパイラを抜け出せなかった
  • ほかの人のコードを読めなかった。

MinCamlコンパイラを抜け出せなかった、これに尽きます。MinCamlコンパイラで使われているの構文木・レジスタ割り当てがそのまま僕のコンパイラでも使われているので、更なる最適化が見込まれます。教育目的に作られ、特徴としてそのシンプルさを持つMinCamlコンパイラのままでも構文木・レジスタ割り当てなどはある程度は動くものができます。ただ、そこから先の最適化を行うにはMinCamlコンパイラを抜け出せないといけなかったし、このコンパイラを自分の作ったもの、というためにはあまりにもコアの部分を残しすぎたと感じています。既にある構文木をちょっと入れ替えるような最適化に比べてコアな部分を変える最適化ではこれまでに動いていたものが動かなくなる恐れがあり、その恐れに負けてしまいました。結果としてドラスティックな最適化よりも、すぐにできる簡単で既存のコアを残した最適化を進めてしまいました。

そして、MinCamlコンパイラを超えてドラスティックな変更をそれに施し、更なる最適化を目指すにはMinCaml以外のコードを読むべきでした。ocamloptのソースコードでもよかったし、1つ上の大田さんたちが書いたコード*2も読むべきだった。MinCamlコンパイラのコードを読むだけで、他の先人の方々が作成したソースコードを読まなかったのは非常に悔やまれる。ソースコードを読み理解する速さが足りなかった。「プログラムを書くにはプログラムを読むことも重要」というのはdouyomu.orgをこれから主催するid:hayamizの言葉ですが、まさにそれを痛感したCPU実験でした。



チーム:良かった点
  • 動いた
  • みんなやさしい

最終的に完璧な動作ではないですが、動きました。比較的早い11月中にはレイトレの実行を行うことができました。何十時間もかけて作成したコード・ハードウェアが動くというのはとても嬉しいことです。動くことはモチベーションにつながり、さらなる最適化を進められます。とにかく、今回やったCPU実験では早めに動いたこと、というのは非常に大きかったです。

そして、みんなやさしかった。CPU実験に必要な知識をほとんど持っておらず、さらに理解力も良くない僕にとってわかりやすくもろもろの説明をしてくれるという並大抵ではできないことをやってくれた班のみんな、ありがとう。特にシミュレータを作成してくれたK君は僕の要望にこたえてポンポンとシミュレータに新しい機能を付け加えてくれた*3。その機能によって検出できたバグはたくさんあるし、バグが取れたことによって2度と使われなかった機能もあったり。自分の作成した機能が使われなくなっても、それでもしっかり僕が要望を出した次の機能を追加してくれてとても助かりました。

そうそう、このチーム、かなり好きです。「俺、このCPUでレイトレが完動したら焼肉食いに行くんだ...」などといいながら日々大学に宿泊し、レイトレが完動したらCPU実験の節目節目でチームのみんなで肉を食べに行ったり、今日も発表の打ち上げとして僕の部屋に集まってピザたべたりしました。僕にとっては非常に居心地の良いチームでした。


チーム:悪かった点
  • 役割分担

2008年になってから班の半分の人が手持ち無沙汰気味でした。コンパイラ係・ハードウェア係が一人で足りないか、というとそうではないのですが、仮に二人でやっていたとしたら、情報・知識の共有とかの面でかなりの難しさが出るのは確かですが、コンパイラの動きの説明0からやって手伝ってもらったら、もっと刺激をもらえたかも。MinCamlコンパイラの動きを知らないとしても、僕より優秀な人が僕と同じ係についていればもうちょっと頑張れたのではないか、1日しっかり時間をとって、match分を使って構文木を再帰的にいじくる方法を説明してコンパイラ係になってもらうべきだったのか...と今でも思います。

今年度の他の班を見てもコンパイラ係は一人でしたが、前年度のチームsakanayaのコンパイラソースを読むと数人でソースをいじくった形跡が見られました。うーん、構文木などを決めてしまって、それをいじくってもらえばよかったのかなー、、、と今では後の祭ですが、役割分担というのはチームでのプログラミングをする際の永遠の問題点なのではないかなと。


それにしても...

1班は強かったですね。コンパイラをHaskellで実装したり、FPGAの上でテトリスを動かしてDVI出力をしたり、3DレンダリングのCADソフト(?)を作ってしまったりしつつも、これまでのCPU実験の最高記録を塗り替えてしまったのだから、すごいもんです。発表もしっかり準備していてmixiの発言を引用するに「班のメンバーが、うまくパズルのピースみたいに合わさった構成」で、見ていて非常にわくわくさせられた発表でした。

おまけでリンク


まとめ

情報科学科伝統のCPU実験は楽しい。自分達で作ったものが実際に動くという嬉しさやみんなで一つのものを作り上げてゆく喜びがある。ただ、チームプレイなので役割分担や情報共有などでの工夫は必要。

自分の作成したコンパイラ、動いたのは良かったがもっと改造すべきだったし、もっと他のソースコードを読むべきだった。この春になにかしら先人の作ったソースコードを読むことにする。

f:id:suztomo:20080311183451j:image

追記(2010 6/17)

KLab×はてな エンジニア応援ブログコンテスト へ応募!

*1:浮動小数点演算をするもの

*2:MinCamlをベースにしていたが、かなりの最適化が行われていた

*3:うちの班の一番の売りはCPUでもコンパイラでもなくシミュレータになったぐらいだ。

LiosKLiosK 2008/03/12 15:01 すげー

ter*ttiter*tti 2008/03/13 02:23 お疲れさまでした!
特に発表で認識の甘さを痛感したので、心を入れ替えて勉強します。
そのために1、とりあえず山梨に行く。

kzkkzk 2008/03/13 03:00 うちのコンパイラを書いたのはほとんどコンパイラ係のid:ushioda氏です。彼は神。nu氏(9.3秒の彼)と僕が命令スケジューラーを書いたという感じです。

命令スケジューラーや各種最適化は入力の型と出力の型をid:ushiodaが指定してくれたので独立して動けたといのが大きいですね。チームプレイなので、出きる限り並列作業が出来るようにまず下地を整えてくれたのが非常に助かったす。

なんにせよお疲れ様ー。4月からの演習3もがんばれー

suztomosuztomo 2008/03/16 21:41 > LiosK
いえー

>teratti
どもどもお疲れ様でした。

>kzk
なるほど。ありがとうございます。
4月からもがんばります。

はてなユーザーのみコメントできます。はてなへログインもしくは新規登録をおこなってください。