CPU実験振り返り(シミュレータ・FPU係目線)

先日CPU実験の最終発表会が終わりました。この記事では、シミュレータ・FPU係目線で振り返りをしていこうと思います。CPU実験開始前にシミュレータ・FPU係について調べたところ、あまりにも情報がなくて困ったので、後輩の参考になればという意味もあります。同輩のシミュレータ係であるCFkazuくんがCPU実験途中で書いた記事もよければ参考にしてみてください(彼は僕より優秀なので、参考になる点も多いと思います)。

ちなみに、この記事は2020年度までのCPU実験の内容です。2021年度からは内容が変わるとの噂もあるので、その点はご了承ください。

CPU実験とは

CPU実験は東京大学理学部情報科学科において、3年生後期で行われる実験です。3人ないし4人(この辺りは年によっても違います)で班を組み(ランダム)、CPUを作ります。具体的には、コア・コンパイラ・アセンブラ・シミュレータ・FPUを作ります。コア・コンパイラ・シミュレータ・FPUはその係の人が担当し、アセンブラは手が空いている人が作る感じです(ただ、この辺りも年によって違ったりします。FPU係がない年もありました)。僕はシミュレータ・FPU係で、20erの中では唯一の兼任でした(一般的にシミュレータ・FPU係は仕事が軽いとされていて、そのため2係兼任が可能でした。人数調整のためたまたま当たった感じです)。

システムの説明はさておいて、軽く内容を説明します。この辺りはどのブログでも書かれていることなので、既知の方は読み飛ばしていただいて構いません。CPU実験では、min-camlという言語で書かれたレイトレーシングプログラムをコンパイルし、アセンブルし、FPGA上にプログラムしたコア上で実行することが目標です。アセンブルした機械語はコア上にプログラムするのですが、引数はFPGAに接続したPCからUART通信で送ります。返り値もまたUART通信で送り返します。そのようにして、こういう車の画像が出たらめでたしめでたしというわけです。

有名なやつ

では、実際にシミュレータ係・FPU係の仕事について説明します。コア係・コンパイラ係についてはすでに記事がたくさん転がっていますから、それを見てもらうのが良いでしょう。(19erのコア係の方の記事 / コンパイラ係の方の記事)

シミュレータ係

シミュレータ係はコアの動作を模擬するプログラムを書きます。といっても、どこまで精密にシミュレートするかはコア係からの要望次第と言ったところです。一番頑張るなら、エミュレータという形で完全にコアと同じ動きをするプログラムを書くことになります(これはかなり大変です。なぜなら、コアを記述する言語はクロックごとに全てが同時に動きますが、C++などの言語は逐次実行だからです)。普通は、1命令読み込んで実行するというインタプリタ的なプログラムを書くことが多いと思います。

また、当然模擬するだけでは意味がないので、コア係がデバッグするための機能をたくさんつけます。例えばそれはステップ実行だったり、レジスタ出力機能だったりします。この辺りはコア・コンパイラ係との相談で決めていくことになります。

言語は自由ですが、基本的には高速であることが求められるので、C・C++・Rustあたりが主流だと思います。ちなみに、自分は爆遅シミュレータを書いて班員に迷惑をかけました。(コロナのせいで、他班のシミュレータの速度がわからなかったために、遅いことすら気づかなかった...)

他には、アセンブリを入力とするか機械語を入力とするかの選択肢があります。前者はラベルなどの情報を活かせるため人間に見やすいですが、パースなどの手間が必要なために動作が遅いという欠点があります。後者はその裏返しの利点・欠点があります。どちらを使うかは好み次第です。

ちなみに、一般にシミュレータ係はアセンブラの実装も任されることが多いです(僕は2係兼任だったので、コンパイラ係に書いてもらいました...)。その場合は機械語の仕様をしっかり認識する必要があるので、機械語入力のシミュレータを書きやすくなるかもしれません(知らんけど)。

FPU係

