Open Design Computer Project

オリジナルCPUから作る本格的自作コンピューター

ユーザ用ツール

サイト用ツール


trial_and_error

mist32 における考察と失敗談

自作CPUを作るにあたって、悩んだ感想や書き留めておきたいことを残しておきます。

まあ、自作CPUを作る人ってそんなにいないと思いますけど… いろいろ悩めるところがあって楽しいです。

ツッコミは @hktechno, @cpu_labs または <hktechno at open-arch.org> まで。

ISA

2オペランドの理由

mist32 は、RISC を謳っているにもかかわらず2オペランドであるが、これは命令セットをアウトオブオーダーに最適化するためである。3オペランドであれば、最大3つのレジスタへの参照が起きてしまい、回路が複雑になり規模が大きくなってしまう。2オペランドにすることで、それを少なくしようという目論見である。

また、レジスタの参照が起きなければよいので、Immediate に関しては、オペランドを追加することもできる。そのため、Load/Store においては、ディスプレースメント付き命令を用意することができた。
hktechno 2013/07/22 00:48

2-operandの場合でも、Register Rename時に3-operandになるため、ハードウェア規模としてはあまり変わらない。2-operand方式を採用したのはAFEを使用したかったため。
takahiro 2013/07/22 01:10

つまり、フィールドのやり繰りがどうにかなれば、3-operand でも良かった… っぽい。
hktechno 2013/07/22 01:17

夢の VLIW の方が優れているのでは?

あとで書く。結果的に言うと、そんなことはない。

コンパイラが使えるような命令を用意する

基本的に、今の時代アセンブラで最適化するなんてことは、滅多に行われない。と言うよりは、せっかく初めから作るのだし、コンパイラが吐くコードに CPU が最適化してあげたほうが良い。

そのような考えに基づき、mist32 では、アウトオブオーダーの邪魔にならずコンパイラが使いそうな命令は入れる、アウトオブオーダーの邪魔になってコンパイラが使わなさそうな命令に関しては入れない、という方向で進めている。
hktechno 2013/07/22 00:51

mull, mulh 命令

mul 命令の演算結果は 32bit 同士の演算であれば 64bit 幅になるので、2つのレジスタに保存されることが多い。

  • x86: edx:eax に格納される
  • MIPS: hi:lo に格納され、専用命令で読み出す

しかし、C言語では、普通の演算では基本的に下位 32bit の結果しか利用しないと思う。更に、mist32 では、1命令で参照・変更するレジスタを制限することでアウトオブオーダー実行に必要なハードウェアを小さくしており、この実装は許容できない。

mist32 は、解決方法として、以下の2命令を用意している。

  • mull: 乗算結果の下位 32bit を格納する
  • mulh: 乗算結果の上位 32bit を格納する

ちなみに、ARM は 32bit だけを格納する命令と、64bit を吐き出す命令と、2種類用意されている。似ている。
hktechno 2013/07/22 00:30

div 命令

x86 とかだと div も、割られる数側が 64bit になっているが、用意しない予定。(mul の理由と同様)
hktechno 2013/07/22 00:30

Flags

開発日記 の、“Flag Chainの廃止について” を参照
hktechno 2013/07/22 00:02

つまりのところ、フラグという存在が一種のレジスタであるので、フラグを書き換える命令はすべてフラグレジスタに副作用が発生することになる。つまり、オペランドが一つ増え、アウトオブオーダー実行する際の依存関係が増える。つまり、フラグは必要ないならそれが一番良い。

フラグレジスタをなくすことの弊害は、上述した他倍長演算におけるキャリーの問題以外にも、もうひとつある。例えば次のようなコード。

  cmp r1,    0
  br  plus,  #gt    ;; OK
  br  minus, #lt    ;; INVALID FLAGS
  br  zero,  #eq    ;; INVALID FLAGS

このような命令列は、mist32 では invalid となる。ブランチで参照されるフラグは、その1命令前の命令としか定義していないからである。つまり、mist32 では、上記のような命令でも cmp を複数回発行する必要が出てくるが、1命令だけであるし、アウトオブオーダー実行と分岐予測がうまく働けば、フラグを発行する命令のコストを隠蔽できるので、比較的問題ないのかもしれない。

ちなみに、フラグレジスタ、condition-code の類を持たないマシンも世の中には存在する。DEC Alpha がその例であるが、どのようにキャリーを判断していたかというと、加算結果と加算前のデータを比較してキャリーを判断するコードを自分で書く必要があるようである。やはり、昔からフラグレジスタはボトルネックになると考えられていたようで、自分たちも車輪の再発明してるなぁと…
hktechno 2013/07/24 04:20

Stack pointer

