コンパイラとつきあって６ヶ月

長かったCPU実験も、そのコンテストは終わってしまった。まぁ、結果は。。。レイトレのスケジューリングはいいから、作業のスケジューリングをしなさいといったところか。昔、動いたはずなのだが、そのときのbitファイルはどれ？　対応するコンパイラとスケジューラはどれ？　と。ソース管理システムも結局つかうひと次第と。

実験中、昨年の資料とか過去の資料はたくさん読んだな。きっと、来年の新3年生もここを読むことになるんだろうな。読んだからにはたくさん実装してもらいたいものです。あ、でも今日コンパイラ演習のTAさんと話した感じでは、あまりにOCamlっぽくないレイトレソースに対して過度に最適化するのはどうよ的なことを話したから、来年はどうなるんでしょうね。オセロでもいいですね。GC実装しないと動かない。。。
個人的には、より関数型っぽいListや再帰を多用したり、もしくは逆に古典的な科学技術計算に対してメモリアクセス順やSWパイプライニングなどがおもしろいか。ま、スケジューリングなんかもおもしろそうなネタではありますね。

Simulation Report in

brief statistics :
proceeded bundles : 1040388531
posted instructions : 1407850789
proceeded instructions : 1198582435
proceeded clocks : 1164796181
external IPC : 1.20867
internal IPC : 1.02901
external IPC(no miss) : 1.3532
internal IPC(no miss) : 1.15205
data cache miss : 31101912
inst cache miss : -1
total time : 23.2959sec.

environment :
processor clock speed : 50MHz
bundle : 2 slot
register forwarding : Enable
units :
unit0 : Brunch
unit1 : Memory
unit2 : ALU
unit3 : FPU
unit4 : N/A
unit5 : ALU2
unit6 : FPU2

instruction statistics :
i.add : 14167269
i.add.im : 27509249
i.mul : 0
i.mul.im : 31789190
i.equal : 101478733
i.less : 3471664
i.and : 17279606
i.mov.bo : 1024
i.mov.im : 52265195
i.mov.reg : 39675817
i.sub : 1276373
f.sqrt.in : 2197809
f.rev.in : 1613752
f.mul : 145352019
f.ftoi : 409031
f.itof : 0
f.mov.reg : 1384202
f.mov.im : 15436054
f.equal : 11192296
f.less : 26289093
f.abs.less : 26173361
f.add : 63503648
f.sub : 63212496
m.load.i.reg : 172084106
m.load.f.reg : 253445235
m.store.i.reg : 20740404
m.store.f.reg : 23020618
m.load.io.i : 23622
m.load.io.f : 212
m.store.io : 49167
br.co : 0
br.im : 77113297
br.reg : 6147315
m.store.i.p : 0
m.load.io.i2 : 0
m.load.io.f2 : 0
m.store.io2 : 1
m.init.io2 : 1
f.abs : 0
i.shift8 : 0
i.mask8 : 280576

created by QualitySimulator (GRAPE-FRUIT Project)

さて、最終的には12億インストラクションを突破したわけですが、実際のところは命令セットによって大きく違ってくるため、ちょっとくらい差があっても本質的な差はなかったりするわけで。本や論文も読んだが、結局あまり役にたたなかったのかな。というか、多くのことは自明に近かったり、ソフトウェアパイプライニングを実装しようとしたが、分岐が多すぎるくせにループの回数が少なすぎで効果薄いのが明らか。他の有名な最適化はほとんど手動で最適化済みだったり。

とにかく早い段階でレイトレ動かしたかったのは、結局のところ動かしてもないのに問題箇所がわかるわけないでしょという自然な発想。たぶん、一番作業してたのは3月じゃなくて10月。fibが動いてからは型推論とunboxing、このころglobal変数は展開すべしという暴挙にでてclosureが消えた。それでようやく動いた。床が真っ白になるのはfloorの実装問題。当時、左上に紫と白が切り替わる例の点がバグではないかと2週間悩んだのを覚えている。結局double実装とfloat実装で出現するか否かが切り替わってた。

最初異常に命令数が多かったが、なんか定数をsave-restoreしてたみたいだ。130億インストラクションとかいってるし。40こstack積むってなんだよ。ここら辺削ったら命令数が半分以下になったような。このころは元が多かったのもあって、ほいほい命令が減っていた。ターゲッティングを実装したらもう半分になったような。それから、レジュメのsave-restoreは分岐があるとstackをあわせる実装にあっているので、後ろに関数呼び出しが控えていないときはregisterであわせる。C++という汎用中間言語（違）に落として、gccにとおせばいいじゃんと言い出したのもこのころ。10secでテストできる。『配列変数のスカラ化でloadが100減った』そうだ。ぉぅ。

