NandToTetris-Hardware simulator / Adder, Inc ,ALU 실습 (밑바닥부터 만드는 컴퓨팅 시스템)

컴퓨터 내부에서 모든것은 2진코드로 표현되며,

레지스터의 wordsize(cpu가 한번에 처리 할 수 있는 단위)에 따라 처리할 수 있는 데이터의 단위가 결정됩니다.

cpu아키텍쳐에 따라 wordsize가 32bit라면 4바이트, 64bit라면 8바이트의 단위를 한번에 처리 할 수 있습니다.

 

예를들어 어떤 컴퓨터가 8bit wordsize를 가졌다면 총 255까지의 숫자를 표현 할 수 있지만, 음수는 표현할 수 없습니다.

이번 글에서는 컴퓨팅 시스템에서 제한된 비트 안에서 어떻게 음수를 표현하는지, 그리고 단순한 가산기부터 ALU를 만드는 실습까지 진행해보려 합니다.

 

컴퓨터에서의 2진수 처리

덧셈

오른쪽에서 끝 비트인 최하위 비트(least significant bit, LSB)부터 최상위 비트 (most significant bit, MSB)까지 각각 숫자를 더해

더해 2가되면 자리올림비트 (CarryBit)를 만들어 다음자리수에 올려 계산해줍니다.

만약 최상위 비트(MSB)에서 자리올림(오버플로)이 발생한다면 사용하는 bit수에 맞게 버림 처리를 합니다.

 

2진수의 음수표현과 2의 보수법

2의 보수법

대부분의 컴퓨터에서는 이진수의 음수를 표현하기 위해 2의 보수법을 활용합니다.

보수를 구한다는건 각 양수에 대응하는 음수를 구한다는 의미입니다.

1의 보수로 음수 표기를 하게되면 음의 0, 양의 0이 존재하기에 컴퓨터에서는 2의 보수법을 사용합니다.

 

예를들어 4bit 2진법 쳬계에서 음수 x를 표현하는 이진코드는 "2^4 - x" 로 나타내게됩니다.

-7을 이진수로 나타낸다면 "2^4-7"이고 십진법으로 계산했을때는 "9", 이진법으로는 1001입니다.

7은 이진법으로 0111이기에 "1001 + 0111 = 0000"이 되어 2의 보수임을 확인 할 수 있습니다.

 

간단하게 2의 보수를 찾으려면, 모든 bit에 대해서 1의보수(0을 1로, 1을 0으로)를 취한 다음 1을 더해주면 됩니다.

부호비트 (sign bit)

 

컴퓨터에서는 음수를 표현하기 위해 비트의 가장 왼쪽 비트(MSB)를 부호비트(sign bit)로 사용합니다.

만약 부호비트가 1이라면 음수, 0이라면 양수가 됩니다.

양수만 표현한다면 4비트는 0부터 15까지의 16개의 수를 표현 할 수 있고,

부호비트를 사용한다면 16개의 절반을 음수를 위해 할당합니다. 

즉 4비트 안에서 음수까지 표현해야한다면 위의 표와 같이 -8부터 7까지 표현 할 수 있게됩니다. 

 

반가산기

컴퓨터에서 덧셈을 하기 위한 첫 단계로,

두 비트를 더해서 결과 값으로 합(Sum)과 자리올림(Carry)를 bit를 산출합니다.

Xor 과 And 연산을 이용해서 만들 수 있습니다.

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

 

전가산기

3개의 비트를 계산하는 가산기입니다.

출력은 반가산기와 동일하게 carry, sum을 산출합니다.

HalfAdder와 Or를 통해서 만들 수 있습니다.

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 가산기

16bit 가산기입니다.

2개의 16bit수를 계산할 수 있습니다.

