September 23, 2005

今年のコンパイラ演習

sumiiさんの日記でコンパイラ演習についての話題が出ていた。

それから、polymorphismとかガベコレを追加するのは、東大理情のコンパイラ演習の課題になるようです。すでにやった人もいるようですが。
とのこと。確かにうちの班のコンパイラ処理系は、俺が多相型をサポートし、xhl氏が組み込みライブラリとしてGCを書いたので、一応多相型もGCもサポートということになっている。

基本的にコンパイラ演習はレジュメが丁寧すぎて困るほど丁寧で、レジュメのアルゴリズムを書き写せば単位取得に十分なモノはすぐ作れてしまう状況なので、それで物足りない人たちは強烈かつ強引な最適化合戦を繰り広げてきたわけだ。コンパイル対象のmin-rt.mlが極度に手続き的かつ人手による最適化がすでに十分に行われていることもあって、関数型言語のコンパイラという面よりはとにかく手続き的プログラムをいかに速くするかという点ばかりに注意が払われてしまう傾向があった。これには、他の点(GC等)を頑張っても大して評価されない(速くなるわけではない)という要因もある(*1)。

unno氏が

あまりにOCamlっぽくないレイトレソースに対して過度に最適化するのはどうよ
進言したり、去年までのコンパイラ演習の「解答」そのものといっても過言ではないmin-camlが一般公開されてしまったりしたので、今年のコンパイラ演習は大きく変わることになるのだろうとは思っていたが、やはり変わるのだろうか。

個人的な意見だが、コンパイラ係は(CPU係と比べ)懇切丁寧なレジュメで手取り足取り何をすべきか教えてもらえるというアドバンテージがあるのだから、もっと頑張るべきだとは思う。多相型・GCくらいは実装しても課題として重すぎるということはないだろう(これまでのようにレジュメでだいたいの方針を解説してくれるならという前提ではあるが)。

ついでに、「アーキテクチャ賞」に並んで「コンパイラ賞」みたいなのもあったらうれしいなぁ、なんて思ったり。去年あったとしたら間違いなく受賞はunnoだっただろう。何はともあれ、今年のコンパイラ係の活躍が楽しみである。


(*1)…俺が多相型の実装を決意したのは、create_arrayを何とかして解決する必要があったことと、unnoが多相型を実装していないと聞いて見栄を張ろうと思ったこと、の2点に尽きるのであって、そうした要因がなければわざわざ挑もうとは思わなかったであろう。やはり対象ソースコード(min-rt.ml)上にコンパイラに対する要求(GCがないと実行できない等)を組み込むことが肝要かと思われる。

| | Comments (2) | TrackBack (0)

July 04, 2005

Wiki公開

今更ながら、CPU実験の班のWiki及び関連資料を公開した。

Firexhl Wiki

主にこれからCPU実験に取り組むことになる3年生が見るとよいのではないかと思う。なお、各班の成果物は地下のマシンise0の/export/disk0/jikken/2004/以下にある(はず)なので、そこで見ることもできる。

| | Comments (0) | TrackBack (0)

April 13, 2005

CPU実験とは!?

何の気なしに「CPU実験」で検索していたらみつけた。「CPU実験とは!?

先輩方があれこれ写真撮ってたのはこれだったのかー。あ、とりあえずうちの班の公開用のページもさっさと作らないと。

ところでうちの班(3班)の記録が当日の混乱でごちゃごちゃになってしまっているが、正しくはコンパイラコードが39.206秒(*)、ハンドコードが39.069秒(多分)。菅原さんには伝えてあるので後世に残る記録としては正しい値になっているはず。

(*)…演算強度削減の実装にバグがあって、削減しきれてない部分が多数あったことがコンテストの2日後くらいに判明。なんで気づかなかったんだろう…。ま、えてしてバグなんてそんなもんだが。

| | Comments (0) | TrackBack (0)

March 20, 2005

最適化MLコンパイラsuc

さて、本腰を入れてコンパイラ係としての話を。

そもそもいつからコンパイラを書こうと思ったのかはわからない。去年の今頃は先輩の日記などを読んで「CPU実験は大変そうだなぁ、CPU係はありえないしやっぱシミュレータだろうか」などと考えていた記憶がある。人生先のことはわからないものだ。

「suc」とは「すしぃ」と読み、そのまま「寿司を食うためのコンパイラ」ということである。名前負けしている…。俺も12億instructionsを達成していればぎりぎりで寿司が食えたかもしれない。

