The Elements of Computing System - Ch.2 PJ

이 글은 insight 출판사의 [밑바닥부터 만드는 컴퓨팅 시스템 / The Elements of Computing System]이라는 책에 있는 프로젝트(과제) 를 수행하는 글입니다.
과제 수행을 위한 언어로 C#을 선택했지만, Java와 거의 유사하여 Java를 알면 쉽게 이해할만한 코드들이예요.

 

---

Chapter 2. Boolean Arithmetic - Project

이번 챕터에서는 컴퓨터가 수행하는 다양한 연산을 처리하는 Arithmetic Logic Unit을 만들어 CPU에 대해 이해하는 것이 목표였다.

 

이전 챕터에서 만든 간단한 게이트들을 기반으로 덧셈을 수행하는 Adder, Incrementer 등을 구현하고, 조건 Flag들에 따라 다양한 연산을 수행할 수 있는 ALU를 구현하였다. Ch.1에서 만든 게이트들은 Boolean 값 위에서 돌아가므로, 구현에 있어서 입력되는 숫자를 2진수로 변환한 뒤 1, 0 값을 Boolean의 참, 거짓 값으로 바꾸어 연산해주었다. 여러 Bit이 필요한 숫자의 경우 주로 16Bit를 나타내는 Boolean Array로 표현하였다.

 

Ch.1에서 만든 게이트 들은 Gates라는 namespace에 있는 BoolGate class에 담아주었었다. 그러나, Ch.2에서 만드는 칩들을 이 namespace에 함께 담기 위해서 아래와 같이 수정해주었다.

• Gates namespace -> CombinationalChips namespace
• BoolGate class -> BoolLogic
• Ch.2에서 만든 class : BoolOperation

 

반가산기 Half Adder

입력 : a, b
출력 : sum, carry
기능 : a, b 두 Bit을 더한다.
        sum은 a+b의 LSB, carry는 a+b의 MSB이다.

public  static  void HalfAdder(bool a,  bool b, out  bool sum,  out  bool carry)  {

    sum = BoolLogic.Xor(a,b);
    carry = BoolLogic.And(a,b);
} 

이 메서드를 사용하면 sum, carry 값을 parameter를 통해 받을 수 있지만, 단순히 a, b의 값으로 얻을 수 있는 sum만 받아오기에는 불편함이 있었다. 따라서 아래 전가산기에 들어가는 데이터를 반환해주기 위해서 public keyword를 붙이지 않고 Boolean 값을 return하는 두 가지 메서드를 더 만들어주었다.

static  bool HalfAdder_Carry(bool a,  bool b)  {

    return BoolLogic.And(a,b);
}

static  bool HalfAdder_Sum(bool a,  bool b)  {

    return BoolLogic.Xor(a,b);
}

물론 위 메서드를 사용하지 않고 Adder 내에서 변수로 처리를 하는 방법도 있었겠지만, 2개, 3개의 Bit을 더하는 단순한 계산을 할 때 마다 Boolean 변수를 4개 이상을 만들었다 없애는 게 효율적이지는 않을 것 같다는 생각이 들었다.

 

전가산기 Full Adder

입력 : a, b, c
출력 : sum, carry
기능 : a, b, c 두 Bit을 더한다. sum은 a+b+c의 LSB, carry는 a+b+c의 MSB이다.
여기에서 c는 아랫자리에서 올림이 발생했을 때 처리하기 위해 HA에서 추가된 것이다.

public  static  void FullAdder(bool a,  bool b,  bool c,  out  bool sum,  out  bool carry)  {

    carry = BoolLogic.Or(HalfAdder_Carry(a,b), HalfAdder_Carry(HalfAdder_Sum(a,b), c));
    sum = HalfAdder_Sum(HalfAdder_Sum(a,b), c);
}

FullAdder에서도 sum, carry 값만 따로 가져올 수 있는 메서드를 2개 만들어두었다. 이것 역시 public keyword를 제외하고 클래스 내부적으로만 사용할 수 있게 해두었다.

static  bool FullAdder_Carry(bool a,  bool b,  bool c)  {

    return BoolLogic.Or(HalfAdder_Carry(a,b), HalfAdder_Carry(HalfAdder_Sum(a,b), c));
}

static  bool FullAdder_Sum(bool a,  bool b,  bool c)  {

    return HalfAdder_Sum(HalfAdder_Sum(a,b), c);
}

 

가산기 Adder

입력 : a[16], b[16]
출력 : out[16]
기능 : out = a + b, 정수의 2의 보수 덧셈을 실행한다. overflow는 처리하지 않는다.

16Bit Adder는 단순하게 말하자면 Full Adder 16개를 서로 연결하여 쭉 나열해놓은 것이다. input 값인 a, b가 주소로 전달되었기 때문에 a, b의 값을 바꾸지 않기 위해 result라는 새로운 배열을 전달해주었다.

