クソ雑魚エンジニアのメモ帳

学んだことを書くところ

低レイヤチョットワカル(nand2tetris/コンピュータシステムの理論と実装5章)

こんにちは。ようやくコンピュータの核の部分を実装する章までやってきた。。

地味に長かった。がなんとか終わりそう

www.oreilly.co.jp

記録用git

vol.1

vol.2

vol.3

vol.4

vol.5 いまここ

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

理論(一般的なコンピュータ)

ノイマンアーキテクチャ

CPUが中央にあり、メモリ・入力デバイス・出力デバイス等と通信する。

メモリ

データメモリ・命令メモリの2種類に分けられる。アーキテクチャによっては別のメモリユニットになり得る。

どちらにせよバイナリで保存される

データメモリ

プログラムで利用するデータを保存することができる

3章で学んだメモリのように、読み込み・書き込みができる

命令メモリ

読み込みのみである

命令メモリとCPUは、以下のようなやりとりを行う

  1. 命令メモリを一つフェッチ
  2. CPUが命令をデコード・実行・次のアドレス計算
  3. 1に戻る(次のアドレスに対して)

CPU

CPUは、ALUとレジスタと制御ユニットで構成されている

ALU

3章で作ったもの。汎用的な演算装置

レジスタ

データメモリよりも高速にデータの保存・取得ができる領域

ただしデータメモリに比べはるかにサイズが小さい

データレジスタ=はやくて便利なメモリ?

アドレスレジスタ=読み書きに利用するためのアドレスを保存するレジスタ

プログラムカウンタレジスタ=現在実行している命令メモリのアドレスを保存するレジスタ

制御ユニット

CPUが命令をデコードするために必要なもの。

命令メモリを一つフェッチCPUが命令をデコード・実行・次のアドレス計算

ここまでを踏まえて、CPUの処理は、以下のように分割できる

  1. 命令メモリを一つフェッチ
  2. 制御ユニットが命令をデコード
  3. 命令を実行
  4. 次の命令メモリアドレスを計算

入力出力デバイス

全ての入出力デバイスはメモリマップドI/Oという仕様に従っている

キーボード=ベースアドレスが決められており、キーボードは常に入力値をベースアドレスに格納している。したがってCPUはベースアドレスを取得するだけでよい

スクリーン=ベースアドレスから描画領域分のアドレスの領域のメモリの値が画面に描画されると決められており、CPUはその領域のメモリの値を変更するだけで良い

理論(Hackハードウェア)

A命令

前章で紹介したが、

0xxxxxxxxxxxxxxxというフォーマットに沿う。

xxxxxxxxxxxxxxxの値がアドレスレジスタに保存される

C命令

前章で紹介したが、

111accccccdddjjjというフォーマットに沿う。

このフォーマットはALUのフォーマットと非常に近い。それに気づけるかどうか少し難しいところ。

Hackハードウェアの構成

  • 命令メモリ
  • CPU
  • データメモリ
    • RAM
    • メモリマップ(スクリーン)
    • メモリマップ(キーボード)

実装

データメモリ

データメモリは、RAMとスクリーンとキーボードで構成されている。

キモは、入力アドレスaddress[15]の値が、RAMかスクリーン(16384~24575)か24576(キーボード)かの判定部分。3パターンなのでDMux4Wayが使える

    // アドレス13,14で判断
    // address[14]=1 かつ address[13]=1 はキーボード
    // address[14]=1 かつ address[13]=0 はスクリーン
    // それ以外はRAM
    DMux4Way(in=load, sel[0]=address[13], sel[1]=address[14], a=isload-ram1, b=isload-ram2, c=isload-screen, d=isload-keyboard);

👇以下全文

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

    PARTS:

    // アドレス13,14で判断
    // address[14]=1 かつ address[13]=1 はキーボード
    // address[14]=1 かつ address[13]=0 はスクリーン
    // それ以外はRAM
    DMux4Way(in=load, sel[0]=address[13], sel[1]=address[14], a=isload-ram1, b=isload-ram2, c=isload-screen, d=isload-keyboard);

    Or(a=isload-ram1, b=isload-ram2, out=isload-ram);

    // RAM
    RAM16K(in=in, load=isload-ram, address=address[0..13], out=out-ram);

    // スクリーン
    Screen(in=in, load=isload-screen, address=address[0..12], out=out-screen);

    // キーボード
    Keyboard(out=out-keyboard);

    Mux4Way16(a=out-ram, b=out-ram, c=out-screen, d=out-keyboard, sel[0]=address[13], sel[1]=address[14], out=out);
}

CPU

