6日目: [CPU] bit拡張と数値演算
bit拡張と数値演算
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の6日目の記事です。
昨日は変数(レジスタ)の数を4個に増やして、mov命令が実行できるCPUを設計した。
しかしmov命令だけでは大したことができない。
そこで今日は(浮動小数点を含む)四則演算ができるように回路を拡張する。
bit拡張
昨日はレジスタの種類を増やしたが、各レジスタの桁数は1bitのままだった。
2進数1桁の変数では計算もへったくれもない1ので、まずはbitを拡張しよう。
拡張方法は極めて簡単。
例えばmov a, bを考えると、aの1の位はbの1の位で上書きされ、10の位は10の位で上書きされる。
つまりmov命令は各桁毎に独立に実行される。
これを実現するには、昨日の回路と全く同じものを並べればいい。
当然だが、マルチプレクサに入る線Sx, Syは各桁の回路で共通化する。 これでのmov命令CPUを4bitに拡張することができた。
ちなみに世間で32bitのCPUとか64bitのOSとか騒いでいるのは、このレジスタのbit数のことを指している。 こうしてみると、Dのフリップフロップを単純にたくさん並べればbitが増やせるので、128bitでも256bitでも簡単に拡張できそうだ。
複数ビットを配列としてSystem Verilogで扱うには
logic [0:3] A; assign A = 4'b0011; // 十進数と十六進数で3 // A[0] === 1'b0; // A[1] === 1'b0; // A[2] === 1'b1; // A[3] === 1'b1; logic [3:0] B; assign B = 4'b0011; // 十進数と十六進数で3 // B[3] === 1'b0; // B[2] === 1'b0; // B[1] === 1'b1; // B[0] === 1'b1; logic [7:0] memory [0:63]; // 8bitのメモリが64個ある assign memory[ 0] = 8'b00000011; // 十進数と十六進数で3 assign memory[ 1] = 8'b00000111; // 十進数と十六進数で7 assign memory[63] = 8'b00001000; // 十進数と十六進数で8
演算素子の追加
変数の桁が増えたので、次は計算命令をCPUに追加しよう。 簡単のために、まずは昨日の1bitのCPUに演算の素子を追加してみる。
昨日の回路
ここから赤い部分だけを取り出したのが下の左の図
取り出した部分に対し、右図のように演算の素子を追加する。
こうすれば、人力でTの線に電圧を印加することで、レジスタ間の演算が行えるようになる。
1bitのCPUに演算を追加する方法は分かったが、次はこれを複数bitに拡張したい。
やや抽象的な図で恐縮だが、要するに足す前に各桁の線を集めて、加算を実行し、結果を各桁に散らすという方法で複数bitの演算が実現できる。
この図のFull Adderの部分に減算器や乗算器などの組み合わせ回路を追加して、マルチプレクサで演算種別を選択できるようにすれば、様々な計算が実行可能なCPUになる。
今日の残りの時間は、ここに入れる組み合わせ回路をひたすら説明していく。
整数の加算
まずは加算を実装したい。 そのためにまず半加算器(Half Adder)を作り、それを使って全加算器(Full Adder)を作ればよい。
半加算器を一言でいうと、1bitのA,Bの加算を行う回路だ。
真理値表は
| A,B | S | C |
|---|---|---|
| 0,0 | 0 | 0 |
| 0,1 | 1 | 0 |
| 1,0 | 1 | 0 |
| 1,1 | 0 | 1 |
つまりA+Bの1の位がSに入り、10の位がCに入る。
このままでは複数桁どうしの加算には使えないので、全加算器に拡張する。 全加算器を一言でいうと、1bitのA,B,Xの加算を行う回路だ。
真理値表は
| X,A,B | S | C |
|---|---|---|
| 0,0,0 | 0 | 0 |
| 0,0,1 | 1 | 0 |
| 0,1,0 | 1 | 0 |
| 0,1,1 | 0 | 1 |
| 1,0,0 | 1 | 0 |
| 1,0,1 | 0 | 1 |
| 1,1,0 | 0 | 1 |
| 1,1,1 | 1 | 1 |
要するにX+A+Bの1の位がSに、10の位がCに入る。
次に複数桁同士の加算を考える。
4桁同士の加算 A+B=C を計算するには、
- A[0]+B[0]を半加算器で計算し、その繰り上がりをX[1]とする
- A[1]+B[1]+X[1]を全加算器で計算し、その繰り上がりをX[2]とする
- A[2]+B[2]+X[2]を全加算器で計算し、その繰り上がりをX[3]とする
- A[3]+B[3]+X[3]を全加算器で計算し、その繰り上がりをX[4]とする
- A[4]+B[4]+X[4]を全加算器で計算し、その繰り上がりをキャリーフラグとする
つまり小さい桁から1bit毎に足していけば、複数桁の加算結果が得られる。 回路図で書くと
回路図は4bitのAとBを加算する回路を表している。
ちなみに最も大きな桁が繰り上がった場合、キャリーフラグが立ったという。 図の右端のCはキャリーフラグを表している。
キャリーフラグは計算の破綻を意味しているように見えるが、必ずしもそうではない。 今から説明する減算の際にはキャリーフラグが立ちまくる。
2の補数と整数の減算
加算の回路は構成できたので、次は減算だ。
ところでA-BはA+(-B)なので、Bをマイナスにする方法が分かれば、さっきの加算器を使って減算が実現できる。
数学的に-Bは、Bと加算するとゼロになる数として定義されている。
ここで
0001+1111=10000 -> 5bit目無視 -> 0000
という計算を考えると、4bitの範囲で-0001は1111っぽい雰囲気がある。
ここで0001から1111を得る操作は
0001のマイナスを計算したい -> 1110 (ビット反転) -> 1111 (1を足す)
このようにして得られる数を2の補数という。 この辺の細かい話(符号付き整数の範囲は-4~3なのか-3~4なのか等)は後のx86のパートで詳しくやる予定なので、今はとりあえず2の補数とればマイナスになるんだなと思って欲しい。
ここまでの話をまとめると、A-Bを実現するには
- Bをbit反転する
- そこに1を加える
- そこにAを加える
とすればよい。この回路は以下のようになる。
BバーはBのbit反転を表しており、Bの各桁をNOTゲートに入れれば作成できる。 2の補数を計算する際に1を加えるが、それは左端の全加算器(FA)に1を入力して対処している。
整数の乗除
加減算が完成したので、次は乗除だ。
2進数の乗除の筆算を考えると、桁をずらしながら加算と減算を実行していることが分かる。 加算器と減算器は手元にある。 従って、あとは桁のシフトさえできれば筆算のアルゴリズムが実装できる。
桁を1つシフトするのは簡単だ
これを直列につなげれば、何桁でもシフトできる。 あとは加算器や減算器とうまく組み合わせることで、乗算器や除算機を作ることができる。 要するに「1桁ずつずらして足す」という操作を、レジスタのbit長と同じ回数だけ直列に実行する回路を作れば良い2。
浮動小数点
ここまでの話は整数の話だったが、せっかくなので小数の四則演算も説明する3。 計算機上で小数を表現する際、いわゆるfloag型の浮動小数点方式がよく使われる。
float型は32bitのレジスタで表現されるのだが、
- 最初1bitが符号部
- 次の8bitが指数部 (桁を表す)
- 次の23bitが仮数部 (1以上10未満の数値を表す)
という3つの部分で構成されている。
例えば科学技術分野ではアボガドロ数を
+ 6.02214*10^23
という指数形式で表すけど、float型はこれを2進数でやっているだけだ。
ところでアボガドロ数について
6.02214*10^23 - 6.02201*10^23 = 0.00013*10^23 = 1.3*10^19
という計算を考える。 減算による桁落ちが発生し、指数が23から19に変わっている。 この数式の2行目から3行目の処理を正規化という。
これと同じ現象がfloat型の演算でも発生する。 つまり浮動小数点の計算を行うためには、電子回路で正規化を実装する必要がある。
正規化を行うためには、アボガドロ数の例で説明すると
- 0.00013を見て、「ゼロでない最大の桁」を発見する機能 ... Find First One
- その桁の分だけ0.00013をbitシフトして、1.3にする機能 ... バレルシフタ
この2つの機能が要求される。これらの実装をまとめておく。
Find First One
まず準備として、最初の4桁に1が含まれるか調べたければ、以下のOR回路の組み合わせのif 1 in 4を使えば良い。
これを拡張して、最初に1が現れる桁を発見する回路を作りたいのだが、
それはif 1 in 4やif 1 in 8をマルチプレクサで繋げば得られる。
縦長の長方形は固定桁のbitシフタを表す。整数の乗除のところで1桁のbitシフタを導入したが、あれを直列に繋いだものだ。 台形のMは頻出のマルチプレクサ。
実はこの回路図だとSのビットが反転しているので、入出力の例は以下のようになる。
input = 0001000011111110 (左から3個0が連続している)
--> [S3, S2, S1, S0] = [~0,~0,~1,~1] (3は2進数で0011)
= [ 1, 1, 0, 0]
バレルシフタ
欲しいのは、入力データをinput、シフトする桁数をSとしたときに
* input = 0001000011111110 * S = 3 (3桁ずらしたい) [S3, S2, S1, S0] = [0,0,1,1] (3は2進数で0011) --> output = 1000011111110000
となるような組み合わせ回路だ。 これは固定長bitシフタとマルチプレクサで構成できる。
以上でFind First Oneとバレルシフタの説明は終了だ。 これらと加算器や減算器を組み合わせることで、浮動小数点の正規化ができるようになった。
これだけツールが揃えば、もはやなんでもできる。
2つの浮動小数点数A,Bに対する四則演算であれば
他にも、剰余であれ三角関数であれ、今まで紹介した素子を組み合わせれば実装できる(と思う。多分)。
これで算術演算の基礎は一通り書き終えたと思う。
明日はメモリ周りをやる。本格的なCPUの形が見えてきた。
どうでもいい話
今日は計算を説明したが、加算器のところにキャリーフラグが出てきた。 このような計算に伴うフラグは、他にもいくつかあって
- 符号付き整数の桁あふれを表すオーバーフローフラグ
- 計算結果がゼロかどうかを表すゼロフラグ
- 計算結果の符号を表すサインフラグ
詳細はx86のパートを待たれよ
