CPU実験 - てきとーな日記

CPU実験が終了しました。
我々の超ksk班はスーパースカラ+動的スケジューリング(OutOfOrder実行)で100MHzというのを作成し、17.3sという記録でした。
なんとか過去の記録は抜けたものの、基板の変更があったので単純には比較出来ない上、実は150MHz(もしくは133MHz)用に作成していたものの間に合わなかったり、分岐予測がうまく機能していないようだったりともう少し時間があれば…という感じでした。
以下、大体の流れ

第一期アーキテクチャ

昨年10月に班が決まり、第一期アーキテクチャの作成が開始しました。
とりあえず過去の班の資料を参考に、絶対必要そうな命令だけからなる単純な命令セットを作成して、50MHzのマルチサイクルで動かすことになりました。
今年から新基板になるハズだったのですが、このときまだ基板が届いておらず、ひとまずは旧基板で作成することになりました。
自分はシミュレータ係となり、暇になったらコンパイラの最適化を手伝うという感じになりました。
MinCamlを読みながらのんびりシミュレータ&アセンブラを作っていたところ、HW係の方々が神すぎてあっという間にHWの方が完成してしまったため、自分も急いでコンパイラからレイトレのコードを吐けるように、最後のアセンブラを吐く部分を手伝ったりしました。
結果、10/16にシミュレータで初画像(真っ白)、17日にそれっぽい画像が、18日についに正しい画像を出すことが出来ました。
さらに翌日には実機でレイトレが動作し、作業開始からわずか２週間でレイトレ完動を果たしました。
この時の記録が34億命令338.985sで次の日にはkskさんによりキャッシュが搭載されたり(こんなにすぐに付けれるものだったのか…)、コンパイラがちょっとはましなコードを吐けるようになったりして、10/22には26.6億命令141.234sとなり、ここで第一期アーキテクチャの開発が終了しました。
ここまでに行った最適化は、ライブラリを書き換えてクロージャが作られないようにしたり、零レジスタの活用、定数テーブルやグローバル配列の読み込みをラベルから直接行うように、といった単純なのくらい。

第二期アーキテクチャ

予想外にスムーズに第一期アーキテクチャが完成してしまったため、まだ新基板が届いておらず、次のアーキテクチャも旧基板で作成することになりました。
第二期アーキテクチャは、命令種を少し増やし、100MHzのパイプラインで動かすことになりました。
主な特徴としては、レジスタが整数・浮動小数共有で64本、比較と分岐がcmpとjmpの２命令、ディレイスロットなし、HW側でストールといった感じです。
kskさんが神なおかげでソフトウェア側でnopを挟んだりディレイスロットを埋める必要がなく、仕事が減って楽になりました。
ソフトウェアの方は一度作ってしまえば、命令セットが変わってもちょっといじるだけで終わるので、自分はコンパイラの最適化とレイトレソースの理解に努めることにしました。
まず、命令セットの変更により命令数が23億くらいに減りました。(即値比較やレジスタ+レジスタのロードができるようになったり、sqrtがライブラリからFPUへ変更になったり、レジスタの本数が増えたりした)
このころ、Javaで書いたGUI付きシミュレータが遅すぎて(１レイトレで３分くらいかかる)我慢ならなかったので、Cで総命令数のカウント以外何も機能のない高速シミュレータを書いたりしました。
こっちだと30sもあれば画像を出せて、コンパイラをいじる上でとても役に立ちました。(高機能の方は統計とったり、デバッグしたりするときのみ使用)
あとはflessとかをコンパイラの組み込み命令化したり、よく使いそうなグローバル配列を直接レジスタに割付けたりして11月初めには20億切りを達成しました。
その後、コンパイラ係のhotaさんにより共通部分式除去(GVNとかいう手法があるらしい)の実装とレジスタ割付の改良(呼び出す関数内で使用されないレジスタは退避しない)が行われたり、自分がスタックアクセスの挿入位置を改良したりして(最終的にはスタックアクセスはほぼなくなるのでこれは不要だった)、12月初めには15.5億命令くらいまで削減出来ました。
HWの方は100MHzで安定動作させるのがとても大変らしく、制約を満たしていて単体テストだと正常動作するのに、全体で動かすと正しく動作しないみたいな状況でした。
また、ようやく新基板が届いたものの、なにやら色々と問題があるようで、新基板担当となったxyxさんが大変苦労していました。
12月は、自分が別の仕事で忙しくて、無駄なジャンプ除去や、不要引数除去くらいしか最適化を行えませんでした。
それでもこの時点で14.6億命令くらいで、比較命令が2.1億くらいあることを考えると過去の人達とあまり変わらないような気がして、実はコンパイラコードじゃこれ以上そんなに減らないんじゃないか、とか思っていました。
1月に入り、自分は完全にICPCモード。
1月の終わりに、ついに実機でレイトレが正常動作(87.5MHz)し、またGShare分岐予測とCallStackが搭載されました。
2月中旬、ついに旧基板100MHzでレイトレを動かすことに成功し、ここで第二期アーキテクチャの開発が完了しました。
この時点でリンクレジスタが不要になった分が減っただけで14.5億命令くらい

第三期アーキテクチャ

