コンピュータシステムの理論と実装を読んだ


普段はアプリケーション開発をメインでやっていますが,最近コンピュータやOS自体の仕組みに興味が湧き,低レイヤーの勉強も片手間で進めています.

ネット上でも評判の高かった『コンピュータシステムの理論と実装』を読んだので,メモを残しておきます.

各章を進めていくことで,低レイヤからアプリケーションまでコンピュータの全体像を俯瞰することができるようになりました.1128

1章 ブール論理

1章では,前半部で基本的なブール理論について学び,後半では付属のハードウェアシミュレータを用いて,ゲートの記述を行います.ここではNandゲートを用いて,他のゲートを表現します.

1.ブール代数

1.1.ブール関数

1.2. 正準表現

2. ゲート

1ビット

  ・Not
  ・And
  ・Or
  ・Nand
  ・Xor
  ・Mux
  ・DMux

多ビット

3. 実装

入力1ビット

  CHIP Not {
      IN in;
      OUT out;
  
      PARTS:
      Nand(a=in, b=in, out=out);
  }
  CHIP And {
      IN a, b;
      OUT out;
  
      PARTS:
      Nand(a=a, b=b, out=out1);
      Not(in=out1, out=out);
  }
  CHIP Or {
      IN a, b;
      OUT out;
  
      PARTS:
      Not(in=a, out=w1);
      Not(in=b, out=w2);
      Nand(a=w1, b=w2, out=out);
  }
  CHIP Xor {
      IN a, b;
      OUT out;
  
      PARTS:
      Nand(a=a, b=b, out=w);
      Nand(a=a, b=w, out=w1);
      Nand(a=b, b=w, out=w2);
      Nand(a=w1, b=w2, out=out);
  }
  CHIP Mux {
      IN a, b, sel;
      OUT out;
  
      PARTS:
      Not(in= sel, out=notsel);
      And(a=notsel, b=a, out= l);
      And(a=sel, b=b, out=r);
      Or(a=l, b=r, out=out);
  }
  CHIP DMux {
      IN in, sel;
      OUT a, b;
  
      PARTS:
      Not (in=sel, out=notsel);
      And (a=in, b=notsel, out=a);
      And (a=in, b=sel, out=b);
  }

入力16ビット

多入力多ビット

  CHIP Mux4Way16 {
      IN a[16], b[16], c[16], d[16], sel[2];
      OUT out[16];
  
      PARTS:
      Mux16(a=a, b=b, sel=sel[0], out=w1);
      Mux16(a=c, b=d, sel=sel[0], out=w2);
      Mux16(a=w1, b=w2, sel=sel[1], out=out);
  }

多出力多ビット

  CHIP Mux4Way16 {
      IN a[16], b[16], c[16], d[16], sel[2];
      OUT out[16];
  
      PARTS:
      Mux16(a=a, b=b, sel=sel[0], out=w1);
      Mux16(a=c, b=d, sel=sel[0], out=w2);
      Mux16(a=w1, b=w2, sel=sel[1], out=out);
  }

4.まとめ

5. 参考文献

・カルノー図による論理関数の簡単化

・ひとりNand2Tetris(1) -NANDから他のゲートを作る

ikenox/nand2tetris

2章 ブール算術

1. 符号付き2進数

2. 加算器(Adder)

2.1. 半加算器(Half Adder)

2.2. 全加算器(Full Adder)

2.3. 加算器(Add16)

2.4. インクリメンタ

2.5 ALU

  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:
      Not16(in=x, out=nx1);
      Mux4Way16(a=x, b[0..15]=false, c=nx1, d[0..15]=true, sel[1]=nx, sel[0]=zx, out=w1);
  
      Not16(in=y, out=ny1);
      Mux4Way16(a=y, b[0..15]=false, c=ny1, d[0..15]=true, sel[1]=ny, sel[0]=zy, out=w2);
  
      Add16(a=w1, b=w2, out=w3);
      And16(a=w1, b=w2, out=w4);
  
      // out = x + y (if 1) or x & y (if 0)
      Mux16(a=w4, b=w3, sel=f, out=w5);
  
      // no
      Not16(in=w5, out=w6);
  
      // out
      Mux16(a=w5, b=w6, sel=no, out=out, out[15]=ng, out[0..7]=orw1, out[8..15]=orw2);
  
      Or8Way(in=orw1, out=w7);
      Or8Way(in=orw2, out=w8);
      Or(a=w7, b=w8, out=w9);
      Not(in=w9, out=zr);
  }

3章 順序回路

comments powered by Disqus