東大IS名物のCPU実験が3/17に最終発表を迎えて無事終了しました。半年のCPU実験を始めるにあたって初めにお世話になったのが先輩たちのブログだったりするので、恩返しの意味で僕もここに記録を残して置きたいと思います。基本的に今後ISでCPU実験を行う人々に向けた記事なので関係ない人が読んでも面白くないかもしれません…(OBが酒の摘みにニヤニヤしながら眺めるのはアリかも)。
CPU実験復習
CPU実験といえば
という知る人ぞ知る超鬼畜演習です。CPU・コンパイラの「性能」はmin-rtという共通のレイトレーサープログラムを動かすことで計測します。FPUは自作することが要求されます。その上で吐かれた画像にdiffがあったら単位がもらえないことになってます。レイトレーシングに15分以上かかってもアウトらしいです。怖いですね。
ちなみに、これを全部学生一人にやらせるのはさすがに酷いと考えたのか、4人班で1つのCPU・コンパイラを作ることになってます。あとCPUもTTLで手配線みたいなことはしなくて(昔はしてたらしいですが)、FPGA上で全部やります。効率的ですね(ブレッドボードに回路を組む演習も別にある)。
14er全体の結果
速度覚えてるのが上位4班だけなのでそれだけでも書いときます。
| 班 | 時間 |
|---|---|
| 7班 | 31秒 |
| 1班 | 37秒 |
| X班 | 39秒 |
| 4班 | 80秒ぐらい |
| その他 | 4〜8分ぐらい |
14erには半年間コンパイラを高速化し続けた班がいなかったので偏差が小さいです。それにしても7班のemakコアはすごかったですね。実行命令数は22億ぐらいらしくそれでこの速度はかなり速いです。
CPU実験の単位要件である「完動」は全班が12月までに終えていました。最速完動は僕の所属していた3班で10/27でした。11月中には半分ぐらいが完動していたはずです。
ちなみに、CPU実験の最終発表会は班ごとに行われる「余興」も楽しみの1つです。今年は音関連の余興が多かったです。「レイトレの音」を演奏した2班のはめちゃくちゃおもしろかったです。ちゃんとオシレーターを操作して「音」から作ってました。1班はMIDIキーボードの入力端子と音源、スピーカーを基盤にくっつけてミニ演奏会してました。
ぼくがやったこと
3班でコア係をやったあと3班を離脱してX班を結成してCコンパイラの作成をやったのとコアを書いたのとOSの移植をめちゃくちゃちょっとだけやりました。X班の成果の詳細はうどんくんさんが↓にまとめてくれてます。
X班はOS移植に3人、Cコンパイラ作成3人で2月初めまで作業したあと、僕がCコンパイラから離脱してコアを書いてました。コア係1人はつらかったです…。今後CPU実験する人たちはコア係を大切にしてあげてください。まじで。
時系列
10月
CPU実験はじまり。コンパイラは作ったことあるしコアの方が勉強になるかなあと思ったのでコア係になる。班の決め方はランダム。班決めが終ったその夕方にはISAが完成してた。とにかく最速完動したかったのでコアの負担を減らすべく命令の種類を極端に抑えた(全12命令・単一フォーマット)。
最初はマルチサイクルのおもちゃマイクロアーキテクチャを実装した。そもそもCPUの内部構造とかよくわからなかったしVHDLも不慣れだったので今見返すとひどい回路だけど…。ちなみに、CPUを作るというとALUとかが一番最初に思い浮かびますが、実際に一番大変で時間が取られたのがシリアル通信モジュールとメモリコントローラです。シリアルはスタートビットを検知してから位相を180度ずらすのと、スタートビットを検知してからちゃんと10ピリオド読み切るのさえ守ってればちゃんと動くはずです(9.5ピリオドしか読まずに死んでた班がいた)。あとせめて読み取りだけでもバッファリングしましょう。
そんなこんなで気づいたら完動。FPUもシミュレータも優秀でバグが出なかった(ありがたや)。とくにライブラリを完璧に作成してくれたコンパイラには感謝してます。
11月
1st ISAは初めから捨てるつもりで作ったものだったので2ndにとりかかる。如何にも速そうでかっこいい名前を考えてくれと言ったら学科民がGAIAというのを考えてくれた。OoOは回路規模が限られていることと分岐予測・キャッシュをまじめにやらないとあんまり意味が無いという噂を聞いたのでとりあえずインオーダーパイプラインで行くことに。が、このへんでCPU実験へのモチベーションが一気に下がり始める。
今から思い出すと11月は一日中ゲームしてた記憶しかない…。2週目を過ぎるか過ぎないかあたりで隣の班がシミュレータ完動(=ソフトウェアスタック完成)して合同班でOSを動かす話が持ち上がる。面白そうなのでうちの班のコア係とコンパイラ係が合同班に移籍して3班がそこで事実上消滅する。
そこからしばらくして合同班に人が集まり始め、計4班から7人が集まってGAIA上でxv6というUNIX系OSを動かすことにする。Cコンパイラをスクラッチで書くことも決まった。
12月
ひたすらCコンパイラを書き続ける。ふとコアを書く気になって一週間でパイプラインCPUとデータキャッシュ(動かない)を作る。
Cコンパイラの開発はめちゃくちゃおもしろかったしそれだけで3000字程度の記事ならさらっと書ける…けど詳細は割愛。
個人的な用事で年末年始2週間ほど日本にいなかったりもした。
1月
ひたすらCコンパイラを書き続ける。このへんでOS移植班がちょっとずつ進捗を出しはじめて、シミュレータ上で起動したxv6-gaiaが
xv6... cpu0: starting...
というメッセージを出したのもこの辺り。月の終わりぐらいになってCコンパイラがmini-gmpを動かすことに成功する。ベアメタル用のlibcも大体揃う。
2月
2月初頭。benzをuccに移植する。これでuccに完成した…かと思いきやCHAR_BITを32から8にするという変更の依頼がOS移植班から入る。ここからはCコンパイラ班は僕が抜けて二人での作業に。
benzがシミュレータ上で動いたのでFPGA上で動かすべくコアの実装を始める(2/4)。パイプラインのハザード処理が雑すぎてバグりまくっていたので修正したり、命令キャッシュ入れるためにバスを追加したりしてた。結果benzを動かすことに成功する(2/23)。嬉しくなってブートローダーのプロンプトをかっこ良くしてみたりする。Cコンパイラ班からバイトアクセス命令が欲しいという声が出たので対応する。
月末になりuccの仕様変更が完了。完成宣言が出る。
3月
3/1、OSの移植が完了する。makeすると確かにGAIAシミュレータ上でxv6が動いている…。すごい…最終発表会まで3週間あるのに…。
コアはめっちゃ急いで割り込みとMMUを作る(3/5)。FPGA上でxv6が起動する！シェルが表示されてlsが起動できたときの感動は言葉には出来ない…。が、なんかいろいろ試すとおかしい。すぐOSがハングアップする。どうも割り込みのバグっぽいのでひたすらデバッグの日々…(めっちゃつらかった)。最終的にisim上でシミュレートしたコア上でxv6を実行する暴挙にでるがお陰でバグがみつかって、3/10に無事xv6完動。17日の発表会には間に合った。
1週間余ってしまったのでX班の余興としてレイトレをすることにする。FPUをつなぐ必要があったので強いFPUを持ってた5班からFPU係を引き抜いてくる。これでX班が8人に。2日ぐらいFPUのパイプライン化とリファクタリングに費やす。寝る前に適当に思いついた方法でFPUをコアにつないでみたら1日で普通にレイトレが吐かれた…。アウトオブオーダー完了って意外と簡単なんやな…とか思う。
せっかくFPUがつながったのでコアを高速化し始める。この間にソフトウェア班ではベアメタルlibcをxv6に移植したりシステムコール増やしたりユーザープログラム作ったりいろいろしていたらしい。
粗方のクリティカルパスを切りおえたのが発表会前日でそこから徹夜で高速化するが93.33MHzで限界が見えた。合成中に適当に繕った発表資料を持ってそのまま寝ずの発表会へ…。(関係ないけど打ち上げが当日でしかも焼き肉だったので死ぬかと思った)。
アドバイス
高速化
レイトレで歴代最速を狙うならコンパイラは尋常じゃなく高速化する必要があります。MinCamlをそのまま素直に改造すると20億命令程度になるはずですが、そこから10〜14億命令程度には削る必要がありそうです。ちなみに、LLVM経由でmin-rtを最適化オプションありでコンパイルした場合のx86での命令数ですら14億程度らしいので、14億を切るためにはmin-rtに高度に特殊化したコンパイルを行う必要があります。
コアはIPCが1を越えないと(多分)歴代最速にはたどり着けません。IPCを1以上にするためにはスーパースカラーが必要ですが、インオーダーパイプラインではハザードが起きまくって性能がでません。レジスタリネーミング付きのアウトオブオーダー実行を実装したうえで2命令同時発行のスーパースカラーにする必要がありそうです。ついで、性能に響くのがキャッシュです。キャッシュの性能の指標にはミス率とミスペナルティがありますが、ミス率を減らすには適切なラインサイズとライン数でキャッシュを実装する必要があります。ソフトウェアシミュレータにキャッシュを実装してどのラインサイズ・ライン数がmin-rtを実行するのに最適化を計測するのが良さそうです(うちの代では1班と7班がやってた)。ミスペナルティを減らすためにはearly restart, critical word firstでのフェッチが重要なようです。non-blockingキャッシュもかなり効くと思いますが14erではやった人はいませんでした。
サイクルアキュレートなシミュレータがあると発表会直前の高速化レースでとても役に立つはずです。
FPU
FPUは最近はいわゆる「神資料」を参照して作成されることが多いようですが、正直神資料は内容が古いです。itofのソフトウェア実装はO(1)で終わるより簡潔な実装が発見されていますし、fmulで乗算を3回に分ける必要も今の基盤ではありません(スライス内に積まれてる乗算器のサイズが大きくなった)。finvは分散RAMを使用することで1clkで終わる実装を作ることも可能です。faddはgrafiさんがブログで書かれているように2パスのアルゴリズムを使えばパイプライン段数を減らすことができます。fsqrt/finvのテーブルの厳密な作成方法(実験のレギュレーションに沿ったulp誤差を持つように計算したもの)はうちのコンパイラ係をやってたb-inaryが14er wikiに掲載しています。
OS
割り込みは非常にバグりやすいので実装するなら覚悟を決めたほうがいいです。TLBはMIPSのようにカーネルが管理する方式のほうがハードウェアが圧倒的に少なくなる上にメモリのバス権をキャッシュとTLBが取り合わなくなるので色々楽になるはずです。たぶんデバッグが大変になりそうですが。ちなみにうちのコアではMMUがすべてハードウェア制御してます。あと、命令キャッシュを実装することになります。SRAMまわりのハザードを減らす意味でもL2キャッシュを用意したほうがいい気はします。L2キャッシュを実装しないにしてもストアマージは実装するべきだったなあと後悔してます。
その他
twoprocで回路を記述するのは非常にオススメです。ぜひやってください。あと回路規模が50%を超えたぐらいでPARがめちゃくちゃ遅くなります。PARは毎回ランダムに結果が変わるので遅延が小さい回路を生成するために何回かインプリを回して「ガチャを引いたり」しますが、それがしづらいです。 あとうちのISAは統合レジスタにしましたがCPU実験程度の規模のプロセッサではとくに弊害は無かったような気がします。レジスタファイルのポート数が激増するケースは今ぱっと考えた限りでは思いつかないです。統合レジスタのおかげでコンパイラは非常に作成しやすかったそうです。
いろいろ振り返って
14er全体の意識に最近のトレンドである「ホワイト」があったと思います。夏休み前からCPU実験していた人もいませんでしたし、どの班も割りとしっかり線表立てて計画的に実験を進めていたような気がします。さすがに最終日は10人ぐらいが徹夜で作業してましたが…。
X班は歴代でもできなかったOSを動かす(しかも正統なUNIX系の汎用OS)という仕事を成し遂げたので、その点については非常に誇りに思っています。班員全員が非常に優秀で、ほとんどの作業を線表から遅れることもなく完遂していました。このような班の中であってコア係という重要なポジションを務められたことはとても幸運でした。班員のみんなには感謝しかないです。
ただ、X班を結成したことによってレイトレ自体の高速化は中途半端に終ってしまいました。本来注がれるべき高速化への熱意みたいなものをX班が吸い取ってしまったような気がします。レイトレの高速化はそれを目指すチーム同士の切磋琢磨があってこそ成されるものだと思うので…。ただ、言い訳をしておけばX班の結成理由の1つにそもそもレイトレ高速化への懐疑があったのも事実です。コンテストで使われるレイトレプログラム自体がかなり古びたものですし、物珍しさはありません。僕らの基盤も使い古されており過去7年の猛者達に果たして勝てるのか？という諦めに近い感情があったのは確かです。そういった意味で、OSという、ISerの長年の夢でありかつ新規性のある仕事が我々のゴールになったのは、意外と、なるべくしてなったのかなあという気がします。願わくば、今後のCPU実験では僕らの成果を踏み台にして、例えばOS移植なんて言わずにフルスクラッチでunixもどきを実装するとか、もっともっと変態的で面白いことをしてくれる人たちが現れて欲しいですね。
// 後半は愚痴なので気にしないでください。 // あと、高速化が中途半端とか言いましたが、それでもインオーダーパイプラインのハーバードアーキテクチャでここまで戦えたのは掛け値なしに嬉しいです。正直40秒を切れるとは思ってなかった。