CPU実験まとめ。

CPU実験

昨日CPU実験の発表会がありました。私たちのチーム「地下詰妖精」はコンパイラコード18.407秒、ハンドコード17.085秒で歴代の記録を更新し優勝しました。

私はコンパイラ係を担当しHaskellでML言語のコンパイラとアセンブラの製作をしました。
この半年は一ヶ月以上家に帰らない月があったりと、非常に充実(?)したものでした。

来年からCPU実験の内容が変わるので、最後に何か面白いことをやりたいという班結成当初の目標の一つ目は達成できたのではないかと思います。
多分この班が初めて行った事。

  • 実験基盤でゲームを作る
    • テトリスを作成
    • 実機のkoiken君, プログラムのmagicant君, グラフィックのarc君のスキルが見事に合わさった。動いた時は感動した。
    • 自分はminCamlを拡張した言語(minCaml++)のコンパイラを作った。
  • レイトレーサのコードの徹底研究
    • uemura君
    • minCamlのコードをC言語で書き直し、コードの解析をした。
    • 今まで誰も見つけなかった、レイトレーサのコードのバグを見つけたり、最適化に関するアドバイスが的確だったり彼の仕事はすごかった。
  • CADソフトの作成
    • arc君
    • コンテストで使用するSLDファイルをリアルタイムでレンダリングしたり、編集したり、検査したりする機能があるソフト。uemura君のC版エンジン搭載。

この実験をしてて一番良かったのは学科のすごい人達と共に作業が出来たという事でした。
単位と全く関係のないことにも本気を出せる、プログラミング好きなメンバーが集まったすごく良い班でした。

個人的にはソフトウェア係のuemura君にものすごく感謝しています。彼のデバッグ技術と最適化のアドバイスに助けられてばかりでした。
あと、arc君のプレゼンに対する熱意はすごいと思いました。泊まり込んでプレゼン資料のロゴとかイラストを描いたりしてくれました。


個人的にはこの実験で

  • とにかくコンパイラの勉強になった
    • コンパイラの全コードをゼロから書いた(一万五千行ほど)。苦行だったが、これほど勉強になることはない。
    • たくさんコンパイラのコードを読んだ。GHC(これは趣味で), ocamlopt, SML#, SML/NJ, COINSプロジェクト
    • コンパイラ関係の本、論文を沢山読んだ。
  • Haskellの勉強になった。

という収穫がありました。

目標の二つめは10秒切りなのですが、それが達成できなかったのはとにもかくにもコンパイラ係である私の未熟さ故で、班員のみんなには申し訳ない気持ちです。

去年7月頃からHaskellの勉強を初め、すらすらコードを書けるようになるまで4〜5ヶ月かかり、並行してコンパイラの勉強も進め、結局初めて本番用のコンパイラコードが動作したのが1月になってから。
それから各種最適化を急いで実装するもまだアイデアがある段階で期限切れになってしまうという残念な結果になってしまいました。

総インストラクション数は14億4,5千万くらいだったかと思います。過去のコンパイラ係の資料とか見てみると12億切っていたりするところもあるのでしょぼいです...orz

