計算機科学実験及演習3ハードウェア（CPU製作）記

先日、長いようで短かった実験がついに終わったので記録を残しておきます。

はじめに

京都大学情報学科の計算機科学コースでは計算機科学実験及演習（以下、実験）という必修科目が 2 回生前期 / 後期、 3 回生前期 / 後期の計 4 つあります。

実験 1 はプログラミングの入門みたいな内容
実験 2 はマリオ AI の作成と電子回路
実験 3 は CPU 製作とインタプリタ製作
実験 4 はいくつかの分野から選択

という感じです。

僕たち 2015 年入学の学生から実験の内容が少し変わったのですが、実験 3 の CPU 製作は昔からあるみたいです。

CPU を製作する学生実験といえば某大学某学科の CPU 実験が有名で知っている人も多いと思います。

CPU 実験でググるとすごい人の製作記がたくさん出てきて面白いのですが、いまググるとこの記事が霞んで見えるので読み終わってから調べてください（参考文献にいくつか並べてあります）

あちらの実験は有名なのに、実験 3 の記事は（調べ方が悪いのか）調べてもあまり出てきません。

これではあまりにも寂しいし、僕自身実験をはじめる前に製作記みたいなのを読みたかったので後輩のためにも少しがんばって書くことにしました。

実験について

実験 3 （ハードウェア）では二人がかりで FPGA を使って CPU を製作します。

期限は二ヶ月弱。今年は初回授業が 4/13 で、デモが 6/2 でした。

実験の時間は毎週木曜 3 限から 5 限と金曜 1 限から 5 限までの 8 コマ（毎週 12 時間）です。めちゃくちゃ長い。

しかも 4 分の 1 以上休むと単位がもらえないというスパルタぶりです。

作るアーキテクチャについては SIMPLE という 16 ビットアーキテクチャが提示されて、これに準拠したものを作ります。

準拠するといっても改良するのはアリで、どこまで変えていいのか聞いてみたところ面白ければなんでもいいらしいのでほぼ自由です。

ただし、レジスタ幅/データバス幅は 16 ビットでないとダメです。この制約が割と辛いので注意してください。32 ビットアーキテクチャにするくらいなら許してほしいところです。

この制約はソートコンテストで SIMD の幅増やす勝負とかにならないようにするためだそうです（それはそれで面白そうですが）

ソートコンテストというのは、製作した CPU 上で 1024 個の 16bit の符号付き整数をソートする速度を競うコンテストのことです。

必須参加ではありませんが、だいたいこのコンテストに参加して上位を狙うのを目標にする班が多いようです。

とりあえず一通り説明したので、これからは日記形式でやったことを説明していきます。

日記

4/13

実験初日です。

ハードウェアにはめちゃくちゃ苦手意識があるので気が重かったです。

初週はまだ CPU を作らないようで、HDL の説明を軽くされたあと、導入課題として個人で 10 進カウンタを作って 7 セグ LED に表示するというものが出ました。

カウンタ自体はそう難しくないんですが、 LED への出力の仕様がよく分からずハマりました。

こういうハードウェア部分でハマって、マニュアルを見ても分からないときは早めに TA に相談するのが良いと思います。

LED さえ満足に光らせられない我々は果たして 7 週間で CPU を作ることができるんでしょうか
— 紫乃さん (@joisino_) 2017年4月13日

▲ハードウェア難しすぎて絶望する joisino 氏

4/14

まだカウンタが終わらないので作り続けます。

昼になった時点で CPU 製作の班分けが発表されました。

僕のペアは kmcyuma くんでした。

KMC の競技プログラミング勢ということで、気心が知れて、プログラミングがとてもできる人なので助かりました。

ペアはたいへん重要なのですが、自分たちで選べる訳ではなく、指定されます。

これから実験 3 に挑む人は良い人と当たるために春休みのうちに徳を積んでおきましょう。

午後は、SIMPLE アーキテクチャの説明と git の使い方説明会がありました。

今年は全員 HDL(Verilog HDL か VHDL) で CPU を作ることになったのですが、去年までは HDL で作る班と CAD でポチポチ配線する班があったそうです。

