😀
ALU（算術論理演算機）
コンピュータシステムの理論と実践の学習内容のダンプ。
論理ゲートを出発点として、算術論理演算機（ALU）を構築する。
多くの計算・命令が二進数の加算に変換できる。つまり、加算器(addr)を作ることができればその組み合わせでALUをつくることができる
2進数加算
最下位bit(LSB)から最上位bit(MSB)まで順に足していけばOK。途中の桁上りの数はキャリービットと呼ばれる。最後に、最上位のキャリービットが1であればオーバフローの判定が行われる
キャリービットを考慮しなければいけないということは、2進数の加算には最低でも3つの加算器が必要ということになる。
符号付き2進数
2進数コードにおいて、負の数を表現する方法として現在は補数が使用されている。
補数とは、n桁の2進数において
あるn桁の2進数xの補数とは足すと2のn乗になるような数を指す
このことから、xに対して、-xをxの補数として表現すれば加算によって引き算を表現することが可能になる。
補数表現の性質
- 最大値は、
2^{n - 1} - 1 -2^{n - 1} - 正の数の最上位bitは0, 負の数の最上位bitは1となる。これは、補数の性質から。
-
-x 2^{n} - {x} 2^
つまり、引き算を足し算として表現できる。これがハードウェアの複雑性を最小限にしている
加算器 (Addr)
加算器には3つの種類がある
半加算器
２つのbitの和を求める。他の加算器の計算結果を使用できないため、半加算器と呼ばれる。
最下位bitをsum, 最上位bitをcarryとすると、sumはXor, carryは And回路で表現できる。
HackマシーンのHDLで表現すると以下のようになる
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}
sum はどちらか一方のみがbitが立っているときに1になる。
carryは、a,b双方のbitが立っているときに1になる。
全加算器
3つのbitの和を求める。前の加算器からのキャリービットを扱えるようになるため全加算器と呼ぶ。
これをつなげていけばn桁の計算が可能となる。
HackマシンのHDLで記述すると以下になる
CHIP FullAdder {
IN a, b, c; // 1-bit inputs
OUT sum, // Right bit of a + b + c
carry; // Left bit of a + b + c
PARTS:
Xor(a=a, b=b, out=out1);
Xor(a=c, b=out1, out=sum);
And(a=a, b=b, out=out2);
And(a=a, b=c, out=out3);
And(a=b, b=c, out=out4);
Or(a=out2, b=out3, out=out5);
Or(a=out5, b=out4, out=carry);
}
sumは、a,b,cで奇数個の1があれば1となるので、3つの排他的論理和を取ればいい
carryは、a, b ともに1の場合か、a,cともに1の場合、b,cともに1の場合に1が立つのでこれを 3つのANDのORを取る
加算器
２つの
HackマシンのHDLで書くと以下のようになる
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
HalfAdder(a=a[0], b=b[0], sum=out[0], carry=carry0);
FullAdder(a=a[1], b=b[1], c=carry0, sum=out[1], carry=carry1);
FullAdder(a=a[2], b=b[2], c=carry1, sum=out[2], carry=carry2);
FullAdder(a=a[3], b=b[3], c=carry2, sum=out[3], carry=carry3);
FullAdder(a=a[4], b=b[4], c=carry3, sum=out[4], carry=carry4);
FullAdder(a=a[5], b=b[5], c=carry4, sum=out[5], carry=carry5);
FullAdder(a=a[6], b=b[6], c=carry5, sum=out[6], carry=carry6);
FullAdder(a=a[7], b=b[7], c=carry6, sum=out[7], carry=carry7);
FullAdder(a=a[8], b=b[8], c=carry7, sum=out[8], carry=carry8);
FullAdder(a=a[9], b=b[9], c=carry8, sum=out[9], carry=carry9);
FullAdder(a=a[10], b=b[10], c=carry9, sum=out[10], carry=carry10);
FullAdder(a=a[11], b=b[11], c=carry10, sum=out[11], carry=carry11);
FullAdder(a=a[12], b=b[12], c=carry11, sum=out[12], carry=carry12);
FullAdder(a=a[13], b=b[13], c=carry12, sum=out[13], carry=carry13);
FullAdder(a=a[14], b=b[14], c=carry13, sum=out[14], carry=carry14);
// ignore carry
Xor(a=a[15], b=b[15], out=out1);
Xor(a=out1, b=carry14, out=out[15]);
// use carry
// FullAdder(a=a[15], b=b[15], c=carry14, sum=out[15], carry=carry15);
}
最初だけHalfAddrで、その後、FullAddrをbit分連鎖させていけばいい。最後でてくるcarry bitを見てオーバーフローかどうかを判断すればいい。
インクリメンタ
1だけを足す回路。最初だけb=trueのHalfAdderを用意し、あとは全加算器同様にすべてを足していく
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
HalfAdder(a=in[0], b=true, sum=out[0], carry=carry0);
HalfAdder(a=in[1], b=carry0, sum=out[1], carry=carry1);
HalfAdder(a=in[2], b=carry1, sum=out[2], carry=carry2);
HalfAdder(a=in[3], b=carry2, sum=out[3], carry=carry3);
HalfAdder(a=in[4], b=carry3, sum=out[4], carry=carry4);
HalfAdder(a=in[5], b=carry4, sum=out[5], carry=carry5);
HalfAdder(a=in[6], b=carry5, sum=out[6], carry=carry6);
HalfAdder(a=in[7], b=carry6, sum=out[7], carry=carry7);
HalfAdder(a=in[8], b=carry7, sum=out[8], carry=carry8);
HalfAdder(a=in[9], b=carry8, sum=out[9], carry=carry9);
HalfAdder(a=in[10], b=carry9, sum=out[10], carry=carry10);
HalfAdder(a=in[11], b=carry10, sum=out[11], carry=carry11);
HalfAdder(a=in[12], b=carry11, sum=out[12], carry=carry12);
HalfAdder(a=in[13], b=carry12, sum=out[13], carry=carry13);
HalfAdder(a=in[14], b=carry13, sum=out[14], carry=carry14);
// ignore carry bit
Xor(a=in[15], b=carry14, out=out[15]);
// use carry bit
// HalfAdder(a=in[15], b=carry14, sum=out[15], carry=carry15);
//// Replace this comment with your code.
}
ALU (算術論理演算器)
このALUは"Hack" というコンピュータプラットフォーム特有のもの。早い話が、この本専用の加算器
18種類の関数がある。どの関数を実行するかは制御ビットの組み合わせで決まる。
/**
* ALU (Arithmetic Logic Unit):
* Computes out = one of the following functions:
* 0, 1, -1,
* x, y, !x, !y, -x, -y,
* x + 1, y + 1, x - 1, y - 1,
* x + y, x - y, y - x,
* x & y, x | y
* on the 16-bit inputs x, y,
* according to the input bits zx, nx, zy, ny, f, no.
* In addition, computes the two output bits:
* if (out == 0) zr = 1, else zr = 0
* if (out < 0) ng = 1, else ng = 0
*/
// Implementation: Manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) sets x = 0 // 16-bit constant
// if (nx == 1) sets x = !x // bitwise not
// if (zy == 1) sets y = 0 // 16-bit constant
// if (ny == 1) sets y = !y // bitwise not
// if (f == 1) sets out = x + y // integer 2's complement addition
// if (f == 0) sets out = x & y // bitwise and
// if (no == 1) sets out = !out // bitwise not
CHIP ALU {
IN
x[16], y[16], // 16-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f, // compute (out = x + y) or (out = x & y)?
no; // negate the out output?
OUT
out[16], // 16-bit output
zr, // if (out == 0) equals 1, else 0
ng; // if (out < 0) equals 1, else 0
PARTS:
Not16(in=x, out=notx);
Mux4Way16(a=x, b=false, c=notx, d=true, sel[0]=zx, sel[1]=nx, out=xout);
Not16(in=y, out=noty);
Mux4Way16(a=y, b=false, c=noty, d=true, sel[0]=zy, sel[1]=ny, out=yout);
Add16(a=xout, b=yout, out=xplusy);
And16(a=xout, b=yout, out=xandy);
Mux16(a=xandy, b=xplusy, sel=f, out=fout);
Not16(in=fout, out=notfout);
Mux16(a=fout, b=notfout, sel=no, out=out, out[15]=ng, out[0..7]=low, out[8..15]=high);
Or8Way(in=low, out=lowout);
Or8Way(in=high, out=highout);
Or(a=lowout, b=highout, out=orout);
Not(in=orout, out=zr);
}
基本的な論理ゲートと加算器の組み合わせによって複雑な処理を可能にする演算ユニットができることが分かった。
Discussion