コンピュータシステムの理論と実装 (2)

あけましておめでとうではあるが、特に新年感もなく粛々と復習を続けていく。今日は第 2 章、ブール算術から。

2 章ブール算術

加算器

$n$ ビットの 2 進数加算をする場合を考える。2 つのビットの和を求める半加算器 (half adder) が必要なのはまあ当たり前である。足し算の筆算的に最下位ビットから計算していくことを考えると、2 つのビットと繰り上がり (キャリービット) を加算することになる。この 3 つのビットの和を求めるのが全加算器 (full adder) である。
半加算器を書いていく。真理値表を書いてぐっと睨めばわかるが、sum (筆算で下に書くやつ) は Xor(a, b)、carry (繰り上がり) は And(a, b) で簡単に書ける。

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);
}

全加算器を書いていく。HalfAdder を 2 つ組み合わせることで実現できる。

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:
        HalfAdder(a=a, b=b, sum=sum1, carry=carry1);
        HalfAdder(a=sum1, b=c, sum=sum, carry=carry2);
        Or(a=carry1, b=carry2, out=carry);
}

16bit の加算器 Add16.hdl は単に最下位ビット用の Half Adder を 1 つと Full adder を 15 個組み合わせればよいので省略。
最後に実装すべきはインクリメンタであり、こちらは単に 1 を足すだけなので Add16 を使えばよいだけだが、HDL で 1 を作る方法がよく分からずまあまあ苦労した。一周目では常に 16bit の 1 を出力する CHIP をわざわざ自作してどうにかしたようだが、賢そうな人の解答例を見る限りこんな感じで書けるらしい。入力の左辺には多ビットパスのピンの一部分を指定できるのね。

CHIP Inc16 {
    IN in[16];
    OUT out[16];
    PARTS:
        Add16(a=in, b[0]=true, b[1..15]=false, out=out);
}

算術論理演算機

初歩的な算術演算と論理演算のすべてをまとめて行うためのものを算術論理演算機 (Arithmetic Logical Unit; ALU) とよぶ。名前がかっこよすぎないか……？
16 ビット入力 $x$ と $y$、および 6 つの制御ビットを与えると 16 ビットの出力が返ってくるように実装する。基本的には p35 のフローにしたがって素直にやっていけすればよい。途中マルチプレキサを使う場面があるが、条件分岐の前にあらかじめありうる出力をすべて書き出して変数に格納しておくのがポイントっぽい。

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 (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
        // if zx then x = 0
        Mux16(a=x, b=false, sel=zx, out=x1); // b = false と簡潔に書ける
        // if nx then x = !x
        Not16(in=x1, out=notx1);
        Mux16(a=x1, b=notx1, sel=nx, out=x2);

        // if ny then y = 0
        Mux16(a=y, b=false, sel=zy, out=y1);
        // if ny then y = !y
        Not16(in=y1, out=noty1);
        Mux16(a=y1, b=noty1, sel=ny, out=y2);

        // if f then out = x + y else out = x & y
        And16(a=x2, b=y2, out=andxy); // ありうる出力を先に全部書き出しておくのがポイント
        Add16(a=x2, b=y2, out=addxy);
        Mux16(a=andxy, b=addxy, sel=f, out=out1);

        // if no then out = !out
        Not16(in=out1, out=notout1); // 反転したものを準備
        // ここで最終的な out が出力されるので、
        // if out < 0 then ng = 1 else ng = 0 もついでに済ませてしまう
        Mux16(a=out1, b=notout1, sel=no, out=out, out=out2, out[15]=ng); 

        // if out == 0 then zr = 1 else zr = 0
        IsZero(in=out2, out=iszero);
        Mux(a=false, b=true, sel=iszero, out=zr);
}

最後 out が 16bit の 0 かどうか判定する場面で、自分の書いたコードでは 16bit すべてについて Or を書いていく CHIP IsZero を書いていたのだけど、よく考えたら Or8Way を 2 回使えば済む話だった。
出力の際に OUT で定義されている同じ名前のピンを複数同時に書くことができることを知らなかったので難儀した。例えば out=out, out=out2, out[15]=ng のように out を複数存在させることができ、ここでちゃっかり新しい変数定義をしたり、出力ピン (の一部) を変数に代入できたりするらしい。逆に例えば in=out[15] のようにすると怒られが発生するので助けてくれーという気持ちに。

コンピュータシステムの理論と実装 (2)

2 章 ブール算術

加算器

算術論理演算機

Further Reading

コンピュータシステムの理論と実装 (1)

コンピュータシステムの理論と実装 (3)

コンピュータシステムの理論と実装 (5)

2 章ブール算術