CAD で CPU 配線するの激ヤバだと思うんですが、今年は全員 HDL ということで良かったです。

僕は Verilog HDL よりも System Verilog の方が良かったのでそれでもいいかと聞いたら OK が来たので System Verilog で作ることにしました。

なんとかこの日のうちにカウンタを作り終えて、レポートを書き終わるところまでたどり着きました。

レポート部分が意外と重いので注意してください。

最後の 1 時間くらいは相方と今後の CPU 製作について打ち合わせしました。

だいたい次のようなことを相談しました。

相方はシミュレータとアセンブラとソートプログラムを作る。
僕は CPU を作る。
とりあえず来週くらいには単位コアを作って精神を安定させる。
単位コアはすぐに捨てていい感じのコアをつくりはじめる。
さすがにパイプライン化はしたい。
OoO とかスーパースカラ化もできればやりたい。
ソートコンテストで 1 位になるのを目標にする。

4/18

CPU が完成しました。

製作パートどこいったんだよ製作記じゃなかったのかよという感じですが僕自身もビックリするくらいすぐ完成してしまいました。

マイクロアーキテクチャの図を見ながら、ひとつずつ部品を作って配線していくと出来上がります（それはそう）

コアを作る上でオススメなのは

SIMPLE/B というマイクロアーキテクチャが参考に上がっていますが、あれよりもパタヘネに載ってるやつのほうが慣れてて書きやすいです（これは人によりそう）
コンパイルに 2 分くらいかかってつらいですが、Modelsim での RTL レベルのシミュレーションなら 1 秒くらいでコンパイル終わるのでこちらでバリバリデバッグして、最後にタイミングの確認とかの段階になって論理合成するのが良いです。
機能を増やすにつれてどこに何があるのか混乱してくるので、コアの全体図を描いておくとわかりやすいです。
テスト用にいろいろな難易度のプログラムを書いておくと良いです。僕たちの班は入力をそのまま出力に返す、演算して出力する、1 から 10 までの和をループで求める、フィボナッチ数列の 10 番目を再帰で求める、バブルソートをするなどをテスト用に書いて、ハードがバグったら簡単なものからどこまで通るかを確認してバグ箇所を特定したりしていました。

特にふたつ目は生産性爆上がりなので、ぜひ実行してみてください。

ちなみにアセンブラとソートプログラムも相方がまだ作っていなかったので僕が作ってしまいました。

愚直なクイックソートで 4.96ms でした。

CPU完動しました🎉🎉じょいしの先生の次回作にご期待ください（第一部・完）
— 紫乃さん (@joisino_) 2017年4月20日

▲完動を喜ぶ joisino 氏

4/20

5 段パイプライン化しました。

パタヘネに有名な文言「誤信: パイプライン化は容易である」というのがありますが、意外とすんなりパイプライン化できました。

ここで特にパタヘネのマイクロアーキテクチャを参考にしたのが効いてきたのだと思います。

SIMPLE/B ベースでパイプライン化しようとするとハザード検出を自分で考えることになるのでバグらせやすいですが、パタヘネのマイクロアーキテクチャは本に書いてある上に講義でもパイプライン化の手順をやったはずなので、手際よくできるはずです。

フォワーディングを実装して、この日にソートコンテストに一度目の提出をしました。1.451ms でした。

4/21

そろそろ単位コアを捨てて新しいコアを作り始めてもよかったのですが、相方と話し合った結果、このままでも歴代最速を更新できるんじゃないかという気がしてきたのでもう少し作り続けようという結論になりました。

ちなみに歴代最速は 2012 年度の 4 コアプロセッサで 0.3680ms です。

4/23

分岐予測を実装、クロックを上げる、Jump And Link 命令すらなかったので追加するなどなどを行って歴代最速を更新しました。

小さい時は挿入ソートにする & ピボット選択をがんばるクイックソートで 0.3650ms です。（これは提出していません）

もうこれ以上の高速化は限界っぽかったのでマルチコアにしようかということになってきました。

そういえば、このあたりは他の講義中もずっと CPU 作っていて、そのせいか週 3 くらいで CPU を作る夢を見ていた記憶があります。