해당 책에서는 오버플로우는 무시합니다.

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=carry0);
    FullAdder(a=a[1], b=b[1], c=carry0, sum=out[1], carry=carry1);
    FullAdder(a=a[2], b=b[2], c=carry1, sum=out[2], carry=carry2);
    FullAdder(a=a[3], b=b[3], c=carry2, sum=out[3], carry=carry3);
    FullAdder(a=a[4], b=b[4], c=carry3, sum=out[4], carry=carry4);
    FullAdder(a=a[5], b=b[5], c=carry4, sum=out[5], carry=carry5);
    FullAdder(a=a[6], b=b[6], c=carry5, sum=out[6], carry=carry6);
    FullAdder(a=a[7], b=b[7], c=carry6, sum=out[7], carry=carry7);
    FullAdder(a=a[8], b=b[8], c=carry7, sum=out[8], carry=carry8);
    FullAdder(a=a[9], b=b[9], c=carry8, sum=out[9], carry=carry9);
    FullAdder(a=a[10], b=b[10], c=carry9, sum=out[10], carry=carry10);
    FullAdder(a=a[11], b=b[11], c=carry10, sum=out[11], carry=carry11);
    FullAdder(a=a[12], b=b[12], c=carry11, sum=out[12], carry=carry12);
    FullAdder(a=a[13], b=b[13], c=carry12, sum=out[13], carry=carry13);
    FullAdder(a=a[14], b=b[14], c=carry13, sum=out[14], carry=carry14);
    FullAdder(a=a[15], b=b[15], c=carry14, sum=out[15], carry=carry15);
    
}

 

증분기

주어진수에 1을 더합니다.

추가로 컴퓨터 아키텍쳐를 설정 할 때,

주어진 숫자에 1을 더하는 칩이 있는게 편리합니다.

 

만약 b에 값을 설정하지 않으면 모두 '0'인 bit입니다

그렇기에 b[0], b의 가장 오른쪽 비트 MSB를 1로 변경합니다.

CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
    Add16(a=in, b[0]=true, out=out);
}

ALU (산술논리장치)

cpu의 계산을 담당하는 부분입니다.

두 수의 덧샘, 뺄셈, 불 연산 등등 연산을 할 수 있는 칩입니다.

입력은 x,y 두개와 6개의 제어비트 zx, nx, zy, ny, f, no가 있습니다.

 

zx가 1이면 x를 0으로 만들고, nx가 1이면 x를 반전시킵니다.

zy, ny는 y에 대해서 1이면 y를 0으로 만들고, ny가 1이면 y를 반전시킵니다.

f가 1이면 변환된 x와 y를 ADD하고, 0이면 AND 연산을 합니다. no가 1이면 반환 값을 반전시킨다. 

 

zr은 위에서 계산한 결과가 0이면 True, ng는 위에서 계산한 결과가 음수이면 True입니다.

 

(해당 책에서 만드는 cpu는 곱셈연산이 없습니다.)

CHIP ALU {
    IN  
        x[16], y[16],         
        zx, 
        nx, 
        zy, 
        ny, 
        f, 
        no;
    OUT 
        out[16], 
        zr,      
        ng;      

    PARTS:
    Not16(in=x, out=notX);
    Not16(in=y, out=notY);

    Mux4Way16(a=x, b=notX, c=false, d=true, sel[0]=nx, sel[1]=zx, out=newX);
    Mux4Way16(a=y, b=notY, c=false, d=true, sel[0]=ny, sel[1]=zy, out=newY);
    
    Add16(a=newX, b=newY, out=addXY);
    And16(a=newX, b=newY, out=andXY);

    Mux16(a=andXY, b=addXY, sel=f, out=MuxOut);
    Not16(in=MuxOut, out=notMuxOut);
    
    Mux16(a=MuxOut, b=notMuxOut, sel=no, out=out, out[15]=ng, out[0..7]=left, out[8..15]=right);

    Or8Way(in=left, out=orWayOut1);
    Or8Way(in=right, out=orWayOut2);
    Or(a=orWayOut1, b=orWayOut2, out=orOut);
    Not(in=orOut, out=zr);
}