コンパイラがやっている最適化等に関してはいずれ資料をアップするので良いとして、Haskellでコンパイラを書いてみての感想です。

  • スラスラコードを書けるようになるまでが長い
    • 初心者にやさしくない言語
    • 副作用がないのでレジスタ割り当てとか地獄
    • Haskellに関するネット上の文献、書籍が少ない
    • インストールが難しい
  • 実行時の消費メモリが膨大
    • 予想はしていたけれど想像を越えていた。使用メモリが増えていくと突然実行時間が急激に低下する。
    • 終了間際にかなり頑張って実行時プロファイル情報を利用した大域的部分冗長性の除去を実装したら実行にン時間かかりコンテストまでにコンパイルが終わらないという事態に。これが高速に動けば上の記録も変わっていたはず。部分冗長性除去なしだとコンパイル時間は10秒〜30秒くらい。
    • テーブルにIOArrayを使用したり正格性の指定とか色々気を使ったけれどもなかなか改善しなかった。
      • 原因としては考えられる事
      • モナド変換子の使いすぎ。コンパイラモナドの上に各最適化用のモナドを乗せるという構成。最大で3段。
      • テーブルの使いすぎ。副作用が無いので、テーブルを作成しIDを使って参照するというポインタもどきな事をしたのだけれど、これが多分問題。データを読み書きするためにいちいちIO層までliftするという多段の間接参照が発生している。実はIOArrayを使わずに、最上層にMapを用意した方が速いという場面もあった。
      • 今後研究したい
  • 一部のアルゴリズムの記述が非常に簡単になる
    • 遅延評価があるため、直感的に書いたコードがなかなか高速に動く。仮想機械語以前の部分はまったく何も工夫しなくても高速。
    • コードの再利用が出来る。
      • 例えばocamloptの実装では「自由変数の集合を求める関数・ある変数が自由変数として出現するか調べる関数」、が別々の関数になっている。
      • 遅延評価言語で書く場合には不必要な計算はされないので、前者だけあれば問題無い。
      • 構文木の探索をしたかったら、構文木に含まれる式をリストにする関数を一つ用意すれば足りる。
    • やはり副作用バリバリのアルゴリズムの記述は難しい。

来年のコンパイラ係へ

  • とくにかく早い段階で動くコンパイラを作った方が良いです。私はminCamlを改造したもの、ocamloptを改造したものを作成した後に、Haskellでのコンパイラを作成しました。
    • 本番用コンパイラを別に作るという場合にも、ここでの経験が助けになると思います。
  • 0から書いた方が絶対に勉強になります。
    • 既存のコードに修正を加えるのと、丸写しでも自分で書くのでは全然違うと思います。
  • 良いハードウェアを生かすも殺すもコンパイラ次第です。来年はハードウェアが豪華になるらしいので、ハードウェアに並列化などの機能が搭載されるようになるかと思います。それらをどれだけ生かせるかはコンパイラ係に懸かっていると思います。
    • ハードウェアが自分でスケジューリングとかするようになってしまったら、コンパイラの仕事がなくなってしまうかもという話もありますが(笑)
  • 折角コンパイラを作るのであれば、何か一つは高度な最適化に挑戦してもらいたいです。データフロー方程式を解く大域的な物とか。骨が折れますが、やっぱり最適化の効果が高く、おもしろく、勉強になると思います。
  • オープンソースのコンパイラコードで参考になるもの
    • ocamloptはあまり参考にしない方が良いです。実は大した最適化があまり行われていません。また、仮想機械語以後が独自の拡張を追加しにくいような形になっています。C--の最適化部とかレジスタ割り当てとかはとても参考になります。
    • SML New JerseyのFLITというとこのコードが読みやすくて参考になると思います。Loop unrollingとかCode Hoistingとかいろいろ揃ってます。CPS変換とかも。
    • COINSというプロジェクトがあるんですが、中間機械語以降が参考になるかもしれません。自分はデータフローの解析とかでちょっと読みました。先進的な最適化をしたくなったら、ここを読むしかないです。
  • 大学の課題をちゃんとやりましょう。
    • 好きな事ばかりやりすぎて、大学の課題を何もやってなかったので単位を落としまくりました。
    • CPU実験が終わって気が抜けて現実に戻った後に鬱になります。

CPU実験は終わっちゃいましたが、来年までにコンパイラコードで9秒を切るという使命が出来たので延長戦をすることにしました。
まず、試行錯誤しながら書いたためぐちゃぐちゃになったコードの整理と高速化(実装言語を変えるかも)をして、やりたかったけれども間に合わなかった大域的なスケジューリング・ポインタ解析(をして間接参照をなくす)、既存最適化の見直し、この班のハードに特化した最適化とかをしていこうと思います。

それからコンパイラやHaskellに関してこの半年に勉強したことを、ここに少しずつ書いていこうか思います。
Haskellプログラムの高速化に関してもいろいろと実験とかしたいと思います。