MIPSマイコンを作ろう

最近、CPUを書くことがすっかり趣味になってしまいました。
今度は、パイプラインを備えた本格的なCPUを書いてみたくなったので、MIPS Iのサブセットを書いてみます。
MIPS Iは今までにいくつかの実装例があり、車輪の再発明をしても仕方が無いのですが、１つ目的があるのです。
自分では、CPUのパイプラインというものを抽象的には分かっているつもりですが、コードに落とせるくらいちゃんと理解しているのかといわれるとちょっと自信がありません。
そこで、実際に書いて理解しようというわけです。
既にあるコードを読んで勉強すればいいのですが、どうも人のソースを読むのは苦手なもので...

パイプラインの動作が確認できる程度でいいので、以下のようなサブセットにしました。

割り込み、例外なし。
キャッシュ、TLBなし。
乗除算なし。
インストラクション、データはそれぞれブロックRAMを使い、相互アクセス不可。
インストラクション 512ワード
データ 512ワード
ロード／ストアはワードサイズのみとします。

サポートするインストラクションは以下の通りです。

ADD ADDI ADDIU ADDU SUB SUBU
BEQ BGEZ BGEZAL BGTZ BLEZ BLTZ BLTZAL BNE
J JAL JALR JR
LUI LW SW
AND ANDI NOR OR ORI XOR XORI
SLL SLLV SRA SRAV SRL SRLV
SLT SLTI SLTIU SLTU

例外はサポートしないので、ADDとADDU、ADDIとADDIU、SUBとSUBUは同じ意味になります。

パイプライン

パイプラインを構成するに当たって、必ずレジスタが入るところを考えてみます。

(1) プログラムカウンタ
(2) インストラクション用のブロックRAM
(3) レジスタファイル用のブロックRAM（読み出し）
(4) データ用のブロックRAM（読み／書き）
(5) レジスタファイル用のブロックRAM（書き込み）

ただし、通常の演算では(4)が、ストアでは(5)が無効です。
上記から、これをそのまま５段パイプラインにするのが自然です。

実際に書いてみると、あまりにシンプルに構成できることに驚きます。
パイプランでめんどくさそうだと思っていたフォワーディングは２ヶ所ありますが、種類としては１つだけです。インターロックは今回の範囲では必要ありません。
MIPSアーキテクチャが非常によく考えられたものであることが分かります。

クロスアセンブラ

有名なプロセッサだと、クロスアセンブラがすぐに手に入るメリットがあります。

http://www.gnu.org/order/ftp.html

の中の適当なミラーサイトからbinutilsを落としてきて展開し、

% ./configure --target=mips; make

するだけです。
できたバイナリの中で必要なのは

gas/as-new
ld/ld-new
binutils/objcopy

の３つです。

シミュレーション

iverilogを使って、N-Queensを走らせてみました。
盤面が5x5のときN=10と、正しい結果が得られました。このときのクロック数は987でした。

download(version0.1)

試しにISE7.1webpackで論理合成してみると、mips_k_coreがエリア優先で335スライスでした(XC3S50-5)。
なんと、Z80の半分です。32ビットなのに、バレルシフタ搭載なのにです。
ブロックRAMは、インストラクション用とデータ用を含めて４つなので、3S50に全部入ってさらに400スライスも余っています。
速度は、MPPR(Multi Pass Place & Route)後の最小周期が17.4nS(57MHz)となりました。エリア優先の割には速いと思います。
パイプラインの勉強で始めたんですが、実用のプロセッサとして使えるかもしれません。

機能追加

もうちょっと書き足しました。
まずは乗除算です。乗算はスパ３のマルチプライヤ任せ、除算は最もシンプルな復元法を書きました。
これらによりインターロックの検証ができます。乗算は待つ必要はないのですが、クリティカルパスになるのでパイプラインレジスタを入れています。
あとは、ワードサイズ以外にバイトとハーフワードのロード／ストアを追加しました。
もう１つ、バージョン0.1では回路を減らすためにトリッキーなバレルシフタにしたのですが、ちょっと遅いので、まともなバレルシフタにしました。
もちろん、バレルシフタがクリティカルパスにならない場合は小さい方で十分です。
これらの追加／変更を全部入れると1000スライス近くになってしまうので、それぞれdefineでON/OFFできるようにしました。全部OFFなら、極小サイズのままです。

FPGAで検証

例によってスパ３スターターで走らせてみたところ、ちゃんと走りませんでした。
仕方がないので、PICオルゴールでI2Cバスのデバッグに使ったコードを改造してトレース機能を追加しました。
ソース中、tracedataで指定したデータをシリアルに送り出します。
この機能を使って検証したところ、レジスタ用のブロックRAMがシミュレーションと異なる動作をしていることが分かりました。
今回は、全て独立したアドレスで２ポート読み出し、１ポート書き込みを同時に行うので、ブロックRAMを２つ使います。
これをXSTがちゃんと検出してそのように割り当ててくれたことには感心しました。
問題は、スパ３のブロックRAMの仕様にありました。
デュアルポートで使う場合、反対側のポートにはWRITE_MODEのWRITE_FIRSTが通用しないのです。
詳しくはアプリケーションノート463に書いてあります。
別途フォワードしてもいいのですが、実際に必要なのは1kビットなので分散RAMに変更して解決しました。
これで、FPGAでもN-Queensがちゃんと走るようになりました。

download(version0.2)

割り込み

