コンパイラ→コア→シミュ→FPUメモリの順で記事が少なくなる印象
思い出して書いていたら長くなってしまった......
これは何？
理情3年後期の名物授業であるところのCPU実験が終了し、最終レポートも提出し終えたことで今期の授業が完了しました。CPU実験でやったことを振り返り書き残すことで未来のCPU実験に役立てばよいかと思います。
レギュレーション
2024年度のレギュレーションは以下の通りでした。
- FPGAボード: Nexys A7-100T 1人1台使用可
- minrt (MinCamlで書かれたRayTracing のプログラム) を実行し、256×256サイズの画像を得る時間を計測する。
- 合成の際は周波数制約を満たすようにする。WorstNegativeSlackが負になってはいけない。(実はWNSが負でもある程度なら動いてしまう)
また、今年からコンパイラのベースとしてRustで書かれたmincaml-rs が使用可能になりました。我々の班は土台としてmincaml-rsを使用していました。
シミュレーター係の仕事
公式の単位要件は以下の通りです。
- 班のプロセッサ用の命令セットシミュおよびメモリシステムシミュを開発すること
- シミュレータ上での実行結果がプロセッサ上での実行結果と一致すること
- キャッシュメモリの統計データ（総アクセス回数、ヒット率、ミス率、等）が取得できること
- プロセッサ上での課題プログラムの実行時間を誤差3%以内で推定できること
これに加え、実際は以下のような仕事もやりました。班によっては別の人がやるかもしれません。
プロセッサ上での実行結果と合わせるためにどのみちFPU内部のエミュレートを行うことになることから、ついでに検証を走らせて要求制度を満たしているか確認していました。
やったこと（時期別）
自分がやったことに加え、班員の進捗も含まれています。
10月 (1～4週)
10月の頭に班分けのアンケートが飛んでくる。3Sで関数型言語適正が無いことが判明したためコンパイラ係以外の3つを候補にし、結局自分の書き慣れた言語で開発をしたい (+ 責任が重いと怖い) と思いシミュレーター係を第1希望にした。その他は第2にFPU、第3にコア係を選択した。
班分けが初回授業で行われた。幸いにも希望の衝突は起こらず、全員第一希望で係決めはすんなりと完了した。
最初のうちはRISC-Vをベースにして開発を進めることにし、まずは（恒例の）フィボナッチ関数を計算するプログラムが動くものを作ることとした。自身は書き慣れているC++でコードを書くことにした。（全7班のうち、Rustが1人とCが1人、残り自分含め5人がC++を選択していた）コンパイラやコアがいつ作業完了してもいいように10/14にはアセンブラ、10/15には命令セットのシミュレーターとして動作するオブジェクトを完成させた。 この時点ではコンパイラが完成していない（そもそもRISC-Vへの出力は自分で組む必要がある）ので、オンラインのCコンパイラでRISC-Vへのコンパイル機能があるものを探しアセンブリを出力させた。 Compiler Explorer
他の係の進捗があるまでは基本的なデバッグ機能を実装していた。10/18には1命令ずつ進めるステップ実行、10/23には指定の命令数進めるデバッグモードなどを実装していた。
月末くらいにメモリ係からキャッシュメモリが届くので、キャッシュヒット/ミスのシミュレートを実装した。これで単位要件1つクリア。
11月（5～7週）
コアがパイプラインプロセッサの写経を完了させるが、それを投げ捨ててアウトオブオーダー（OoO）実行を考え始めた。
FPUが届き始めるので、そのエミュレートをしながら完成品についてはランダムテストで精度検証も行った。実際は向こうでテストベンチを書いて検査してくれているので、実際は自分のコードに致命的なバグが無いかの確認であった。同時にコンパイラ係が少しずつ形になってきたので、要望に応えながら命令の追加やシミュのバグ取りを進めた。この頃からgithubのissueが次々届くようになった。pull requestを受け取ろうとしたらちょうど自分がリファクタリングをしているところで、マージに失敗し大事故を引き起こしたことから班内では全てissueで要望を管理することにした。あとforce pushを使ってはいけないことを学んだ。
11月中旬にシミュレーターでI/O命令の再現を適当に実装したことで命令セットのシミュレーションはほぼ完了した。これで単位要件2つ目クリア。Sierpinskiのガスケット（整数命令だけで出力できる画像）やMandelbrot集合（浮動小数点数命令の簡単な検査）を出力できることを確認した。
11/28、ついにコンパイラ係からminrt のコンパイル結果が届く。I/Oの仕様に起因するエラーはすぐ直せたが、どこがコンパイラの不備でどこがシミュレーターの不備なのか分からない状況が続く。float演算を変えると出力結果も大きく変わることに気付き、こちらからはfloat演算のエミュレートを止めC++標準のfloat演算を行うモードを提供した。最終的に擬似命令の展開に問題があることが判明、そこを治すことで大幅にバグの状況が改善した。今まで床しか映っていなかったところ物体が出現するようになった。「レイトレ画像デバッグ Ver.2」も参照されたい。
何やかんやあって、11/30にはシミュレーター上で正しい画像を出力する「シミュ完動」を達成した。自前のシミュレーターという条件を付ければ2着、spike上で完動したものも含めれば3着であった。
12月（第8～11週）
コンパイラはしばらく最適化を進めることになるため、本格的に仕事がなくなった。仕事がないのでOoO実行に関するブログや本、授業スライドを読んで知見を深めていた。6月に計算機構成論の授業で習ったときには全く意味不明だったOoO実行の仕組みをようやく理解した。12/2の時点でOoOに必須のリザベーションステーションおよびコモンデータバスの挙動をエミュレートするコードを書いて将来のシミュレーションに備えていた。結局これらは使われることなく終了した。 残りはコンパイラ係に必要な統計情報を提供しながらFPUのシミュレートを修正していた。
この辺りでシンプルなTomasuloアルゴリズムに基づいた設計に方向性が決まる。この機構だと正確な割り込みを行うことができないという問題点がある。当初割り込みを起こすような命令も無いので問題にならないと思えていたが、分岐予測を行う場合間違った予測を取り消すのにROBなどを用いていることを理解する。しばらくは分岐の結果が判るまで新規の命令を停止する方針で実装が開始するが、本当に大丈夫なのだろうかと心配していた。万が一手詰まりになった場合に備えてリサーチは継続し、その場合は最悪自分がSystemVerilogを書いて何とかすることを宣言した。
1月（第12～14週）
コンパイラがアセンブリ→C++へのトランスパイラを作り、実行結果を1秒で得られるようにしたことによって存在意義がさらに薄くなる。
コンパイラ実験の課題としてJITコンパイラの実装があり、シミュレーターを改造したものでもよいと担当から聞いていたので本腰を上げて実装を開始した。課題が提示された12月中旬時点でこれをやることは決めていたが、実際に実装する段階に移ったのは締め切り3日前の1/7～1/9であった。 全ての命令をサポートするのは厳しいので整数命令のみに限定した。
このあたりの記事を読みながら命令の一部をx86/64のアセンブリに直す作業が続いた。システムプログラミング実験の後半でインラインアセンブリに散々苦しめられていたので、何故こんなことをもう一度やらなければいけないんだろうと考えていた。結局動くものは完成したが、締め切り当日の午前7時までかかった。この辺りから生活習慣をCPU実験に破壊され始めた。
これと同時期にコンパイラ係が「並列実行ができそう」と主張し、最適化と並行して並列化の証明に取り組んでいた。
一度シミュレーター全体のリファクタリングを行うことにした。散らかったファイルをincludeとsrcのようにフォルダに分け、作業フォルダをきれいにした。また、ある行の命令に対応する操作を毎回if文で探していたところ、実行前に対応する操作を関数ポインタの形であらかじめ指定して実行時に関数ポインタを通して関数を呼ぶような形式に変えたところシミュレートが5倍ほど早くなった。なぜこれを最初にやらなかったのだろうかと深く後悔していた。
1月中旬に秋学期の授業が終了し、テスト期間に入ることで進捗はあまりなかった。（なぜかコンパイラとコアの進捗は出ていたが......） 最後の進捗報告会の時点では7班中4班が実機で画像を出力できる「完動」状態にあり、進捗をTAにも心配されていた。 最終週の報告会終了後、毎週進捗報告と方針の相談を行う場を班内で設けることに決めた。
2月
1月の最後からコアが怒涛の勢いでロジックを書き始め、1/31にはメモリと、2/2にはFPUと、2/5にはI/Oの統合まで完成させた。2/9の時点で残りはminrtのみという状態まで持ち込むが、I/Oの仕様や謎のバグに苦しむ。この段階でFPUのシミュレーターに不備があり、FPUの更新に対応できていないことが発覚したため大急ぎで再実装を行い、同時に打ち棄てられていたアセンブラを使えるようにした。FPUシミュの修正でシミュと実機間のdiffが消えるが、同時に発生していた「最適化を一部付けると実行が止まらなくなる」バグは残ったままであった。ここでアセンブラに即値の不足を通知するチェック機能を実装したところ、一部の命令がオフセット幅不足で誤って読まれていることが判明した。これを手作業で修正することにより、遂に完動を達成できた。完動の順としては全班で5番目だったらしい。
残り3週間で命令セットアーキテクチャ（ISA）の移行を行い本格的に並列実行に手を付け出した。この段階で最後にFPUシミュに残っていたバグを解消し、プロセッサとの誤差が消滅したことで単位要件3つ目もクリア。並列実行のシミュレートといっても今起きているスレッドの中で1つずつ順に命令を実行し、必要に応じてメインスレッドが待機するように実装すればよかったのでやることはほぼなかった。ちょうどこの頃他班（ CPU実験2024(byシミュレータ係)｜卯村ウト これのところ）からOoOの時間予測に関する質問が来たことから、OoO実行の競争相手が増えることに警戒していた。実際のところは実装を断念したらしい。
2月も下旬になった頃、ようやく最後の単位要件である時間予測に手を付け始める。OoOに加えてノンブロッキングキャッシュを搭載しており、ハードウェアの機構がこの時点で複雑極まりなくなっていたため、サイクルアキュレートなシミュレートは不可能に近いと判断して方針を打ち切った。リザベーションステーションに受け取られてからコモンデータバスに拾われるまでのサイクル数から、その命令で書き込まれるレジスタが使用可能になる時刻はだいたい推定できる。これを実装すると本来の値の0.9倍程度の値が出るが、それに定数を掛け算すると128,256,512サイズのminrtについては時間予測ができてしまう。この「嘘の時間予測」でお茶を濁すこととした。これで単位要件はクリア（？）
最終盤になるとコンパイラ共々いよいよ実装するものがなくなるため、デバッグ要員としてハードのデバッグ作業を手伝っていた。2/27時点でマルチスレッド版は動き始めていたが、条件によって命令が止まってしまうことがありスピードアップの障害となっていた。最後3日ほどはハードウェア係がgitに修正版を上げながら他の修正を試し、手が空いているソフトウェア係がpullしてVivado上でbitstreamを生成、共有しながら実行結果を実機で記録する分業体制でデバッグを行っていた。
最終発表会（3/4）
8スレッド並列+ノンブロッキングキャッシュやマルチコアなどの合成は通っていたが、いずれもminrtが途中で止まってしまう問題は当日まで解消しなかった。デバッグに対しほぼ何も貢献できなかったのが非常にもどかしかった。
発表会直前、動くバージョンの周波数を引き上げることで時間を短縮できるとのことで急いで最終版のbitstreamを生成し始める。Vivadoの実行中に最終発表会の開始時刻となり、なお悪いことに発表順の抽選では2番手を引き当ててしまった。時刻は13:42、1番手の発表も終盤に差し掛かるころFPUメモリ係より合成完了したbitstreamが届き、焦りが大きくなる中RESETボタンを押し実行させる。プログレスバーが着々と進み100％を指し、diffもないことが確認できひとまず安心。あとは発表するだけの状態まで持ち込めた。
最終的な実行時間は256×256で62.8秒、128×128で19.2秒であった。1位の班が256×256で32秒と圧倒的な記録を出していたのには度肝を抜かれたが、それでも辛くも2位を守り抜けた。作っていたものの全てが動かなかったなど悔いは残ったものの、何よりも班として新規性を残せたのは良かったのだろうと思う。
最終結果
256×256のminrtに対し、
- 命令数: 29.9 億 （全体2位）
- 実行時間: 62.8秒 （全体2位）
- 動作周波数 : 78.336MHz
- シミュレーター実行時間: 170.6秒 （全体3位）
128×128の命令数が9.21億で、歴代を通しても1つの壁である10億命令を破っています。これが今年は2つあったというのだから恐ろしい。 シミュレーターはマルチスレッドの待ち合わせの実装方法がよくなかったせいで若干遅くなってしまいました。設計ミスですね。
感想
班全体としては、FPGAボードがナーフされて以降の環境でノンブロッキングキャッシュを用いたOoO処理やマルチスレッド実行、メモリアクセス解析・ラフなシンボリック実行による自動並列化機構と大きめの新規性を生み出せたという点でとても良かったと思っています。自分も何か新規性を発表したかった...... (JITやAoT実行は21erでやっているところがあったらしいので、仮に完成していても新規性にはなりませんでした。残念！)
初動でシミュレーターを大急ぎで完成させ、そこから2ヶ月ほどは完全にコンパイラの支援に回ったのは正解だったと思っています。コンパイラが一刻も早く完動すれば、その分最適化にしっかり時間を使っていただくことができます。コンパイラ+シミュレーターのデバッグを行う際は、どちらが間違っているのかを切り分けながら二人三脚で進むことになるので仕様の伝達ミスなどもここで明らかになることが多かった印象です。
サイクルアキュレートなシミュレートを行うべきかに関しては、個人的には結構疑問に思っています。組み始めの時点では役に立つ場面も多そうですが、ある程度ステージが進むと速度を犠牲にすることになるので使われなくなっていくことが多いように思えます。そもそもVivadoのシミュレーションで波形を見られるのが大きそう。バグが起きてそうな場所を切り出してVivadoのシミュレーションに読み込ませやすくする、のようなことができるのが理想だと思います。積極的にハード側のデバッグも援助できると良いと思います。
シミュの高速化Tips
速くないと使い物にならない！ 序盤は命令の正しさや実行の流れの正しさを保証するように安全側に倒し、コンパイラが動くようになって来たら少しずつ速度重視に倒していくとよいかもしれません。
前計算できるものは前計算する
jumpの飛び先や実行する命令の中身など、予め計算できるものを先にやっておくことは重要です。また、FPUのinv/sqrtテーブルはstatic変数で1度だけ作ってあとは再利用、というようにすることもできます。
コピーコンストラクタ・デフォルトコンストラクタに注意
ループの中でstructやclass を宣言すると毎回コンストラクタが呼ばれて遅いです。これを無くしただけで2倍速くなったこともあります。
重いオブジェクトは参照渡しを使う
上とほぼ同じです。一方でintなど軽いオブジェクトはコピーの方が安くつくらしいです。
JIT化 (最終手段)
コンパイラ実験の課題を1つ提出できます。
参考書籍
これの付録にパイプラインプロセッサのVerilog実装例が載っているとのことです。（我々の班は書いてから投げ捨てましたが......）
- Hisa Ando『高性能コンピュータ技術の基礎』（毎日コミュニケーションズ）
絶版になってしまいましたが、Kindleにあります。工学部図書館にもあります。 スーパースカラ、OoO、分岐予測、マルチコアなどをやる場合は読むとよいかもしれません。
- Takenobu Tani『プログラマーのためのCPU入門 : CPUは如何にしてソフトウェアを高速に実行するか』（ラムダノート）
実装が書いてあるわけではないので、現代CPUが何をやっているか知りたい人向けです。マルチプロセッサは授業で深く扱わなかったので、この辺りの話を知るにはよい本です。キャッシュコヒーレンシーなどの勉強にもなります。
おわりに
未来のCPU実験ではOoOと並列化と自動並列化機構が標準搭載になっていたらどうしよう
