CPU実験おしまい
単位も来たので、CPU実験が完全に終了しました。約27億命令、44.8秒でした。
わたしのコアは https://github.com/grafi-tt/Maizul で公開しています。
流れ
10月前半
コンパイラ係になるつもりでいたけど、じゃんけんで負けてしまい、何となくコア係になってしまう。何をすればいいのか分からないので、試験勉強がてら図書館で借りて少しだけ読んでいたヘネパタ4th editionを買って、まずはひたすら読んでいた。
その後、いきなりパイプラインアーキテクチャを作るという方針でコアの実装を始める。途中まで実装が進んだあたりで命令セットの設計を完全にやり直したりも。
10月後半
コアのテストに必要なので機械語のシミュレータを書く。
SRAMが動かず何度も地下に泊まっては未明の本郷を徘徊しながら悩んだ末に、ついに論理的には初めから正しくてxst（論理合成プログラム、コンパイラのよなもの）のオプションを変更すると動くということを突き止める。これで機械語を手書きしたフィボナッチ数列を計算するプログラムが動作する。
その後、アセンブラを一応動く状態に持っていく。
11月前半
アセンブラとコンパイラを概ね完成させる。
MinCamlのライブラリ関数をアセンブラでひたすら書いたり、FPUの実装やテストなどを行ったり。
このあたりで見えてきた命令セットの微妙なミスを並行して修正する。
11月後半
まずは残ったFPUを実装。マンデルブロ集合をプロットするプログラム（MinCamlに付属）が動く。
コアの実装が解読できなくなってきてこのまま完動させる自信が無かったので、behavioralにデータパスを書き直す。ひたすらコアのデバッグを行い、MinCaml付属のmin-rt.mlが動作する。
そのあとレイトレ向けにコンパイラを修正し、無事11月中に完動。13erでは一番早かった。
12月〜2月前半
しばらくはお茶を濁すように形ばかり作業をしていたが、次第に何も進捗がなくなり進捗発表に行かなくなる。わたしが引きこもっているうちに他の班員が進捗を語っているかもしれないと思っていたが、どうやらそうでもなく一定期間班が消えていたらしい。
とりあえず冬休みに分岐予測だけは実装した。パイプライン実装だと分岐予測の実装はすぐにできると言われるし、実際簡単だと思っていたが、レイテンシの調整が複雑で相当手間取った。データパスの変更が必要だったこともあるけど、今から思うと実装方針が悪かったかもしれない（後述）。
あとは、余興でイーサネットを行うことにする。必要な資材を買い集める。
2月後半〜進捗発表
これまで逆数および平方根は加算と乗算を使ってアセンブラで実装して動かしていたが、VHDLによる実装が出来たとFPU係から報告を受ける。試してみるとほぼそのままで問題なく動く。チームプレイってこういうものなのかとしみじみ喜ぶ。
試しにクロックを上げてみると、少しFPU周りのパイプラインを調節すれば110MHzで安定した。121MHzは動かずあきらめる。
コンパイラ演習で壊れているスケジューリングを実装していたので、動くように直して取り込む。分岐予測も壊れていたので、一応直す。（ただしこのあたりは本当に直っているかあやしい）
また、min-rt.mlの初期化ルーチンの改変は許されているので、実質的にグローバル変数として確保されている配列をアセンブラに移して、MinCamlの上でクロージャが作られないようにしておいた（無論グローバル変数の検出をコンパイラで行うのが本当は正しい）。進捗発表直前に地下でコンパイラ係と二人で作業して何とか間に合わせた。
イーサネットキットは必死こいてハンダ付けしたが、ハンダ付けが完了したあたりで力尽きた。FPGAからの制御方法は一応考えたのだけど……。
感想
CPU実験ではチームプレイを学べるという噂がありますが、わたしに限って言えばあまり学べなかった気がします（反省点があるという意味や向き不向きが分かったという意味で全く学べなかったとは言いませんが）。それよりも、がんばればこのくらい大きなものがこれくらいの期間で実装できるんだなという感覚が学べたように思います。
12erが11月中にほとんど動いていたという話がプレッシャーになって、かなり無理して11月中の完動にこぎつけたところはあります。やる気を喪失したのはその反動もあるとは思いますが、ではどうすればよかったのかと言われると分かりません。祭りのような、それを行うことに何らかの権威的なお墨付きが与えられた上でチームで行う活動に対して、傍から見ているとあんまり関わりたくないと感じるものの、いざ自分がコミットしてみると結構快楽を感じる、そういう性格をしているように思います（もっともこれは多くの人に当てはまる性格かもしれない）。コミットする際に感じるのはあくまで自分の中で閉じた快楽であって、周りの人と心を通わせてた上で何かをすることを楽しいと感じているのかというとそうでは無いような気がします。別にそれ自体が必ずしも悪いことでは無いのですが、ちょっと嫌な面かもしれません。
あとは、わたしはライブラリ関数やテスト用のプログラムをコンパイラが安定してからもMinCamlで書かず全てアセンブラで書いていたのですが、それはやはり自分が設計および実装に携わったことによる慣れや思い入れがあったからのような気がします。そう考えると、自分でコンパイラをフルスクラッチしていれば、MinCaml（を拡張した言語）をもっと書く気になっていたかもしれません。
ご指導頂いたTAや12erの方々に感謝します。班員の方々には勝手に動きすぎたことをやや申し訳なく思うとともに感謝します。13erのみなさん、特に技術面や精神面で多大な支えとなって頂いた @nemunemu3desu に感謝します。またこの文脈で適切かは分からないですが @alpicola には限りなく感謝します。
アドバイス
取り立てて速く動かしたわけではなく何かすごいものを作ったわけでもないのに色々と書くのはおこがましいのですが、まあ思い当たるところを書いておきます。
コア
はじめに断っておきますが、2命令以上の同時発行やアウトオブオーダーに関しては分かりません。他の人を当たってください。
また、ここに書いてあることはいかにもRISCくさいですが、いっそCISCに振りきれるのも楽しいかもしれません。
HDLの書き方
process文はクロックの立ち上がりでレジスタに転送するためだけに用いて、基本的にsignalのみでデータフロー的に書くのが良いという噂をIS周辺で耳にしました。確かにsignalのみを使ってプログラムするのは、VHDLの複雑さと係わらずに済むという意味で分かりやすく、ハードウェアのモデルと近いので論理合成の結果に問題が出にくいのかもしれないとは思います。
しかし、VHDLはデータフロー的なモデリングを行うためだけの言語ではありません。xstはif文やループくらい組み合わせ回路に展開できるし論理圧縮もやってくれます。実際、Web上のHDLプログラミングに関するリソースにも、データフロー的にVHDLを書くことを推奨するような記述は全く見当たりません。signalはコンポーネント間の接続やクロックをまたいで保持する情報などに用いて、ロジックはbehavioralに書けば良いのではないのでしょうか。
といってもやみくもに書こうとすると良い書き方が分からずかなり苦しみました。 @hiyuh さんからtwitterで教えた頂いた A strucutured VHDL design method （スライド）という論文で説明されている、twoprocというデザインパターンが極めて有効な指針でした。
分岐予測
まず、「分岐するかどうかを予測する」方法と「アドレスを予測する」方法があります。後者だと例外の実装がちょっと簡単になり、関数のリターンアドレスの予測も統一できます。前者だと多分回路は少なくて済みます。どっちが良いかはよく知らないですが。
どちらにせよ、「分岐予測の失敗」に対処する必要があります。そのために分岐予測の結果をしばらくの間保持しておくことになるのですが、fetchフェーズあたりの分岐予測ユニットの中で保持する形で書くよりも、executionフェーズあたりの実際の分岐を決めるユニットまで命令と一緒に流す方が、ストールなどの処理が明らかに簡単なはずです。わたしはここで完全にハマりました。
GPR/FPRの分離
データパス周りでの配線遅延を減らすには、データを必要以上にあっちこっちに流さないようにすることが（多分）大事です。とりあえずGPR（汎用レジスタ）とFPR（浮動小数点数レジスタ）は分けた方が賢明らしいです。
さて、わたしのコアでは、ALUとFPUはそれぞれ整数レジスタおよび浮動小数点レジスタのみに書き込むようにはしていましたが、ALUの入力として浮動小数点数を使ってもよく、FPUの入力として整数を使ってもよいような実装となっていました。こうすることで、たしかにFPR/GPR間の移動や浮動小数点数の比較やitofが自然に実装できるようになります。しかし、ALUとFPUの重い命令同士が（例え重い命令ではねじれた入力を必要としなくとも）フォワーディングによってつながってしまうことになり、そのままクリティカルパスとなってしまっていました。ALUの入力は整数のみFPUの入力は浮動小数点数のみにした方がよかったかもしれません（試していないので本当に正しいかは不明。またこの場合は本当に重たい処理が存在しているわけではないので、xstのregiser balancingを有効にすればひょっとしたら解消するかもしれない）。こうすると、GPR/FPR間の移動などは特殊な命令とすることになります。
FPU
基本的にみな「神資料」に従うので没個性なパートです。また、FPUのサイクルを全ての命令で固定するなら3サイクルよりも縮めるのはおそらく相当厳しいので、逆に3サイクルで動かすにはオーバーキルな最適化を余裕がある命令に対して行う必要もあまり無いことになってしまいます。
が、実行サイクルを可変にするなら最適化の余地は存在します。まず、許される範囲で丸めを適当にすれば速くなるかもしれません。加算のレイテンシを根本的に縮めるのに有効そうなのは、 2パス加算器 です。 ヘネパタのAppendix.J には、加算器の数を節約しつつ一回の加算で済ませる方法の記載があります。わたしの faddの実装 は、多分ヘネパタに記載の実装になっているので参考になるかもしれません（ハードウェア実験の際に自力で考えた工夫がたまたま一致していた）。わたしの FPU は全体的にある程度速度を意識しているので、ひょっとしたら参考になるかもしれません。
加算と乗算は最近接偶数丸めをきちんと行う実装があったほうが、三角関数や除算のソフトウェア実装の精度が出るはずなので好ましいかなと思います。あとは、WikipediaやIEEE754の仕様書を参考にしつつ、0の符号の扱いなどに気を付けましょう。
コンパイラ
MinCamlを改造してレイトレを動かすだけなら、基本的に雑用です。出力部を書き換えて、倍精度浮動小数点数を扱うため8byteにしているところを単精度で良いので4byteに書き換えて、ひたすらライブラリを書けば、大体動くはずです。その後の最適化はほとんどやっていないので分かりません。個人的にはMinCamlベースで改善していくよりも、余裕とやる気があるならば、最低限MinCamlベースで動かしたところできりあげて、フルスクラッチしたコンパイラで最適化するなり言語を拡張して遊ぶなりするのが楽しそうです。
スケジューリングだけやりましたが、MinCamlのバックエンドのデータ構造のハンドリングで苦労し、またOCamlの標準ライブラリが貧相で苦労しました。早めに基本ブロック単位の処理などがしやすいようバックエンドに手を入れておくとか、Janeのライブラリを使ってみるとか、すればいいのかなとは感じました。
シミュレータ
シミュレータで一番大切なことは、とにかく確実に命令を動かしてくれること。速度とかデバッグ機能とか、そんなことよりも走らせた結果に嘘が無いことが大切です。
それなりに速く動くようにするなら、まあスクリプト言語で実装するのは止めたほうがよさそうです。大人しく配列を使ってレジスタやメモリを表現すれば、関数型言語で実装してもおそらく速度的な問題は無さそうに思えます。OCamlで実装するなら64bitマシンでないとunboxedなintが31bitしかなくて遅いと語り継がれているようです。
まじめに作るなら、機械語を解釈する部分をCで実装してフロントエンド部を他の言語で作るのが最善かなあと個人的には考えます（高速な高級言語で全部実装するのもアリでしょうが）。たとえばちゃんとデバッグできるようにするなら機械語をアセンブラに変換して出力する機能くらいはまず欲しいですが、それすらCで実装するのは苦痛です。また、一番重要な箇所をCで実装することには「誰でも読み書きできる」というメリットがあります。あんまりかっこよくはないやり方ですが、シミュレータの内部状態はグローバル変数として保持するようにして、「次のブレークポイントあるいはシミュレーション終了まで実行する」関数をCで実装してexternした上でフロントエンドから呼び出しするのが、比較的やりやすいでしょうか（自信は無い）。
Cの実装に関しては、命令デコードのために 2進数リテラルもどき を使うのが便利です。コンパイラの拡張やC++14で2進リテラルが使えますが、環境依存はあんまりよろしくないです。あとは、math.hやstdint.hやinttypes.hは役立ちます（むしろFPUのソフトウェア実装で活躍しますが）。C99は正義。
サイクルアキュムレートシミュレータ（きちんと理解していないけど、多分コアのパイプライン状態までシミュレートするシミュレータ）は、有るに越したことはないと思いますが、下手するとコアをもう一つ作るようなものになってしまうので大変かなとは思います。コアと実装が完全に一致しているかどうかを確かめるのも困難な気がします。「コアの設計としようとしているものが正しいかどうか検証するのによさそう」という話は聞きましたし、それはその通りだとは思いますが、先に書いた理由や、論理的には間違っていない設計でもFPGAでの実装として筋が悪いことはあるという理由から、効果のほどはやや疑問です。ただ、コア係とシミュレータ係の相性が良ければやってみる価値はあると感じます。
アセンブラ
スクリプト言語でちゃらっと実装してしまって動くもののような気もしますが。
代数的データ型がある言語でアセンブラを実装することを考えます。この場合、全ての命令を同じ型にして、コンストラクタで命令を区別するのが自然です。さて、各命令が引数として受け取るのは、GPRやFPRや即値やラベルのてんでバラバラな組み合わせです。こうした状況で、各命令を表すデータが正しい引数を持つということを型レベルで保証するのには、OCamlの多相バリアントが便利でした（もっともこの程度なら、各命令ごとに別々の型を用意してインターフェースやType Classで処理しても良さそう）。
型安全に実装しようとすると、命令を表す文字列をコンストラクタの名前に持ち上げるための[ボイラープレート]()が大量に出来てしまいます。Template Haskellなどでボイラープレートを自動生成するとか、Camlp4などでアセンブラのコードを直接読み込んでしまうとかすれば、ボイラープレートは無くせるかもしれません。
夢
200MHz
SRAMを半分の速度で動かせば理論的には可能ですよね。
ハードウェアレイトレ
min-rt.mlをそのままFPGAで実装すればすごく速そうです。実際FPGAで特定のアプリケーションを実装して高いスループットを得たという論文は見つかります。おそらく深いパイプラインが肝です。
Linux動作
Linux動作のためにやるべきことを考えるのが最終レポート課題（の一つ）でした。
独自アーキテクチャにGCCとLinuxカーネルをポーティングするとか、x86_64を実装してやるとか、まあ面白いのですがLinuxがサポートするシンプルなアーキテクチャ（たとえばMIPS R3000）ベースにするのが無難そうです。当たり前ですがノイマン型（命令とデータをともにSRAMに入れて、BlockRAMはキャッシュとして用いる）になりますし、TLBも必要です。あとは、RS-232C/SDカードをコアから操作できるようにして（デバイスのレジスタを適当なアドレスにマッピング）、特定の組み込みデバイスをターゲットにした既存のドライバのソースコードを参考にしつつドライバを書けば、なんとかできないことはないかもしれません。
インターネット
わたしが LF-A1 というAX88796搭載のキットを半田付けはしました（下手くそだけど）。チップをコントロールするレジスタおよび送受信バッファを命令レベルから操作できるようコントローラを書けば、理論的には動くはずです。プロトコルスタックを書けば理論的にはインターネットができるはずです。デバイスドライバを書くくらいのレイヤーで扱えるので、物理層を直で触るのに比べるとかなりソフトウェアっぽいです。
チップのレジスタへのデータの読み書きは、普通のRAMのようにしつつ、データシートを参考に適当なクロックだけ待ってやればできると思います。チップからの割り込みは、割り込み信号をFPGA上のレジスタへのAsynchronous Resetにして、コアのクロックでそのレジスタを監視すれば扱えると思います。受信バッファのデータはチップ側のクロックでDMA転送されますが、これは非同期の読み書きに対応しているXilinxのBlockRAMを使ったキューを介することで、おそらくコアのクロックで読み出せるようにできます。