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

5 章コンピュータアーキテクチャ

本章ではついにメモリ、CPU を実装していく。

メモリの実装

基本的に p99 の仕様に従って書いていけばよい。まずは入力として与えられたアドレスがどのメモリマップに位置するかを判定する必要があるが、0-16383 が RAM に、16384-24575 がスクリーンに、24576 以降がキーボードに割り振られていることを考慮すると以下のような表が完成する。これらは p21 の表を参考にしつつ DMux4Way で簡単に書くことができる。出力も同様にマルチプレキサを用いればよい。

	`Address[14]`	`Address[13]`
RAM	0	0
RAM	0	1
Screen	1	0
Keyboard	1	1

最初のデマルチプレキサ部分で a と b に同じ名前の変数を入れると怒られが発生するので (よく考えたらそりゃそうだ)、ここでは loadram0 と loadram1 という変数にそれぞれ格納したうえで、Or をとることによって RAM 入力の boolean をまとめている。

CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];

    PARTS:
        DMux4Way(in=load, sel=address[13..14], a=loadram0, b=loadram1, c=loadsc, d=loadkey);
        Or(a=loadram0, b=loadram1, out=loadram);

        RAM16K(in=in, load=loadram, address=address[0..13], out=outram);
        Screen(in=in, load=loadsc, address=address[0..12], out=outsc);
        Keyboard(out=outkey);

        Mux4Way16(a=outram, b=outram, c=outsc, d=outkey, sel=address[13..14], out=out);
}

CPU の実装

p102 とにらめっこしながら地道に実装していくことになる。ここで作る CPU はデータレジスタ D、アドレスレジスタ A、プログラムカウンタレジスタ PC を備えている。これらのレジスタには、遠く離れた場所にあるメモリより高速にアクセスできる。
CPU に与えられるのは M value input (16 ビット)、reset (命令メモリの値をリセットする場合は 1 を与える) のほか、16 bit の命令がある。p70 で説明があったように、この命令は
- A 命令: 0vvvvvvvvvvvvvvv の形式。A レジスタに vvvvvvvvvvvvvvv の値を設定
- C 命令: 111accccccdddjjj の形式。
  - acccccc の部分 (comp 領域) では実行する計算 (の数式) を指定する。1 bit 目 a では ALU が計算に A レジスタの値か M value input のどちらを用いるかを決定する。
  - ddd の 3bit (dest 領域) では、計算結果を A レジスタ、D レジスタ、Memory[A] にそれぞれ格納するかどうかを指定する。
  - jjj の部分では計算結果の正負に応じたジャンプの条件を指定 (p73 表を参照)。ジャンプする場合、アドレスは事前に A レジスタに設定しておく必要がある。
という形式になっている。とりあえず instruction[15] が 0 のとき A 命令、そうでないとき C 命令になることが分かる。
以上より、ここで A レジスタの目線に立つと次のように書ける。
- A 命令である場合 instruction の値を無条件で A レジスタに設定
- C 命令でありかつ instruction[5] == 1 である場合、ALU 出力を A レジスタに設定
D レジスタの目線では、C 命令でありかつ instruction[4] == 1 である場合のみ ALU 出力を D レジスタの入力に設定することになる。その他の場合は何もしなくてよい (load ビットに false を設定するようにすればよい)。
次は ALU の視点に立ってみる。
- A 命令の場合は特に計算するものもないので適当に false でも出力させておく。
- C 命令の場合は何らか 2 つの 16bit 値に関して計算しなくてはならない。そのうちの 1 つに D レジスタからの出力を用いるのは確定である。もう一つの入力については、a つまり instruction[12] が 0 の場合 A レジスタからの出力を、1 のときは M value input を用いる形にすればよい。
最後は PC の目線である。C 命令でありかつ ALU の出力が jump の条件 instruction[0..2] を満たしている場合のみ load させればよい。そのほかの場合は特にジャンプ操作は発生しないのでインクリメントすればよい (inc = true としておけばよい)。
この CPU の出力について。writeM が true の場合、RAM[addressM] に outM の値を設定することになる。writeM の値は、C 命令でありかつ instruction[3] == 1 であるときのみ true になる。A 命令の場合は A レジスタの値が変化するだけであり RAM の操作は絡まないので、無条件で false となる。
非常にややこしいが、上記をまとめると以下のようになる。