FPU係はFPU (Floating Point Unit、浮動小数点（演算処理）装置) をハードウェア記述言語で書きます。パッと見コア係の仕事っぽいですが、多分コア係に割り振ると負担が重すぎるということで分けられたのでしょう。年によってはこの係はなかったりします。実際、この係が一番楽だと思います。

FPUとは、具体的にはfadd, fsub, fmul, fdiv, etc...といった浮動小数点数の演算を行うモジュールです。FPU係の仕事はこれらのモジュールを書いてコア係に渡すことです。どういうモジュールを書くかは班内で相談して決めることになります。というのも、最低限のモジュールがあればその他はそれらの組み合わせで実現できるからです。すなわちコンパイラ係にお願いして、ソフトウェア実装という形を取ってもらうこともできるということです。実際、サイン関数などは多く(全て？)の班がソフトウェア実装で済ませてしまいます。

ソフトウェア実装とハードウェア実装はどう違うのでしょうか。単純には、ソフトウェア実装は実装が簡単で、遅いです。ハードウェア実装は実装が大変で、早いです。すなわち、高速化の観点から言えばハードウェア実装の方が良いということです。にも関わらず、例えばサイン関数は全ての班がソフトウェア実装をします。理由は簡単で、手間の割にあまりにも効果が薄いからです。サイン関数などはそもそも呼び出し回数が少ないので、ハードウェア実装してもほとんど高速化に寄与しないということになります。このような事情があるので、何をソフトウェア実装し、何をハードウェア実装するかは各班で話し合うことになります。

結果

さて、係の説明が終わったところで自分の班の結果を簡単に述べたいと思います。自分の班ではVLIWプロセッサを作り、180MHz・14.8億命令(VLIW割り当て後は10.3億命令)で動かして11.015秒という記録を出しました。20erの中では1位の記録です。やったね。

ちなみに、歴代は2016年のマルチコアプロセッサで出された4.66秒です。意味がわかりませんね。一応その年はFPUにIPコアを使って良いという条件だったらしいですが、それを加味しても意味わからないと思います。その班のブログはこちらです。よければ読んでみてください。

やったこと

では、ここからはやったことを時系列順に簡単に説明したいと思います。

9月末 班決め & 顔合わせ

まず、初回の授業で班決め・顔合わせをしました。例年だと係決めは全員で集まって空気を読みながらやるらしいですが、今年はコロナの影響もあり、事前にオンラインで希望調査がありました(その結果、コンパイラ係希望が無限に増殖していました)。そして、初回授業ではその希望をもとに抽選で班が決定していました。ここで自分の2係兼任が決定したわけです。先生に「大丈夫？」と言われたことを覚えています(「まあなんとか...」的なことを言った記憶があります)。

その後、班員で顔合わせをして最初に線表(予定表)とISAを決めます。線表と言っても、今後のことがわかるわけもないので「いついつまでに1stコアが動いたらいいなあ」程度のものです。ISAについては、自分たちの班はMIPSベースで進めることにしました。最初の1週間はその程度で終了です(ちなみに、他班にオレオレISAを1週間でガチガチに固めてきた人がいてビビりました)。

~10月下旬 フィボナッチ用コアの開発

そうして開発が始まるわけですが、すぐに1stコアに取り掛かるわけではありません。まずは規模の小さいコアから始めるということで、引数を与えてフィボナッチ数を計算するコアを作ることにしました(以下フィボナッチコアと呼びます)。フィボナッチコアはFPUが不要なので、自分はシミュレータの制作にとりあえず着手しました。これは1週間程度で書けたっぽいです。そのあとは暇だったので、FPUを書いていました。faddは3Sのハードウェア実験で書いたものがあったので、fmul・finv辺りを書いて暇をつぶしていました。

班員はというと、まずコア係が夏休み中にパタヘネを読んでフィボナッチコアを実装していたという猛者だったので、コアはすぐにできました。その後コンパイラも動き、10月下旬ごろにフィボナッチコアが完動しました。

~11月末 1stコア開発