mist32 は、sp が汎用レジスタではない。そのため、読み出しと書き出しに専用命令が必要になるが、コンパイラから見るとあまり良くない実装である。例えば、スタックトップに store するとき、sp が汎用レジスタであれば st32 Rs, sp のような構成でいけるものが、2命令必要になる。ディスプレースメント付き命令でも一緒である。

まあ、ベースポインタから参照する方法もあるが、-fomit-frame-pointer をつけてコンパイルすると上記のような命令を比較的使うようになる。そうなった場合、実質スタックポインタのコピーを汎用レジスタで持つ必要があるので、あえて sp をシステムレジスタとして分ける必要はない。何もデメリットがないのであれば、sp は汎用レジスタとして持たせたほうが良い。

ちなみに、どうでもいい話ではあるが、sp が汎用レジスタでないと、gcc の実装も大変面倒くさくなるのでやめたほうがいい。(ソフトウェア屋的視点)

しかしながら、sp をシステムレジスタにしたのは何らかの理由があったはずだけど、なんだっけ…
hktechno 2013/07/23 06:51

Interrupt

割り込みの優先度と流量制御

プロセッサが、外部から何か通知を受け取る手段、それは基本的に割り込みとポーリングの2つである。しかしながら、ポーリングは定期的に監視し続けなければいけないので、間隔が速すぎるとプロセッサのリソースが専有されてしまう。外部からの通知をすぐに受け取りたい場合には、割り込みを利用するべきである。

それでも、割り込みにも問題はある。割り込みは高コストである、通知の監視に一切資源を専有しないのにも関わらず。それはなぜかというと、割り込み処理にコンテキストスイッチが発生するため、レジスタ退避などが必要であるからである。割り込みは、発生した瞬間にハンドラが呼び出されるため、割り込み実行前のコンテキストは十分な時間実行されていないにも関わらず、終了されてしまう可能性もある。割り込みが頻繁に発生し続けるとなると、コンテキストスイッチに使われるCPU時間の割合が大きくなる、つまり無駄である。

この問題を解決するには、割り込みの流量制御のような仕組みを用意することが考えられる。mist32 では、割り込みに優先度を用意しているが、この優先度によって、割り込みがかかるタイミングを制御しようとしている。

割り込みには、すぐに受け取らなければいけないもの(タイマや高速なI/O)と、比較的どうでもいいもの(キーボードやマウス)がある。前者は優先度を高くしておいて、後者は低くしておく。そして、優先度が低いものは、割り込みをすぐ起こさず、間隔を制御する。例えば、ハードウェアコンテキストスイッチと連携して、コンテキストスイッチが起きた時に発生させたり、他の割り込みが発生したあとに発生させたりすることで、無駄なコンテキストの切り替えが起きづらくなると、なんとなく考えた。

特に、数10ms間隔でシステムコールなどが起きているらしいので、カーネルがこのタイミングでポーリングさせてもうまく行くよね、みたいな話がモダンオペレーティングシステムに書いてあったので、現実味有りそう。具体的に調べてみる必要がある。
hktechno 2013/07/22 01:18

Calling Convention

引数レジスタの個数はいくつに設定するのが良いのか

glibc の関数の引数の数について調べてみた を参照。

上記の例だと、6個ぐらいあれば良いようなので、6個にしようと思う。というのも、r0 が返り値で、r7 をテンポラリレジスタにすると、r0 - r7 までを caller-saved register にすれば区切りがよく、6個引数レジスタを確保できるので。
hktechno 2013/07/22 02:59

Memory Management Unit

4KB ページサイズに隠れた不思議

当たり前のように、現在のプロセッサはメモリページング機構を使っていますが、ページサイズは 4KB が、基本的にどのプロセッサでも使われている。 もちろん、これを変えてしまうと OS やソフトウェアが 4KB ページを前提に作られているので問題になるということもあるが、4KB 以上のページサイズに設定するプロセッサが出てきてもいいと思う気がした。(x86 の 4MB ページとかあるけれど、結局は 4KB ページがベース)

4KB Page の場合

だが、実はページサイズを変えると、ページテーブルのサイズがページサイズと一致しなくなる問題もある。実は、4KB ページサイズはこの点に置いて優れた方式であった。

  • Page Size: 4KB ⇒ Page Address Offset: 12bit
  • Page Index: 32 - 12 ⇒ 20bit / 2 = 10bit
  • Page Table Entry: 4byte
  • Page Table Size: 2^10 * 4 = 4KB

となるので、一般的に使われる 10:10:12 な 2-Level 4KB ページサイズのページング機構は、ページテーブルサイズも 4KB となり、とても扱いやすい。

16KB Page の場合