public  static  bool[] Add16(bool[] a,  bool[] b)  {

    bool[] result =  new  bool[16];
    bool carry =  false;

    for(int i =  0; i <  16; i++)  {
        result[i]  = FullAdder_Sum(a[i], b[i], carry);
        carry = FullAdder_Carry(a[i], b[i], carry);
    }

    return result;
}

 

증분기 Incrementer

입력 : input[16]
출력 : out[16]
기능 : out = input + 1, 1을 더하는 정수의 2의 보수 덧셈을 실행한다. overflow는 처리하지 않는다.

public  static  bool[] Inc16(bool[] input)  {

    bool[] one =  new  bool[16]  {true,  false,  false,  false,  false,  false,  false,  false,  
                                  false,  false,  false,  false,  false,  false,  false,  false};
    return Add16(input, one);
}

 

산술 논리 연산 장치 ALU

입력 : x[16], y[16], zx, nx, zy, ny, f, no
출력 : out[16], zr, ng
기능 : zx가 1이면 x = 0, nx가 1이면 x = !x
        zy가 1이면 y = 0, ny가 1이면 y = !y
        f가 1이면 out = x + y, 0이면 out = x & y
        no가 1이면 out = !out
        out이 0이면 zr = 1, 0이 아니면 zr = 0
        out < 0 이면 ng = 1, 아니면 ng = 0
        overflow는 처리하지 않는다.

이번 Chapter의 목적인 ALU까지 왔다. 이 ALU가 CPU안에서 연산처리를 담당하는 ALU이다. ALU는 16Bit의 데이터를 x, y로 받아들인다. zx, nx, zy, ny, f, no 6개의 Flag가 어떤 연산을 처리할 지를 결정하는 조건들이며, 이 Flag의 조합이 어떤가에 따라 64가지의 다른 연산을 처리한다.

 

대표적인 ALU의 연산들. 이것 말고도 총 64개의 연산이 있다.

public  static  bool[] ALU(bool[] x,  bool[] y,  
						   bool zx,  bool nx,  bool zy,  bool ny,  bool f,  bool no,
                           out  bool zr,  out  bool ng)  {

    bool[] result =  new  bool[16];
    bool[] ground =  new  bool[16]  {false,  false,  false,  false,  false,  false,  false,  false,  
                                     false,  false,  false,  false,  false,  false,  false,  false};


    //zx, nx
    x = BoolLogic.Mux16(x,  (bool[]) ground.Clone(), zx);
    x = BoolLogic.Mux16(x, BoolLogic.Not16(x), nx);

    //zy, ny
    y = BoolLogic.Mux16(y,  (bool[]) ground.Clone(), zy);
    y = BoolLogic.Mux16(y, BoolLogic.Not16(y), ny);

    bool[] temp1, temp2;

    temp1 = BoolLogic.And16(x,y);
    temp2 = Add16(x,y);

    // MUX에 의해 골라진 걸 result에 넣음
    result = BoolLogic.Mux16(temp1, temp2, f);

    // NO 조건 검사
    result = BoolLogic.Mux16(result, BoolLogic.Not16(result), no);

    // out
    ng = result[15];
    zr = BoolLogic.Not(BoolLogic.Or16Way(result));

    return result;
}

내가 구현한 ALU는 이렇게 생겼다. 간단하게 만든 ALU이기 때문에, 부동소숫점 연산 같은건 지원하지 않는다. 하지만 나중에 프로젝트를 진행하면서 SW적으로 처리하는 방법을 배우게 된다.

 

 

---

작동

값을 편리하기 넣기 위해서 DebugTool을 만들어서 테스트해주었다.

using  System;
using  CombinationalChips;
using  DebugTools;

class MainClass {
    public  static  void Main (string[] args)  {

        while(true)  {
            // A, B 값을 정수로 읽어서 16Bit의 Boolean Array로 바꾸어주고
            Console.Write("VA : ");
            int a =  int.Parse(Console.ReadLine());
            Console.Write("VB : ");
            int b =  int.Parse(Console.ReadLine());

            bool[] input = DebugTool.IntToBools16(a);
            bool[] input2 = DebugTool.IntToBools16(b);

            bool[] outValue =  new  bool[2];

            // Flag 값을 읽어서 6Bit의 Boolean Array로 바꾸어주고
            Console.Write("Flag : ");
            int flags =  int.Parse(Console.ReadLine());
            bool[] setValue = DebugTool.IntToBoolFlagReverse6(flags);

            // ALU에 값들을 넣어서 result에 받아오기
            bool[] result = BoolOperation.ALU(input, input2,
                                 setValue[0], setValue[1], setValue[2], setValue[3], setValue[4], setValue[5],
                                 out outValue[0],  out outValue[1]);

            // result와 zr, ng 를 확인
            DebugTool.PrintBools(result);
            Console.WriteLine("zr = {0}, ng = {1}\n", outValue[0], outValue[1]);
        }
    }
}

위 코드를 작동하여 아래와 같은 결과를 얻을 수 있었다. 위에서부터 차례대로 x+y, x-y, x&y이다.