2. Boolean Arithmetic - [밑바닥부터 만드는 컴퓨팅 시스템]

이 글은 insight 출판사의 [밑바닥부터 만드는 컴퓨팅 시스템 / The Elements of Computing System]이라는 책에 있는 프로젝트(과제) 를 수행하는 글입니다. 해외에서는 Nand2Tetris라는 이름으로 잘 알려져있는 프로젝트입니다. 내용은 동일하니 참고해주세요!

 

Chapter 2의 Project 글 보러가기

---

 

목표는 ALU 완성하기 - CPU에 대한 이해
2진코드 불연산으로 더하기 → 가산기 칩에 대한 이해 (Adder) → 구현해보기

배경

2진수

컴퓨터는 수를 2진수로 다룬다.
19라는 수를 나타내고자 하면 10011(2진수) = 2^4×1 + 2^3×0 + 2^2×0 + 2^1×1 + 2^0×1 으로 나타날 것이다.
더 정확히, 64비트 컴퓨터의 레지스터에는 0000000000000000000000000000000000000000000000000000000000010011로 저장될 것이다!

 

2진 덧셈

두 이진수를 더할 때는 LSB부터 MSB까지 순서대로 더한다.

LSB Least Significant Bit - 최하위 비트

MSB Most Significant Bit - 최상위 비트

계산이 끝나고 자리올림수가 0이면 계산종료, 1이면 overflow가 발생한 것.

1001 + 0101 = 1110
1011 + 0111 = 10010 (overflow가 발생)

논리게이트로 덧셈을 만들기 위해서 3개의 비트를 합산하는 게이트를 만들면 된다. ( 두 수 + 자리올림 수 )

 

부호가 있는 2진수

부호를 나타내기 위해 대부분의 컴퓨터는 2의 보수(2's complement) 방식을 이용한다.

X의 보수 = 2^n-X (x가 0이 아닌 경우) // 0 (x가 0인 경우)
수를 0은 1로, 1은 0으로 뒤집은 뒤 +1 해주면 된다.
양수는 MSB가 0, 음수는 1로 시작한다.

 

2진수를 이용하면 산술연산 Arithmetic 과 논리연산 Logic 을 동시에 담을 수 있다!

 

명세

반 가산기 Half-Adder

두 Bit을 더한다

전 가산기 Full-Adder

세 Bit을 더한다

가산기 Adder

정수의 덧셈을 처리한다
Overflow에 대한 처리는 불가능하다
디바이스의 종류에 따라 16/32/64 Bit의 가산기를 사용한다

증분기 Incrementer

주어진 수(input)에 1을 더한다
Overflow에 대한 처리는 불가능하다

산술논리연산장치 ALU - Arithmetic Logic Unit

16bit 아키텍쳐의 ALU를 만들어보자고 가정해보자.
6가지 조건Bit을 통해 2^6^가지 계산이 가능하다.

1. ZX X입력값을 0으로
2. NX X입력값을 반전 (NOT)
3. ZY Y입력값을 0으로
4. NY Y입력값을 반전 (NOT)
5. F 1이면 ADD(X,Y) 0이면 AND(X,Y)
6. NO OUT값을 반전시킨다
   1,2는 X의 전처리, 3,4는 Y의 전처리, 6은 결과의 후처리를 위한 BIT이다.

ZR OUT이 0이면 true
NG OUT이 음수이면 true
연산결과를 이용하기위해 옵션을 체크할때 사용되는 BIT이다. 결과와 함께 set된다.

가능한 간단하게 연산을 설계하여 단순하고 명쾌한 ALU를 만들어낸다!

 

구현

반가산기 HA

전가산기 FA

가산기 Adder

증분기 Incrementer

ALU

Adder와 멀티버스 And게이트로 산술연산이 가능하다.
ZX,NX,ZY,NY에 해당하는 게이트 만들기
F에 의해 두 연산이 선택되도록 만들기
NO에 따라 멀티버스 NOT게이트 만들기
연산결과에 따른 플래그 반환하기
이를 통해 간단한 ALU를 만들 수 있다!

정리

멀티비트 가산기의 표준적인 방법 ... 효율성은 낮다. (맨 아랫자리부터 맨 앞자리까지 시간 지연이 발생) 고급ALU에서는 자리올림수 예측기법-Carry look-ahead technique를 통해 개선이 가능하다. (저수준의 연산 개선을 통해 전체적인 성능 향상이 가능하다)

 

고급 ALU에서는 소숫점, 곱셈, 나눗셈까지 가능하다. 그러나 우리는 HW를 간단히 설계하고 SW로 이를 커버치면서 설계해나갈 것이당!

---

Chapter 2의 Project 글 보러가기