例えば、これを 8KB, 16KB, 32KB のページサイズにしたらどうだろう。ここでは 16KB ページサイズとして計算してみよう。

  • Page Size: 16KB ⇒ Page Address Offset: 14bit
  • Page Index: 32 - 14 ⇒ 18bit / 2 = 9bit
  • Page Table Entry: 4byte
  • Page Table Size: 2^9 * 4 = 2KB

このように、ページテーブルのサイズは半分になるにも関わらず、ページサイズが4倍になるので、扱いにくくなる。

何故扱いにくいかというと、今までは PDT の PTE の上位20bitが、ページテーブルの物理ページ番号になっていた。これによって、1段目も2段目も同じページテーブルサイズ、かつそれがページサイズと同一、同じ PTE 構造を保つことができていた。しかし、これが他のページサイズになるとできなくなる。

ページテーブルサイズ != ページサイズとなる場合に、いくつかの解決方法が考えられる。

1ページに複数のページテーブルを配置する解決方法

まずひとつに、1ページに複数のページテーブルを入れる方法である。ページサイズ 16KB の時に、ページテーブルサイズが 2KB であるならば、1ページに8個のページテーブルが入る。しかしながら、こうなった場合に PTE を1段目(PDT)と2段目(ページテーブル)で統一することができなくなる。PTE を共通構造のままにした場合には、1ページに1ページテーブル、しかもページの先頭にしか配置できなくなり、とても扱いにくいし効率が悪い。

  • Page Directory Table Entry
    • Page Index: 21bit
    • Flags: 11bit
  • Page Table Entry
    • Page Index: 18bit
    • Flags: 14bit

とすると、しっくりくる。ちなみに、PDT は専用のレジスタ (x86: CR3) がアドレスを指定することになるので、ページのどこに配置されていようと問題にならない。

但し、1ページに複数のページテーブルを配置すると、効率化を追求するとよく使うページテーブルと使わないページテーブルを同じページに入れたくないという問題が出てくる。あまり使わないページテーブルはまとめてしまって、なるべくスワップアウトしたいので、欲を言うとこういったややこしい問題が出てくるが、ページテーブル全体のサイズは少なくなっているので、ページテーブルをスワップアウトしない前提ならあまり気にする必要はない。

2段目のページテーブルサイズをページサイズに合わせる解決方法

もうひとつの方法として、均等割にしていたページテーブル内のインデックスのビットサイズを可変させて、2段目のページテーブルのサイズをページサイズに合わせる方法である。例えば、上記の 16KB ページの例では、つまり以下のようになる。

  • Page Directory Table Index: 6bit
    • Size: 2^6 * 4 = 256byte
  • Page Table Index: 12bit
    • Size: 2^12 * 4 = 16KB
  • Page Offset: 14bit

こうすれば、PTE は共通構造のまま、16KB ページを維持することができる。

この方式の利点は、PDT を除きページサイズに統一されるため、扱いやすさはさほど 4KB ページと変わらないことと、ページテーブルの数が少なくなること(つまり PDT 内の PTE の TLB ミスも減る)。ただし、ページテーブルの粒度が上がるので、メモリ全体がまんべんなく使われるとなると、ページテーブルに使われるサイズが大きくなる。

たぶん、後者の方がパフォーマンスが良いと思うのだけど、ちゃんと調べたわけでもないのでよくわからない…
hktechno 2013/10/09 07:07

ページサイズを大きくしたい理由

ページサイズを大きくしたほうがいい理由は、TLB ミスが減るからです。TLB は、回路面積を大きく消費するので、あまり大きくすることができません。Core2 の場合は128エントリぐらいのようです、Nehalem はもっと大きい。(参考)

では、ページサイズをむやみに大きくするとどうなるかというと、メモリの利用効率が悪くなります。例えば、1MB が最低のページサイズであるならば、最低でも1プロセス 1MB のメモリを消費するようになりますし、スワップの単位もこのサイズになります。memcached のような、大量のオブジェクトが仮想メモリに乗っているような場合にスワップした時を考えると、1MB はやりすぎのように思えます。

しかし、まあスワップしない前提で大量にメモリが乗っている環境なら、さほど問題ないのかもしれません。ちなみに、x86 の 4MB ページや 2MB ページは、カーネルなどスワップアウトさせない前提のメモリ領域を TLB ミスを少なくするために用意された機能です。上記のように実装しやすかったから、このサイズになってます。

正直、用途や環境によって最適なページサイズはすごく変わってきそうな気がします。なので、一概にこれがいいと言えない気がしますが、4KB と 4MB の中間があってもいい気はするのです。また、SSD などを使って積極的にスワップをするようなものだと事情が変わってきます。細かく可変サイズ、とかもありな気がする。
hktechno 2013/10/09 07:17

カーネル空間専用ページテーブルの必要性

trial_and_error.txt · 最終更新: 2014/01/14 12:59 by hktechno