Continue reading "最適化MLコンパイラsuc"

| | Comments (0) | TrackBack (0)

CPU実験を終えて

我々の班が優勝できたのはまず「ちゃんと動いた」という事実、それに尽きるだろう。実際、6チームの中でCPUがきちんと動作して正しい画像を生成し、RS-232Cを使ってサーバーとのやりとりができたのはうちのCPUだけだった。

Continue reading "CPU実験を終えて"

| | Comments (3) | TrackBack (0)

March 19, 2005

祝・CPU実験優勝

我々のチーム◆SiLFFMBgは2004年度の情報科学実験II・プロセッサ実験において、スーパースカラプロセッサ「FX25636」、最適化コンパイラ「suc」によって見事優勝を飾った。記録は39.206秒であった。

CPU実験を終えて書きたいことは山ほどあるが、昨日から38時間ほど連続で起きているので、続きは起きてから書こうかと思う。とりあえず、ちょ~気持ちいい!

| | Comments (0) | TrackBack (0)

February 24, 2005

和風ブランチ

CPUにとってブランチ(分岐)は最大の敵。条件に応じて異なった処理を行えることはコンピュータの最大の利点の1つであるはずなのだが、条件が判明するまでどっちのパスが実行できるかわからないので、処理のボトルネックになりやすい部分である。なおかつ一般的なプログラムにおいては6~7命令に1つは分岐命令とも言われていて、条件分岐をいかになくすか、いかに低コストで実行するかということは現代のCPU高速化における重要なテーマの1つだ。

そんな中、ブランチ前後の命令の関係についてあれこれ考えながら生協で買い物をしていたら、ありました和風ブランチ

xhl氏によって、早速アーキテクチャに「和風ブランチ命令」が追加された模様。

| | Comments (0) | TrackBack (0)

命令数 / IPC = const.

命令数を削減するとIPC(Instruction per Clock)も下がる。命令数を増やしてでも命令移動と並べ替えをアグレッシブに行うとIPCはぐんぐん上がる。しかし、命令数 / IPCの値は常に一定である。よってプログラムの実行速度は変わらない。

ソフトウェアスケジューリングの先駆者おーくらによって提唱された法則を確認するハメになるとは……。

| | Comments (0) | TrackBack (0)

February 10, 2005

min-otha.ml

今日は卒論の発表を見学しに学校へ行った。ちらっと噂には聞いていたが卒論発表とはなかなか恐ろしいモノであった。

午後、ふと何の気なしに「あーレイトレとmatmulの中間に位置するベンチマークが欲しいなぁ、オセロとかどうよ」と呟いたところ、xhl氏を刺激してしまったらしくxhl氏は突如作業モードに。なんと数時間でOCamlOthaのmin-ml版を作ってしまった。

途中コンパイラの謎の挙動(多相型絡みっぽいが謎)に遭遇したり、明らかなバグをつぶしたりしながらコンパイルに成功し、実行するも途中でヘンなメモリにアクセスして落ちる。レイトレは動いているのにまだバグがあるのか……と萎えつつ帰宅したところ、オセロはGCの存在を前提に書かれているためがんがん配列を作っては捨てているとのこと。で、メモリ不足で落ちるということらしい。シミュレータ上でメモリ上限をでかくしてやってみたところメモリを40MB使って無事終了したらしい。性能を見る限りでは15手完全読み@実機くらいはいけそうだろうか。

問題の配列はエスケープ解析すればスタックに割り当てられるメモリなので、エスケープ解析を実装すればメモリ4MBでも問題なさそう。エスケープ解析はそれほど難しくなさそうだったので実装してみようかな。

結果として「レイトレとmatmulの中間」どころかレイトレよりもある意味重いテストになってしまった感がある。

| | Comments (0) | TrackBack (0)

January 29, 2005

レイトレ動作

新アーキテクチャに移行して、コンパイラ・アセンブラ・シミュレータのバグを1つずつつぶしていってようやくレイトレが動作。何もしなくてもアーキテクチャ変えるだけで速くなったりするあたりにちょっとソフトウェア側の限界を感じたりもしつつ。でもまだまだ速くする余地はいくらでもあるので1つ1つやっつけていこう。

とりあえずリファクタリングを伴う大がかりな移植計画は完了したので、やっとこれで心おきなく試験勉強チューニングができ……あれれ?

| | Comments (0) | TrackBack (0)

より以前の記事一覧