これはただ単に第二期アーキテクチャを新基板へ移行するだけでした。
新基板用のモジュールなどはすでに作成してあり、移行はスムーズに進んで３日くらいで完了しました。
その後、新基板で150MHzまでクロックを上げることに成功したものの、それでもまだ過去の記録を抜けないという状況でした。
自分は、HW側でストールしてくれるおかげでサボっていたパイプラインシミュレーションをようやく行いました。
その結果、ものすごくストールしまくることが発覚…
特に浮動小数演算の依存関係がひどく、どうしようもない感じに…
急いでスケジューラを作成してみたものの、それでもどうしようもないストールが大量にあり、分岐先からも命令を移動させる投機的スケジューラの作成を行いました。
ところが投機的スケジューラを用いてもまだ埋まらないストールが存在し、また、このスケジューラを用いたコードはなぜか実機動作しませんでした。
また、シミュレータでの予想時間と実機での動作時間に3.5sくらいのズレ(実機の方が遅い)があり、結局これも解決しませんでした。

第四期アーキテクチャ

３月になり、最終アーキテクチャの仕様を決めることになりました。
まず、ボトルネックとなる部分が大体、loadしまくったもの同士をFPUで演算しまくり、その結果を比較して分岐するという感じで、第三期アーキテクチャではFPU間に４つ命令を挟まないといけないため、分岐先から命令を移動させても全然埋まらない、という問題点がありました。
また、分岐予測が付いているのに、比較命令が別にあるため、効果が薄れているという問題もありました。
そこで、FPUのうち、3clkで動作可能なfaddとfmulについては3clkにし、また比較と分岐は1命令にすることになりました。
また、fabsやfnegはフラグを用いて他のFPU命令と同時に行うことになりました。
あとは新基板となったことを生かすために何かできないかということになり、命令を全てブロックRAM上に載せることが可能であったため、命令キャッシュが不要となりました。
また、これにより1clkで複数命令を発行でき、スーパースカラ化が可能となりました。
しかし、ただ単にスーパースカラ化したところで、依存関係によるストールがある限り大して性能向上が得られないため、分岐予測を生かすために動的スケジューリングでOutOfOrder実行を行うことになりました。
これに伴ない、レジスタが整数・浮動小数別で64本ずつ、CallStackは廃止されることになりました。
この時点で残り２週間、ここから怒涛の最適化タイム開始。
まず、命令セットの変更により、一気に命令数が12.2億に。
次にグローバルレジスタ割付を実装し、スタックアクセスをほとんど撲滅し、11.5億。
また、IO周りをインライン展開しないよう制御することで、総命令実行数をほとんど増やすことなく、命令サイズ2^13制約を満たすことに成功。
hotaさんにより、タプルの共通部分式除去が強化され、ついに11億切りを達成。
条件式の中のif文(要するに&&)の部分のアセンブリがとてもひどかったので、基本ブロック分割を実装して無駄な比較の除去を行い、ついでに同一ブロックのマージ、If文の二重化、ブロックの順番の変更などなどを行って10.1億命令に。
引数レジスタを関数内で保存することで関数呼び出しによるmovを削減し、ついに10億切り達成。
ここからついにハンドアセンブルの神nuさんの行ったタプルの中身を展開するという最適化にコンパイラで挑む。
てきとーに配列長推論を組んだところ、３次元ベクトルのサイズが６になってしまい失敗…
それをてきとーに修正したところ、なんかうまく配列長が推論できた(とても怪しい…というかたぶん嘘ｗ)
あとは中身の展開をとりあえず手抜きで嘘実装し、9.5億命令切りを達成(結局修正する時間がなくて、嘘のままになってしまった)。
各種パラメータをいじって9.3億命令まで削減し、最終日、徹夜で引数のタプル・配列を展開して渡すのを組んで8.8億命令に。
結局、12.2億から8.8億まで命令数を削減出来ました。
がんばればコンパイラコードでも8億切りくらいはいけそうな感じなので、ぜひ来年以降の人達には頑張ってもらいたいです。
また、HWの方は終了２日前についに実機でレイトレを動かすことに成功し、そこからDキャッシュの搭載、同種命令間でのフォーワーディングによるレイテンシの軽減、などが実装されていきました。
しかし、どうやら分岐予測が正常動作していないことが発覚、頑張って原因を探りましたが結局このバグは終了までとることが出来ませんでした(分岐予測ミスのペナルティが最低8clkはあるらしいです)。
また、新基板は非常に合成に時間がかかるため、66.6MHzでデバッグしていたところ、終了までに本来の予定だった150MHzや133.3MHzでの合成に成功することができず、結局100MHzで動かすことになり、17.3sという結果になりました。
本来であれば、シミュレータ係の自分が動的スケジューリングのシミュレーションを行い、このアーキテクチャでどのくらいの性能が出そうなのかちゃんと計算するべきだったとは思いますが、時間がなくて行えなかったので、うまく動作していたらどのくらいの時間になったのかは分かりません。
ともあれ、最後の２週間という僅かな時間でスーパースカラ+動的スケジューリングを一人で動かしてしまったkskさんは本当に神です。
班のみんなお疲れ様でした。