特に CPU の配線を全て手作業で行わされる悪夢にうなされたのが印象に残っています。

4/27

基数ソート + 挿入ソートを書いて 0.1916 ms で提出しました。

アルゴリズムの変更でここまで速くなるのはアルゴリズムの勝利という感じがして嬉しかったですね。

実験3のCPUですが、歴代最速記録を大幅更新しました(368us->192us)🎉🎉🎉🎉
— 紫乃さん (@joisino_) 2017年4月27日

▲twitter で自慢する joisino 氏

4/28

8 コアプロセッサが動いて 0.05040ms で提出しました。

8コアプロセッサが動いてさらに4倍記録更新しました(50.4us)🎉🎉🎉🎉🎉🎉🎉🎉
— 紫乃さん (@joisino_) 2017年4月28日

▲記録の更新に浮かれる joisino 氏

結果的にこれがソートコンテストの最終提出になりました。

正直 4 月中にマルチコアが動くと思ってなかったので動いた時はめっちゃ嬉しかったです。

俺は 2 週間でマルチコアプロセッサを作ったぞってあと 10 年くらいは自慢するかもしれませんが聞き流してもらって構いません。

ちなみにメモリとかタイミング制約を限界まで取って 8 コアでコンパイルすると論理合成に 1 時間くらいかかって絶望するのでそこそこで我慢しましょう。6 割にするだけで 5 分くらいになります。

マルチコアですが、ソートコンテストが動く最低限の同期だけ実装したものならそこまでヤバくはありません。

僕の班でも、8 つのコアはほとんど独立で、メモリだけ共有しています。

動作するために特別やったことといえば、メモリの排他制御が必要なのでセマフォ入れたぐらいです。

あとは高速化のためにメモリアクセス権のプライオリティをクロックごとにコアに順番に割り当てていくことと、メモリの 2 ポート化（読み込み 1 / 書き込み 1）をしました。

ソートコンテストでは要素数 1024 個の配列をソートするのですが、ハードウェアの制約上メモリは 2 ポートまでしか実現できず、クロック数も 250 MHz が上限（といっても CPU を 250 MHz で動かすのは至難の業ですが）なので、仮に値の収納先がわかって毎クロック値を読み込み / 書き込みを行ったとしても 1024 / 250 MHz = 0.0041 ms くらいはかかります。

相当無理をした仮定でも 13 分の 1 くらいにしかならないことを考えるとこれ以上の本質的な高速化は厳しいという結論になり、これからはソートコンテスト以外の道を模索することになりました。（後から思うと、僕たちの CPU は 90MHz なので、パイプライン段数を増やしてクロックを上げればまだ高速化はできたと思います。）

ところで少し話は変わりますが、この実験では中間レポートというものがあり、我が班は非常に焦っていました。

というも、実験の評価項目では分担がうまくできているかが重視されているのですが、ここまで CPU は全て僕が作ってしまっていました。

ということで、この日に急遽相方に CPU の仕組みと System Verilog を教えて、細かい部品を作ってもらうことにしました。

4/29

ゴールデンウィークですが、コンパイラを作れたらなぁと思って LLVM のドキュメントを眺めたりしつつ遊んでいました。

あとゴールデンウィーク中にちょくちょくレポートを書きましたがかなり分量が多いので気をつけてください。

5/6

LLVM バックエンド難しすぎて挫折する。

5/7

とりあえず flex + bison で温かみのある昔ながらのコンパイラを作ることにしました。

ソースは C サブセットにするつもりだったのですが厳密にサブセットにするのは面倒だったので C サブセットっぽい何かになってしまいました。

この日は演算命令をコンパイルするくらいを実装しました。

5/8

コンパイラに比較、if、else、whileあたりを実装しました。

このあたりで気づいたのですが、16 ビットということもありアーキテクチャが弱すぎでコンパイラを作るのが相当大変です。

たとえば、分岐命令は上下 128 命令くらいまでしか飛べないので if 文などでそれ以上飛ぼうと思うと一旦別の場所に飛んでから遠くの場所に飛ぶ必要があります。

ここまではよくあるテクなのですが SIMPLE は即値分岐や即値代入も絶対値 128 くらいまでしか指定できないので困り果てました。