MIPS/kコアに割り込みを実装しようとして、仕様的に謎な部分がありました。
通常は割り込まれた命令をなかったことにして、復帰時にその命令から実行します。
ところが、分岐のディレイスロットで割り込まれると、復帰時は既に分岐先にいるかもしれないのでディレイスロットの命令を実行できません。
ディレイスロットにいるときは割り込みを受け付けなければいいのですが、実物は受け付けるようです。
で、あるときこの謎が解けました。
分岐のディレイスロットにいるときは、直前の分岐命令もなかったことにして、そこに復帰し、分岐の判定からやり直します。
具体的には、IFステージがディレイスロットのときに割り込みを受け付けたら、PCとして割り込み先のアドレスを出力するとともに、IDステージでデコード中の直前の分岐命令をNOPに差し替えます。
また、割り込み許可の状態では常にPC出力をコピーするEPCも、ディレイスロットにいるときはコピーしないことで、直前の分岐命令に復帰できます。
外部からの割り込み入力を１本用意してFM音源ジュークボックスの７セグのスキャンをタイマー割り込みによるソフトウェアスキャンに変更して検証したところ、このやり方でOKでした。
CP0はEPCとIEcのみ実装し、MTC0でIEcにだけは書き込めるようにしました。
また、割り込みからの復帰はMIPS IのRFEではなく、MIPS IIIのERETを実装しました。

branch likely

MIPS IIIで、分岐のディレイスロットにある命令を分岐する場合だけ実行する
BEQL/BNEL/BGEZL/BGTZL/BLEZL/BLTZL/BGEZALL/BLTZALLが追加されました。
一見何のためにあるのか分かりませんが、通常の分岐命令ではディレイスロットをNOPにせざるを得ない場合に、分岐先の最初の命令をディレイスロットに移すことで１クロック得をします。
割り込みを実装したことにより、ディレイスロットにいることを検出し、条件によって命令をNOPに置き換える機能がついたので、これらの命令もついでに実装しました。

Xilinx専用に

プリミティブライブラリを使うと、スライス内の割り付けを指定できるようになり、通常の書き方では不可能なマッピングができます。結果として、使用スライス数を減らすことができます。
そこで、できる限りプリミティブで書き直してみました。
そんな訳で、このバージョンからXilinx専用になってしまいました。名前もKX_MIPSに変えました。
フォワードを追加することで、レジスタの読み出しをEXステージから１つ前のIDステージに移したこともあり、機能が増えたにもかかわらずサイズ、スピードともに前のバージョンより改善しています。

download(version0.3)

キャッシュ

KX_MIPSにキャッシュを実装しようとして、謎な部分がありました。
それは、５ステージ構成のままキャッシュを付けられるのかということでした。
例えばIキャッシュの場合で、タグメモリにブロックメモリを使う前提で考えます。
まずプログラムカウンタが確定したらタグメモリを参照して、キャッシュにヒットしているかどうか調べます。
ここで、ブロックメモリは同期読み出ししかできないので、ヒットしているかどうか分かるのは次のクロックが立ち上がったあとです。
ところが、同じタイミングで次のインストラクションが用意できていないといけないので、ミスした場合は間に合わないのです。
キャッシュを付加するためにはステージ数も増やす必要があるのか？
...と考えていたのですが、実は大丈夫です。ミスした場合でもとりあえずキャッシュに入っている無効なインストラクションをデコードさせておいて、そのままストールさせてキャッシュフィルをします。
フィルが完了してキャッシュから正しいインストラクションが出力されるようになったら、改めてデコードさせてストールを解除します。
Dキャッシュの場合も同様に、無効なデータをロードしたあとストールしてフィルし、正しいデータが準備できた時点でレジスタに書けば問題ありません。

以上の考え方を元に実装しました。
FM音源ジュークボックスのPSG版で動作確認をしました。
なんでPSGかというと、アドレス空間を4Gバイトにして検証するため、FM音源では手持ちのXC3S200に入りきらないからです。
Iキャッシュは2kバイトのダイレクトマップで、ブート用のコードを初期値として持たせるためvalidフラグはありません。
Dキャッシュは2kバイトのダイレクトマップで、ライトバックです。
両キャッシュとも、ラインサイズは16バイトとしました。
キャッシュの制御をするCACHEインストラクションは実装していません。
4ウェイセットアソシアティブも作ってみたのですが、全てのウェイのタグとデータを同時に読み出し、タグアドレスが一致するデータを選択してコアに出力する構造となり、どうしても遅くなってしまうため今回は見送りました。
MicroBlazeのキャッシュがダイレクトマップなのはこの辺りの事情かもしれません。

OPENCORESにあるMIPS系のコアとサイズ、速度を比較してみました。
ISE9.1.03i(webpack)のエリア優先で、デバイスはXC3S400-4FG320としました。
KX_MIPSはIキャッシュとDキャッシュを含み、それ以外はコアのみです。
UCoreについては、`DEBUGをコメントアウトしています。

KX_MIPS	852スライス+3RAMB(キャッシュを含む)
Plasma	1285スライス
UCore	2050スライス+2RAMB
miniMIPS	2522スライス+4MULT

KX_MIPS	18.590nS
UCore	19.723nS
miniMIPS	27.945nS
Plasma	49.951nS

(2009/03/15修正)
ALU周りを最適化

download(version0.41)

このページからダウンロードできるソースは、非営利目的に限り自由に使用できます。
なお、いっさいの保証やサポートはありません。