フィボナッチコアが完動したということで、いよいよ1stコアの開発に着手することになりました。まずはISAの決定ですが、これはコア係に任せました。ちなみに、ISAですが、以下のようなフォーマットでシートなどにまとめると見やすいです。

例: フィボナッチコアのISA

11月初旬: シミュレータ拡張 & FPU完成

ISAが決まったので、残りのFPUを書いてシミュレータを拡張しました。FPUについては、シミュレータ係を兼任していることもあったので、1st時点ではソフトウェア実装を多めにしてもらって負担軽減してもらいました(ftoi, itof, floorをソフトウェア実装してもらった)。

11月中旬: シミュレータ & コンパイラ 無限デバッグ編

1週間くらい暇だなあってゴロゴロしてたら、11月中旬にコンパイラ係からレイトレのアセンブリが飛んできました。これが地獄の始まりで、1週間アホほどデバッグしていました。ちなみに、このデバッグはシミュレータ係がやった方が良いです。なぜなら、コンパイラのバグかシミュレータのバグかの見分けがつかないからです。僕も例に漏れずたくさんバグを埋め込んでいたので、血反吐を吐きながらデバッグしました。最終的にはアセンブリ1万行を5時間くらい眺めてバグを取りました。これにより、11月下旬くらいにシミュレータ上でレイトレが動きました。

11月下旬: 1stコア 無限デバッグ編

喜びも束の間、次はコアのデバッグが始まります。ということで、その後すぐにコアのデバッグの応援係に就任しました。コアのデバッグはメンタルを病んでしまうので、応援する人が必要です。半分冗談ですが、半分マジなので、コア係は労ってあげましょう。精神面以外でも、岡目八目という言葉があるように、外野が俯瞰して見ることでバグがすんなり見つかることもあります。わからないと言ってコア係のみに投げるのはやめて、デバッグを手伝ってあげましょう。

11月末: 感動の完動編

そうして無限デバッグ編を乗り越えると、ついに感動(完動)の瞬間が訪れます。このときはさすがに班員みんなでzoomを繋いで喜びを分かち合いました。この時に飲んだビールはとても美味しかったです(小並感)。

ちなみに、この時点では58.7億命令・348.3秒でした。20er内では最速完動で、これも気持ちよかったです。

~12月末 パイプラインコア開発

ということで単位が確保できたので、ここからは高速化フェーズです。ひとまずパイプラインにすることを決め、2nd ISAを相談しました。

2nd ISAが決まったので、ひとまずシミュレータを拡張しました。そして1stでソフトウェア実装していたFPUをハードウェア実装しました。ここまでで12月中旬くらいになったので、次はパイプラインコアの動作をエミュレートするシミュレータを作ることにしました。

12月3週目: パイプラインコア完動(????????)

そうしている間に、コア係がパイプラインコアを完動させちゃったとの連絡が入ります。なお、パイプラインシミュレータはこの時点でできていません。なんで？？？

また、他班の報告によりmin-camlコンパイラに元々備わっているインライン展開がすごいことが発覚し、コンパイラにも革命が起きました。これにより、一気に命令数が半分以下になります。

そうして動いたパイプラインコアは21.2億命令・36.73秒でした。すごすぎる。自分なんもやってないが...... パイプラインコアを完動させたのは最速タイでした。

12月末: パイプラインシミュレータ完動

焦ったので、一足遅れてパイプラインシミュレータをなんとか完動させました。ちなみに、これが本当にありえないくらい遅くて、その後一度も使うことがありませんでした。(悲しいね)

悲しいので多少弁解すると、アウトオブオーダー実行を実装する暁にはその機構をこのシミュレータに実装し、このシミュレータをメインにする予定でした。インオーダー実行の範疇では、マルチサイクルもパイプラインも途中状態にそこまで差がなかったので、どちらでも良かったようです。そして、アウトオブオーダーを実装する日はついぞきませんでした......

~1月末 無限試験・レポート編