調べてみると MIPS は即値分岐で飛べない場所に行かないように配置するらしいのですが流石に 128 しか飛べないように配置するのでは制限が大きすぎます。

ラベルの x ビット目から y ビット目を表すラベルみたいなのを作って無理やり処理したのですがこういうのはどのように処理するのが正解だったのでしょうか。

あと、この日にようやく相方が作っていたシミュレータがまともに動くようになりました。

もう既に完動してしまっていますが、いちいち波形シミュレータを使うのは面倒すぎるので、このシミュレータはこれからのコンパイラ製作に大いに役立ちました。

5/9

コンパイラに関数呼び出しを実装しました。

5/10

コンパイラに関数の引数や配列を実装しました。

このあたりで以下のフィボナッチ数を求めるプログラム程度ならコンパイルできるようになりました。

gist.github.com

5/11

中間レポートを提出しました。

相方もいい感じにパーツを作ってそれらを CPU に組み込んでなんとか協力した感じを醸し出しました。

5/12

この日は中間デモでした。

完成品を見せるというよりは進捗確認の意味合いが強い感じで、とりあえず 1 命令以上実機で動くことを見せるというものでした。

張り切った僕たちの班はすでにコンパイラの原型までできていたので、ちょっと C プログラムを書いてマンデルブロー集合を出力するデモをしました。

f:id:joisino:20170604175836p:plain
▲誤差がすごいマンデルブロー集合

FPU とかはないので固定小数の掛け算のライブラリを書いて動かしました。

とりあえず山場の中間デモまで終わったので最終デモでやる余興を何にするかという話になりました。

いろいろ考えてはみたのですがハードウェアの制約がかなり厳しいです。

FPGA からなにか使える端子が伸びていてディスプレイでも繋げられたらいろいろやりようがあると思うのですが、残念ながら出力は LED とブザーしかありません。

OS っぽいものを作る案もあったのですが、ハーバードアーキテクチャで作ってしまったのでプログラムの展開をどうするんだという話になって流れてしまいました（後から思うとハーバードでも何かしらは作れたと思うのですが）

とりあえずボードに乗っているハードウェアを最大限使ってテトリスを作ることにしました。

テトリスのプログラムは相方が作って、ハードウェアとコンパイラ方面を僕が作ることにしました。

とりあえず僕は LED の出力周りをいい感じにアーキテクチャから見えるようにしたりしました。

f:id:joisino:20170604175957j:plain
▲実験で使うボード

5/15

コンパイラに for や continue や break などを追加したりしていました。

5/19

ブザーで音楽を鳴らせるようにしました。

音楽部分はプロセッサから独立させてひたすらメモリからデータを読みだして BGM を鳴らし続けるようになっています。

アーキテクチャから見えるようにしたかったのですが、BGM を鳴らすとなるとタイマ割り込みとかが必要になってきそうなので諦めました（これも後から思うと色々やりようはあったと思います）

だいたいテトリスが動くようになりました。

割と大変だったのが、メモリの容量不足です。

実験で使うボードでは 16 キロワードくらいまでしかメモリが入らなくて、データ 8k 命令 8k にしているのですが、コンパイラが最適化をしてないこともあり、普通にテトリスを書くと溢れてしまいました。

なんとか相方に手で命令数を最適化したりしてもらっていました。

5/25

この時点になってもまだソートコンテストの参加者が僕たちだけだったので、まだ完成していない KMC 部員の席に行っては煽ったりしてました（ごめんね）

5/26

タイマーを追加して、リセットからの時間を取得できるようにしました。

他にもいろいろと微調整をしてデモ用のプログラムが完成しました。

さて、このあたりでまたまたレポート問題です。

最終レポートはこれまでのレポートよりも分量が多く、班で提出するレポートが 4 種類と個人で提出するのが 1 種類あります。

なかでもユーザーズマニュアルというのが大変で、「IPコア(ソフトコアプロセッサ)として提供することを想定し、プロセッサを使用するうえで必要十分な情報を記載すること」といういかにも大変そうな注意書きが書かれています。