最初はスイスイ行ったけどところどころハマった。👇以下全文

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:

    // CPU制御ユニット
    // a命令かc命令か
    // a-instruction
    // c-instruction
    Or(a=instruction[15], b=instruction[15], out=c-instruction);
    Not(in=c-instruction, out=a-instruction);

    // Dレジスタの保存はC命令の場合のみ
    And(a=instruction[4], b=c-instruction, out=isload-d);

    // instruction[4]はd2=>Dに保存するかどうか
    DRegister(in=alu-out, load=isload-d, out=out-d);

    // Aレジスタが保存するのは、A命令時の定数かC命令時の計算結果
    Mux16(a=alu-out, b=instruction, sel=a-instruction, out=in-a);

    // A命令でもC命令でも、結局のところAレジスタをloadするかどうか
    Or(a=instruction[5], b=a-instruction, out=isload-a);

    // instruction[5]はd1=>Aに保存するかどうか
    // outを切り取るのは問題ない??
    ARegister(in=in-a, load=isload-a, out[0..15]=out-a, out[0..14]=addressM);

    // instruction[12]はa。ALUのyはa=1ならM,a=0ならA
    // ALUにMを使うかAを使うか
    Mux16(a=out-a, b=inM, sel=instruction[12], out=aluin-y);

    // メモリの演算
    // 命令がそのまま流れる?
    ALU(x=out-d, y=aluin-y, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], out=alu-out, out[0..7]=alu-out1, out[8..15]=alu-out2, out[15]=alu-minus, out=outM, zr=alu-zr, ng=alu-ng);


    // Mに書き込み行うかどうか
    // CPUの領域外?
    // C命令の時のみ出力
    And(a=instruction[3], b=c-instruction, out=writeM);
    
    // jmp判定
    // 負の数はa-out[15]=1
    // 正の数はa-out[15]=0
    // 以下の変数を計算
    // alu-minus
    // alu-plus
    // alu-iszero
    Not(in=alu-minus, out=alu-plusorzero); //正の数または0
    Or8Way(in=alu-out1, out=temp1); // 0判定その1
    Or8Way(in=alu-out2, out=temp2); // 0判定その2
    Or(a=temp1, b=temp2, out=temp3); // 0判定その3
    Not(in=temp3, out=alu-iszero);
    And(a=alu-plusorzero, b=temp3, out=alu-plus);

    // カウンタ
    // C命令の場合のみ飛ぶのを忘れずに
    // j1, j2, j3の計算
    And(a=alu-minus, b=instruction[2], out=is-j1);
    And(a=alu-iszero, b=instruction[1], out=is-j2);
    And(a=alu-plus, b=instruction[0], out=is-j3);
    // 条件に合致するか
    Or8Way(in[0]=is-j1, in[1]=is-j2, in[2]=is-j3, out=is-jump);
    // なおかつ、C命令か
    And(a=is-jump, b=c-instruction, out=can-jump);
    // PC処理
    // incは基本true
    PC(in=out-a, load=can-jump, inc=true, reset=reset, out[0..14]=pc);
}

ハマったこと

j1, j2, j3の判定

alu-out(aluの出力結果)が[15]=trueの場合、alu-outが負の数と判断できる

=>Notをとれば、正の数かどうか判断できる

==> Not(in=alu-out[15], out=alu-plus)

これは正しくなく、alut-out[15]のNotを取ると、正の数か0かになります。なので、

Not(in=alu-out[15], out=alu-plusorzero)として

And(a=alu-plusorzero, b=temp3, out=alu-plus)で正の数と判定しないといけないので注意

DRegister/ARegisterのload

DRegisterloadは、 instruction[4]を見がちですが、A命令の場合も考慮して、以下のようにしましょう

    // Dレジスタの保存はC命令の場合のみ
    And(a=instruction[4], b=c-instruction, out=isload-d);

    // instruction[4]はd2=>Dに保存するかどうか
    DRegister(in=alu-out, load=isload-d, out=out-d);

ARegisterもだいたい同じ。isloadの条件が少し違うので注意

    // A命令でもC命令でも、結局のところAレジスタをloadするかどうか
    Or(a=instruction[5], b=a-instruction, out=isload-a);

    // instruction[5]はd1=>Aに保存するかどうか
    // outを切り取るのは問題ない??
    ARegister(in=in-a, load=isload-a, out[0..15]=out-a, out[0..14]=addressM);

Sub bus of an internal node may not be used

ALU(... , out=alu-out, out=outM, zr=alu-zr, ng=alu-ng);として

Or8Way(in=alu-out[0..7], out=temp1); // 0判定その1
Or8Way(in=alu-out[8..15], out=temp2); // 0判定その2
Or(a=temp1, b=temp2, out=temp3); // 0判定その3

とすると変数が使われてないかもよと怒られる。変数ちゃんと使ってるのにと思ったら同様のエラーの質問発見。

http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Sub-bus-of-an-internal-node-may-not-be-used-td4031198.html

正しくは、ALU(... , out=alu-out1, out[0..7]=alu-out1, out[8..15]=alu-out2, out=outM, zr=alu-zr, ng=alu-ng);として

    Or8Way(in=alu-out1, out=temp1); // 0判定その1
    Or8Way(in=alu-out2, out=temp2); // 0判定その2
    Or(a=temp1, b=temp2, out=temp3); // 0判定その3

としないといけない

PCのincはtrue?

ハマったわけではないけど、PCのincは常にtrueにしてるがこれでいいものか。。。

   // PC処理
    // incは基本true
    PC(in=out-a, load=can-jump, inc=true, reset=reset, out[0..14]=pc);