11月下旬。このあたりで中間発表。もうシミュレータ上で動いてるといっても反応薄いなと思ったが、後で聞いたらそれなりに衝撃だったようだ。この辺で28億あったらしい。当時は、即値加算すらなく、アドレス計算は即値をとってきて、加算して、load。大変だ。12月。とにかく実装しまくりですね。φ関数除去時のmovの軽減、wordアドレッシング、述語付き命令によるif文の展開、if文の片方のパスにしか使わない変数の計算を移動、ループに使う変数の加算除去。思いついた順に実装。13日にはシミュレータ上で19億命令、40secを突破。当時はbr周りがすかすかだったので、依存関係を解析してif節中の命令を適度に投機実行するとはやくなったり。この辺、1日1日どんどんはやくなってておもしろい。1日0.5secくらいずつ。キャッシュミスのカウントがはじまるが、24日にはそれ込みでも35secに到達。年越しまでには33sec。当時は関数間にまたがって生存するレジスタを指定する、F氏の手法と同じことをする予定だったようだ。

年明け、O氏が命令のしみだしを実装して、30.5sec。命令セットの関係でIPCは1.3。Virtual.tは出力にむかない。基本ブロックに分解して小さなブロックは除去して、、、29.7sec。片手間にライブラリのSW実装をしつつ、プロファイリング結果に基づく再配置。配置を換えるだけで28.3sec。だんだん手詰まり。F氏に24secで動かすなどとあおられ、4sec短縮計画を練る。ループ内で不変な式をループ外に。結果、遅くなる。ifの関係で実行されない命令までループ外に出してしまったようだ。そもそも該当する命令がすくない。

2月。このあたりで17億命令。依然として即値は代入してからじゃないと使えない。HWが厳しめだったので、半田付けを手伝ったり、デバッグ手伝ったり。

3月。即値関係の命令を乗せたら14億。魔法の命令、f.abs.lessも入れてもらう。HW資源的にも小さいので、効果的。brにフォワーディングがきくらしい。代わりに投機実行は単純に命令数を増やすだけになった。スケジューリング時のしみだしだけで十分。26.0sec。12日。連続するifを論理演算してからbrするのをやめる。0.5sec。外部呼び出し回数800万でダントツのsolve_each_element_fastを1回インライン展開。1.5sec。実行頻度が高いブロックを複製してbrを押さえる。0.2sec。結果、12.5億命令、23.9sec。投機実行を実装し直す。結果遅くなる。ぉぅ。HW側の制約で、やっぱりfaddは2クロック、レジスタバンキングの話、あとなんかあったかな。27secくらいまでもどされる。おーん。実装方針上の問題で、関数間にまたがるレジスタ割付をやっていなかったのだが、帰り際に簡易的なCPS変換の実装方針を思いつく。思いついたからには実装しなきゃいけない。インライン展開できればreturnコストもへるはずだし。0.5secくらいしか速くならない。25.7sec。よく見たら、確かにメモリ周りが減った代わりにmovが増える。バグ発見。25.5sec。できた継続が小さいときは展開。25.0sec。loopのpeelingも併用。24.5sec。関数間でmovが増えないように引数レジスタの位置をそろえる処理。すると、レジスタが足りない。レジスタ割り当ての処理を直してもらう。23.9sec。一連の変換で3secくらい速くなった計算。itofをSW実装。なぜかデータキャッシュミス減少。23.2sec。このとき11.9億命令を記録。
まぁ、あくまで予定だったわけですが。mov命令をもう少し削減できれば22sec代か？　結局floatの定数たたみ込みはやらず。frevの120万回分消せば、これくらい行くんじゃない？　データキャッシュミスはheap領域の位置によって変わるらしい。学科ノートと自宅PCをフル稼働。なんと、6000万から2600万まで上下したり。ひぇぇ。そこら辺は微調整。やっぱり、CPS変換なんてしないでF氏のように関数内で変更しないレジスタを決めた方がよかったかな。命令頻度をみればメモリアクセスが異常に多いのはあきらかで、このあたりの解決が鍵ですよね。即値加算loadは結局アドレス計算はloadの脇に隠れやすいので、命令数ほどの影響はない。それでも、load結果に即値を加算してからloadといって処理のコストは抑えてくれる。ポインタをしっかり解析して、メモリの使い方を変えまくるというのも効果あるかもしれませんね。
そういえば、前日にfmulが50MHzにのらないとかで、O氏が手動配線してたなぁ。でも、浮動小数点プリミティブの実装基準をよく読んで、よく考えたら。。。どうも、この文書の中にたくさんヒントが隠れていたようである。P氏あたりなら、この辺実装してたのかも。

あー、なんでしょね。まぁ、これから連続系なんかがあるわけですが。