特に僕たちの班はごちゃごちゃと機能を付け足してしまったので書くことが山盛りです。

そんなわけでこのあたりから実験中はずっとリファクタリングをしながらレポートを書き続ける回になりました。

6/1

デモ前日です。

デモはペアがそれぞれ絶対に喋らないといけないのに、相方はハードウェアの中身については知らないらしいのでいろいろとレクチャーして発表の分担を考えたりしました。

6/2

いよいよデモ当日です。

デモといってもスライドを作ってみんなの前で発表するわけではなく、TA と教員が班席まで回ってきて 10 分くらいプロセッサやプログラムの説明をする感じです。

知り合いの発表は聞きにいったりしていましたが。

テトリスはこんな感じに仕上がりました。

youtu.be

声が入っているので音は入れていませんが、プレイ中はコロブチカが流れます。

あと相方がプレイして僕が撮ってるのですがミスするたびに笑ってカメラを揺らしています。ごめんなさい。

これだけ色々言ったわりには大したことないようなという感じかもしれませんが、とにかくデモが終わった後はようやく終わったという開放感でいっぱいでした。

レポートもこの日のうちになんとか書き終えて提出することができました。

6/4

この記事を書いています。

感想

2 ヶ月弱、つらいことも多かったですが、振り返ってみると全体的に楽しかったと思います。もうやりたくはありませんが。

期間も短く班員も 2 人なのであまり大層なことはできませんが、こんな短期間で CPU 製作を一通り学べるのはものすごく良い経験だと思います。

僕たちの班も最後の方は若干だれてしまったので、全力疾走するにはこの位の期間が限度なのかもしれません。

色々やりたいことの中から、無理だと諦めたものもありましたが、最終的に作れたものには満足しています。

来年以降実験を受ける人たちは僕たちが諦めたものたちも含めて、僕たちの成果物なんかよりもっとすごいものを作ってください。（半分そのために記事を書いているので期待してますよ！）

的を射ているかは分かりませんが若干アドバイスです

OoO とスーパースカラ

- ソートコンテストをやるうちにいつの間にか目標から外れていました。というのは、通常実験ではアセンブリコードを手書きするので、相当のハザードを手で解消できてしまい OoO の恩恵をあまり受けられないというのと、そもそも 8 コア化するとすごい量のメモリアクセスがあってアクセスキュー待ちがボトルネックになるのでこのあたりの高速化テクの意味が無くなってしまったからです。ですが、正直このあたりの技術を実装するのを目標にしている人たちならソートコンテストは無視してもっと大規模なプログラムを目標に据えて、OoO とかスーパースカラを実装していくのがいいと思います。

second architecture

- 僕たちの班も最初は単位コアを作って新しいアーキテクチャに移ろうと考えていたのですが、結局最後まで first を建て増しし続けて終わりました。これについてはどちらが良いとも言えないと思います。もうちょっと実験期間が長ければ有用だと思うのですがなにしろ実験期間が短いので second を作る余裕はあまりありません。second を作ることにするならちゃんとペースを考えたほうが良いと思います。

- OS を作りたいなら最初の設計の段階から決めてかかったほうが良いです。ハーバードで作るよりノイマン型で作ったほうがいろいろやりやすいと思うし、割り込みとかもあんまりすぐに建て増しできる感じではないので最初の設計で考えたほうがよいはずです。たぶんハードウェアに詳しくない人は最初からこのへん考えるのは難しい（少なくとも僕はそうだった）ので、OS 作ったりする場合は second 作るのが有用なのかもしれません。

出力

- ボードに出力が全然ないと言いましたが、唯一出てるリッチな出力がコンフィギュレーション用の USB Blaster です。全く知りませんが、これを使っていい感じにシリアル通信したりできるかもしれません。最後の方になって気づいたのですが結局調べる時間もないまま終わりました。これが使えるならできることが一気に広がると思うので調べてみると良いかもしれません。

レポジトリを置いておきます（剽窃があるといけないので公開しないようにと先生が言っていましたが、頼んだら許可してくれました。来年以降受講する人は絶対に剽窃しないでくださいね。）

github.com

一息つく間もなく来週からはソフトウェア実験がはじまるのでがんばります。