아침 CS - (7) 가산기

가산기

지식인에 1 + 1이 뭐에요 라고 물어본 적이 있다. 중학교 1학년때였다.

답변은…의외로 고퀄리티다. 솔직히 지금 읽어도 완전히 이해되진 않지만, 핵심은 모든 자연수는 연속된다. 바로 다음 수가 같다면 자연수는 같은 수이다 라는 대전제를 통해 1 + 1을 풀이해 주신 것으로 생각된다.

컴퓨터 프로그램이란 별 거 아니다, 더하고 빼고 곱학고 나누고 하는거다 라는 누군가 했는지 잘 기억나지 않는… 명언이 있다. 결국 누군가가 컴퓨터 안에서 더하고 빼고 곱하고 나누는 작업을 수행해줘야 로직을 작동시킬 수 있는 것이다. 우리는 그런 역할을 수행하는 주체가 CPU임은 상식으로 알고 있지만, 생각해보면 CPU가 어떤 원리로 사칙 연산을 수행하는지는 고민해본 적이 별로 없다.

CPU는 어떻게 1 + 1을 수행하는가? 오늘은 가산기에 대해 알아보자.

반가산기

반가산기는 이진수의 한자리수를 연산한다. 만약 자리올림이 필요하다면, 자리올림수 출력에 따라 출력한다.

입력 (A, B)	자리올림수, 출력(C. S)
0, 0	0, 0
0, 1	0, 1
1, 0	0, 1
1, 1	1, 1

전가산기

반가산기를 통해 연산한 자릿수를 포함해 연산한다.

하위 자리올림수 출력을 받아 상위 입력으로 연결하는 것이다. 초등학생 덧셈 공부하듯…..

하나의 전가산기는 두 개의 반가산기와 하나의 OR 로 이뤄진다고 한다.

입력 (A, B, 자리올림 입력)	출력(자리올림 출력, 출력)
0, 1, 1	1, 0
1, 1, 1	1, 1
1, 0, 0	0, 1
1, 0, 1	1, 0
1, 1, 0	1, 0

A, B 입력을 일단 한 번 반가산기에 올린 후, 자리올림수 값과 출력값을 받는다. 받은 출력값을 두 번째 반가산기에 연결시킨다.

두 번째 반가산기에는 첫번째 반가산기의 결과값과 처음에 받았던 자리올림 입력을 넣으면 된다. 두 번째 반가산기의 출력이 출력값(S)이 되고, 자리올림수는 두 반가산기의 자리올림 출력을 OR 연산하면 된다.

아니 그럼, 뺄셈은 어떻게 하나?

변속레버를 R에 놓으면 차가 뒤로 가듯 가산기를 거꾸로 돌리면 뺄셈이 된다.

입력 A, B는 피감수와 감수로, (감산을 당한다는 뜻일 게다.)

자리올림수는 빌림수가 된다. 낮은 위치에서 1을 한 개 꿔 와 감산하고, 다음 비트 연산에 반영하는 것이다. 출력은 차이수(D)와 빌림수로 한다.

아니 그럼, 곱셈은 어떻게 하나?

초등학생 때로 돌아가보자. 당신이 파인만이나 토발즈 급의 천재가 아니었다면 나처럼 엄마한테 볼기짝을 맞아가며 구구단을 공부했을 것이다.

구구단은 외워주는 것이 제맛이지만 평가 시간만 되면 까먹기 마련이므로 둔부를 맞지 않기 위한 일련의 방책을 준비해 두는 것이 가장 좋다.

즉 8 * 5 , 4 * 5 와 같이 암기하기 간편한 값을 캐싱해 두고 그 이후의 단수는 캐시된 값에 피승수를 더해가며 계산하는 것이 좋다. 4 5는 20! 이므로 4 6 은 20 + 4, 24가 되는 것이다.

컴퓨터의 곱셈도 마찬가지다. 앞서 살펴본 가산기를 통해 컴퓨터가 덧셈을 처리하는 방식은 알았으니, 컴퓨터가 덧셈을 처리하는 방식에 대한 이견은 없을 것 같다. 다만 멍청한 컴퓨터를 위해 그가 지금까지 몇 번 덧셈을 수행했는지를 알려줄 부품이 필요할 것이다. 체육시간에 앉아번호 할 때 꼭 지 번호 까먹는 놈들이 있지 않았던가. 이런 부품을 계수기(counter)라고 한다.

다만 이런 방식의 곱셈은 엄청난 문제가 있다. 19 * 19 정도의 연산이면 문제가 전혀 없다. 문제는 자릿수가 엄청나게 커지면 커질 수록 연산의 비용도 커진다는 것이다.

이런 방식의 곱셈 연산은 O(2^n)의 시간복잡도를 갖는다.

그래서 이런 방식을…

이진수 곱셈

사실 이진수의 곱셈은 십진수보다 쉽다. 승수가 0 아니면 1 둘중에 하나기 때문에 피승수 혹은 0을 한 칸씩 왼쪽으로 옮긴 후 각 행별로 가산 연산을 해주면 된다. 위 그림처럼 말이다.

왼쪽으로 한칸씩 옮기는 과정을 시프팅(shifting)이라고 부르고, 이를 수행하는 연산 유닛을 시프터(shifter)라고 한다. 곱셈 회로는 시프터와 가산기만 있으면 만들 수 있다. 또 시간 복잡도는 O(N)으로 대폭 개선된다. 32비트 이진수를 곱해도 32번의 시프팅과 32번의 가산 연산만 하면 계산할 수 있는 것이다.

아니 그럼, 나눗셈은 어떻게 하나?

다행히 우리 엄마는 나눗셈을 못한다고 나를 혼내진 않았다. 그래서 나눗셈을 쉽게 할 방법은 별로 고민하지 못한 것 같다.

그러나 라이프니츠나 폰 노이만 같은 분들은 고민했을 것이다.

나눗셈도 단순히 생각하면 곱셈의 단순한 방법과 같이 피제수에서 제수를 정해진 횟수만큼 빼면 되지만 그랬다간 O(2^n)을 피할 수 없을 것이다.

이진 나눗셈

오른쪽 쪽지는 무시해라.

곱셈과 같은 방식으로 한 행씩 감산 연산을 해 나가면 된다. 제수를 피제수의 첫 세자리에서 빼고, 한 칸씩 오른쪽으로 가며 같은 연산을 수행하면 된다. 피제수의 남은 숫자가 제수보다 작아질 때까지.

시프터를 거꾸로 돌리고 감산 회로만 있으면 나눗셈도 O(N)에 수행할 수 있고, 제수와 피제수의 자릿수가 일치하는 최상의 경우에는 O(1)로도 가능하다(감산 한 번).

참고 문헌

가산기

[MCU강의⑤] CPU 실행방법… 덧셈·뺄셈·곱셈·나눗셈 어떻게?

….이외에 집에 굴러다니던 과학 교재, 수학책, 정처기 교재 등…..