このあと今後の方針を話し合って、VLIW(Very Long Instruction Word)プロセッサを実装することにしました。VLIWの詳しい説明はWikipedia等に譲りますが、簡単にはn命令を一気に実行できるプロセッサです(おそらくn=4が主流?)。つまり、理想的にはn倍早くなります。すごいですね。まあ、現実は厳しいものですが......(結果を見れば分かる通り、1.4倍にしかなっていません)。

それはともかく、1月になると試験と期末課題が襲いかかってきたので、開発は一旦中断されました。余談ですが、2係兼任した状態でも出された課題はほとんど消化できたので、他の授業が破滅するということはないはずです。

~発表会 最後の追い込み

1月末: 雑務

1月末に試験が全部終わったので、ここから最後の追い込みに入りました。シミュレータ係としては特に全面的に何か書き換えるということはなかったので、ひとまずFPUを最適化しました。他には、シミュレータを使って様々な分岐予測器を実装したときの見込み正解率を調べたりしていました。

2月1週目: VLIWの検討

2月頭くらいに班内でミーティングをして方針を固めました。VLIWはコンパイラ側が並列性を抽出してあげる必要があるのですが、コンパイラ係は他の最適化が忙しそうだったので、並列性抽出を僕が担当することにしました。これについてはすぐに書けたので、コア係に渡してデバッグフェーズに入りました。

2月2週目: 周波数向上の試み

程なくしてVLIWプロセッサが動いたとのことだったので、周波数を向上させるフェーズに入りました。この段階になってやっとFPUをクロック分割しました。仕事が遅くてコア係に迷惑をかけちゃったので反省しています。このクロック分割やコア係の努力が功を奏して、190MHz・12.67秒まで性能が向上しました。これが発表会3日前です。

ちなみに、その他の時間は暇だったのでいろんな調べ物をしていました。そしてコア係・コンパイラ係に対して、良く言えば最適化の要望 / 悪く言えばイチャモンをつけていました。暇人が頑張ってる人に口を出すの、最悪の構図って感じだ...

発表会2日前: バグの発覚

ここまではパイプライン終了時と同じコードでコアを動かしていたのですが、コンパイラ係の最適化がひと段落したので、コードを差し替えることにしました。しかし、コードを差し替えたら動かないことが発覚します。これが発表会2日前の夜のことです。コア係はそこから原因追及すべくアマゾンの奥地ならぬvivadoの奥地に踏み込むわけですが、そこでvivadoのシミュレータが謎のバグにより使い物にならなくなりました。ヤバいですね。どれくらいヤバいかというと、調査のためにアマゾンの奥地に入ったらコンパスがバグって方角が分からなくなるくらいヤバいです。そもそも、vivadoのせいであることに気づくために5時間くらい費やしたのもこの世の終わりって感じでした。その日はそこまでで寝ました。

発表会1日前: 修羅場

vivadoのシミュレータが使えなくなってしまったので、実機デバッグをせざるを得ません。唯一の暇人である僕も協力してバグを大捜索することになりました。これは発表会当日の0時くらいまでかかりました。ギリギリすぎる...... なんとか原因を突き止めたので(普通にコアがバグっていた)、一命を取り止めました。

発表会当日: 悪あがき

とりあえずまた動くようになったので、ここからは0.01秒でも早くなるように悪あがきをしました。とりあえず周波数を上げて、一番最適化の効いたコードを用いることで11.015秒まで持ってくることができました。ちなみに、我が班のコアは1回の合成に40分かかる激ヤバコアだったので、いろいろな組み合わせを試すだけで朝になっていました。

ここからは本当の悪あがきとして、1MHzでも早くならないか、1命令でも少なくならないかと血眼になってアセンブリを眺めていました。しかし、数時間でバグなく実装できるような改善案には思い至らず、ここで力尽きました...... 12秒台まではすぐに至ったこともあり、なんとか10秒切れないかと試行錯誤したのですが、なかなか記録が伸びず高速化の難しさを痛感しました。悔しい。

発表会

