「コンピュータシステムの理論と実装」に載ってたCPUを実装してみる

#はじめに
[コンピュータシステムの理論と実装](https://www.oreilly.co.jp/books/9784873117126/)の5章の演習問題に従い、CPUを実装しました。

いっぺんに考えると頭の中混乱したので、ひとつひとつ整理し考えました。
整理することでCPUの理解も深まったので内容を記事として残したいと思います。
また、この演習問題を解くにあたってのヒントになれば幸いです。

# 注意事項
本記事は「コンピュータシステムの理論と実装」を読んでいる前提で記述します。
読んでいなくても何となくCPUの動作について理解できるとは思いますが、
知らない固有名詞とかも出てきますので、そのあたりはご了承ください。

#実装の前に
## CPUのInput、Outputに関して

#### Input3種類
1. InM[16]：addressMが指す**データメモリ**の値
2. instruction[16]：PC(プログラムカウンタレジスタ)の出力(アドレス)が指す**命令メモリ**の値
3. reset：プログラムカウンタレジスタの値をリセットするか否か

#### Output4種類
  1. OutM[16]：ALUの計算した出力
    - writeMがtrueの場合に、addressM[15]が指す**データメモリ**にOutM[16]の値が書き込まれる
  - writeM：outM[16]をMに書き込むか否か
    - 以下の2つの条件のANDをとったもの
      1. 命令(instruction)の16ビット目 (A命令かC命令か)
      2. 命令の5ビット目(d3:Mに出力するかどうか)
  - addressM[15]:Mを指し示すための**データメモリ**のアドレス値
    - Aレジスタの値がそのまま入る
  - pc[15]:次の命令を表す**命令メモリ**のアドレス
    - ALUの出力や、命令(instruction)によって変化する

## CPU内の各装置について

#### MUX0
  - Aレジスタへの入力をinstructionの値にするか、ALUの出力にするかを決める(**Aレジスタがloadするか否かは考えない**)
  - Aレジスタへの入力がALUの出力となるのは、instructionがC命令(`instruction[15]=true`)かつ、`instruction[5]=true`の場合
  - それ以外の場合は、instruciton[0..15]の値をAレジスタの入力とする
  - つまり`instruction[15] && instruction[5]`を**selectorビット**としてAレジスタの入力を切り替える
 
#### Aレジスタ

- MUX0で指定されたAレジスタへ入力値をloadするか否か
- `instruction[15]=false`の場合は、A命令でなのでinstructionの値をAレジスタに書き込む
- C命令(`instruciton[15]=true`)かつ、`instruction[5]=true`の場合はALUの出力を書き込む
- つまり`Not(instruction[15]) || (instruction[15] &&instruction[5])`を**loadビット**とする
    - 何を書き込むかはその前のMUX0で判断してくれてるのでレジスタは気にする必要なし

#### MUX1

- ALUの入力を決めるためのマルチプレクサ
- Aレジスタの値をそのまま入力とするか、それともM(Aレジスタの値が指すデータメモリの値)を入力とするかを決める
- どちらを選択するかは、ALUがどのような計算をするか(C命令のComp部分)に依存する
- Comp部分はALUでどのような計算を行うかを指定するものであり、Aを使うかMを使うかが示されている
- 命令がC命令を前提とし、instruction[12]が0の場合はAの値を利用し、1の場合はMの値を利用する
- つまり`instruction[15] && instruction[12]`を**selecotrビット**とする

#### Dレジスタ

- DレジスタにALUの出力結果をloadするか否か
- 命令がC命令で、instruction[4]が立っていればDビットにALUの出力をロードする
- つまり`instruction[14] && instruction[4]`が**loadビット**となる

#### ALU
ALUに関してはこちら→[CPUの演算処理を司るALUの仕組み](https://qiita.com/satodayo/items/755672aa44acdec1e66e)

- 入力されたDレジスタの値と、A or M(MUX2の出力)に対しててどのような計算を行うか
- 計算方法の指定はc1-c6までの6ビットで決められる
- selector(?)は`instruction[6..11]`

#### PC

- 次のinsutructionの値となる、命令メモリのアドレスを指定する

- 今回のPCの仕様として、以下の優先度の高いものから実行される。
  1. inputのresetが`true`であれば初期値のアドレスをロードして出力
  2. jumpする条件を満たしていれば**Aレジスタ**の値をロードして出力
  3. 現在の値をインクリメントして出力
- jumpする条件に関してはALUの出力(ng,zr)とinstructionの値に依存する。
- まずinstructionがC命令である場合、instruction[0..2]の値によりjump条件が異なる
    - jumpする条件は、ALUの出力(out)がout=0,out≠0,out<0,out<=0,out>0,out>=0の6パターンで場合分け可能である
    - この条件に対し、ALUの出力ビットng(out<0)とzr(out=0)を利用し、判別する
    - jumpする条件を満たした場合にPCのloadビットが`true`となるよう実装し、その場合にAレジスタの値が出力される
- instructionがA命令である場合、もしくはjump条件を満たさない場合は`3.インクリメント`された値が出力される

# 実装してみた

以上の内容を踏まえ実装を行いました。
上記のことが理解できていれば、あとは書いていくだけかと思います。
一応テスト通ってますが、何かミスがあれば指摘お願いします。

```hack:CPU.hdl
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:
    //Mux0
    And(a=instruction[15], b=instruction[5], out=AloadALU);
    Mux16(a=instruction, b=ALUout, sel=AloadALU, out=Mux0out);

    //ARegister
    Not(in=instruction[15], out=notA);
    Or(a=notA, b=AloadALU, out=loadA);
    ARegister(in=Mux0out, load=loadA, out=ARegout, out[0..14]=addressM);

    //Mux1
    And(a=instruction[15], b=instruction[12], out=loadM);
    Mux16(a=ARegout, b=inM, sel=loadM, out=Mux1out);

    //DRegister
    And(a=instruction[15], b=instruction[4], out=DloadALU);
    DRegister(in=ALUout, load=DloadALU, out=DRegout);

    //ALU
    ALU(x=DRegout, y=Mux1out, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], out=ALUout, out=outM, zr=zr, ng=ng);

    //writeM
    And(a=instruction[15], b=instruction[3], out=writeM);

    //ProgramCounter
    And(a=zr, b=instruction[1], out=load0);
    And(a=ng, b=instruction[2], out=load1);

    Not(in=zr, out=nzr);
    Not(in=ng, out=nng);
    And(a=nzr, b=nng, out=positive);
    And(a=positive, b=instruction[0], out=load2);

    Or(a=load0, b=load1, out=load01);
    Or(a=load01, b=load2, out=load012);
    And(a=load012, b=instruction[15], out=jump);

    Not(in=load012, out=notjump);
    Or(a=notjump, b=notA, out=incPC);

    PC(in=ARegout, load=jump, inc=incPC, reset=reset, out[0..14]=pc);
}
```

## 余談

[クロック周波数とランダムアクセスメモリの性質について](https://qiita.com/satodayo/items/e936e3448971120c41d9)の記事に関連して。
今回Aレジスタ、Dレジスタ、PCレジスタが順序回路となっています。
これらが存在することにより中途半端な値がメモリに書き込まれることが防がれているのだなと、実感しました。

##まとめ
ひとつひとつかみ砕いていくとCPUがどのように動作しているかを理解することができました。

今回の実装はあくまで書籍に出てくるHackコンピュータというプラットフォーム上での実装でしたが、
どんなCPUも根本の動作原理は同じかと思うので、今回の知識を踏まえて学習の方を進めていきたいと思います。