CHIP CPU {
    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).

    OUT outM[16],        // M value output
        writeM,          // Write to M? 
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction

    PARTS:
        // instruction[15] が 0 のとき A 命令、1 のとき C 命令
        Mux(a=false, b=true, sel=instruction[15], out=isC);

        // writeM (M に書き込むかどうかの bool) を出力
        And(a=instruction[3], b=isC, out=writeM);
        
        // A レジスタの処理
        // instruction[5] は d ビット。A に書き込むかどうかを決定する
        // A 命令であるか, あるいは C 命令でかつ instruction[5] == 1 なら load する
        Mux(a=true, b=instruction[5], sel=isC, out=isLoadA);
        // A 命令なら instruction を、C 命令なら outALU を読み込む
        Mux16(a=instruction, b=outALU, sel=isC, out=loadobj); // 図 5-7 の A レジスタ手間のマルチプレキサ
        ARegister(in=loadobj, load=isLoadA, out=outA, out[0..14]=addressM);

        // 計算結果を D レジスタに保存する
        // C 命令でかつ instruction[4] == 1 であるときのみ load すればよい
        And(a=instruction[4], b=isC, out=loadD);
        DRegister(in=outALU, load=loadD, out=outD);

        // instruction[12] は、ALU が A レジスタかメモリ入力のどちらを操作するかを決定する (p71 図 4-3 の左右が決定される)
        // 0 のときは A からの出力を, 1 のときは inM を利用
        Mux16(a=outA, b=inM, sel=instruction[12], out=AorM); // 図 5-7 の、ALU の手間にあるマルチプレキサ
        // ALU
        ALU(x=outD, y=AorM, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], out=outALU, zr=zr, ng=ng);
        // C 命令のとき outALU を outM として出力。A 命令の時は何を出力しても良い
        Mux16(a=false, b=outALU, sel=isC, out=outM);

        // load は ALU の出力 (outM) が jump の条件を満たしている場合に 1 となる
        Jump(in=instruction[0..2], zr=zr, ng=ng, out=isLoadJump);
        Mux(a=false, b=isLoadJump, sel=isC, out=load);
        // in には A レジスタからの出力が入る
        // load あるいは reset が 1 のときはどうせ無視されるので、inc は常に 1 でよい
        PC(in=outA, load=load, inc=true, reset=reset, out[0..14]=pc);
}

ジャンプ部分では以下の自作 CHIP を用いている。ALU から出力された zr, ng のフラグが、instruction[0..2] の内容に沿っているかを判定していけばよい。

CHIP Jump {
    IN in[3], zr, ng;
    OUT out;

    PARTS:
        // 正かどうかの boolean (pg) を作っておく
        Or(a=zr, b=ng, out=tmp);
        Not(in=tmp, out=pg);

        // in[0] は 正、in[1] はゼロ、in[2] は負のときを表す
        And(a=in[2], b=ng, out=out0);
        And(a=in[1], b=zr, out=out1);
        And(a=in[0], b=pg, out=out2);

        // out0-2 のいずれかに該当する場合は true を返す
        Or(a=out0, b=out1, out=out3);
        Or(a=out2, b=out3, out=out);
}

Computer の実装

やっとこさ CPU まで出来上がったところで、あとは p105 の図を参考にしつつこれらを接続するだけである。やったね……！

CHIP Computer {
    IN reset;
    PARTS:
        ROM32K(address=pc, out=instruction);
        CPU(inM=inM, instruction=instruction, reset=reset, outM=outM, writeM=writeM, addressM=addressM, pc=pc);
        Memory(in=outM, load=writeM, address=addressM, out=inM);
}

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

5 章 コンピュータアーキテクチャ

メモリの実装

CPU の実装

Computer の実装

Further Reading

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

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

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

5 章コンピュータアーキテクチャ