発表会において「VLIWの並列度が上がらなかった」話をすると、先生から述語付き命令(Predicated Instruction)の存在を教えてもらいました。たらればですが、これを知っていたら10秒切りも見えたかもしれないと思うと己の知識不足が悔やまれます。

ただ、結果1位だったのでそれは素直に嬉しかったです。発表会までは「もう少し何かできたんじゃないか」と悔いが残る気持ちもあったのですが、結果でかなり報われた感じがしました。

やってよかったこと

週1での班ミーティング

コロナもあり、例年のように対面でいつでも会えるというわけではなかったので、まず最初に週1で班ミーティングを行うように決めました。ミーティング内では、進捗報告・次にやること・期限などを明確にするようにしました。特に、コア・コンパイラ係は自分の最適化で手一杯のことが多いので、その辺りは暇人である自分がなるべく担当するようにしました。

google docsでの議事録

上の班ミーティングで決まったことはまとめて議事録につけるようにしました。また、班のslackがあったのですが、slackに流れた大切な情報は議事録にも書くようにしました。

他の係への質問

分からないこととか、不思議に思ったことはなんでも聞くようにしていました。分かっているつもりのことでも、認識に齟齬があると大事故に繋がりかねません。聞いて言語化できたものは上の議事録に書くようにしていました。特に、これは最初の方に是非やるべきだと思います(お互い手探りで進めることになるので)。

やったほうが良かったこと

ISAの検討作業

1月末あたりにVLIWプロセッサの開発が始まった時、なあなあでパイプラインのISAを流用したのですが、ここでISAの再検討を行うべきでした。あまり時間が取れなかった時期ではあったのですが、そういう発想すら出なかったのは反省点の1つです。

コアの設計検討

コアの設計についてはコア係に一任し、自分はコア係から流れてきた仕様を言われるがままに実装していたのですが、これももう少し自分でも調べるべきだったかなあという気持ちがあります。別にコア係の設計が悪かったわけじゃないけど、いろんな視点があったほうが大概のものはよくできるので......

シミュレータ係に向いている人

これはCFkazuくんのブログにも書いていることですが、やはり「暇な人」ということに尽きると思います。より具体的には、レスポンスの速い人です。コア・コンパイラ係の要望にどれだけ早く答えられるかで開発スピードが大きく変わると言っても過言ではないです。シミュレータ係の大半はシミュレータを書くことではなく便利屋的な仕事なので、その辺りがめんどくさい人はあまり向いてないかもしれません。(まあ、一応シミュレータ書いてコア係に投げれば最低限の仕事は終わりなんですが。)

FPU係に向いている人

FPU係は、CPU実験にそこまで熱意がない人に割とお勧めできます。楽なので。便利屋みたいな仕事もないので、ちゃちゃっと書いてしまえばそれだけで終わりです。まあ、暇そうにしてたら雑用が飛んでくるかもしれませんが......

あとは、コア触ってみたいけどコア係は荷が重いって人はFPU係になってコア係のお手伝いに就職するという手もあると思います。実際、2ndコアはFPU係が書いたという班もありました。

感想

コア係もコンパイラ係も荷が重かったために逃げるようにシミュレータ係を志望したのですが、班員に恵まれて充実したCPU実験になり、良かったです(コア係もコンパイラ係もかなりバケモノだったので、ついていくだけでここまで来れたみたいなところがあります)。たったの3人ですが、プロジェクト開発的なことも経験できて面白かったです。

2係兼任・3人班については、そこまで大変じゃないと思います。それぞれの係の(コア・コンパイラ係と比較した)相対的仕事量の少なさもそうですが、FPU係とシミュレータ係の稼働時期が大きく被らないのも大きいです。3人班は連絡が取りやすいのでむしろアドって感じでした。

なんか書き始めたらいつの間にかめっちゃ長くなっちゃったんですが、ここまでお読みいただいた方はありがとうございました。何かの参考になれば幸いです。後輩(特に21er)がバケモノコアを作ってくれるのを楽しみにして、筆を置きたいと思います。それでは。