정수 덧셈의 오버플로와 곱셈 하드웨어 — 2의 보수에서 세 가지 곱셈 설계까지

1. add 한 줄의 안쪽

앞 글에서 add $t0, $s1, $s2를 32비트로 바꿔 봤습니다. 명령어를 읽는 법은 알았지만, 프로세서 안에서 그 덧셈이 실제로 어떻게 일어나는지는 보지 않았습니다. 이 글은 그 안쪽입니다. 32비트 두 개를 더하면 자리가 넘칠 수 있습니다. 그때 MIPS가 무엇을 하는지 봅니다. 그다음은 곱셈입니다. 첫 글에서 mult의 결과가 Hi와 Lo 두 레지스터에 나뉘어 담긴다고만 하고 지나갔습니다. 왜 나뉘는지, 곱셈 회로를 세 가지 설계로 차례로 보면서 확인합니다.

2. 2진수 읽기와 덧셈

십진수는 자리마다 1, 10, 100으로 커집니다. 2진수는 오른쪽 끝자리부터 1, 2, 4, 8입니다. 규칙은 하나입니다. 그 자리의 값을 쓰면 1, 안 쓰면 0을 적습니다. 그래서 0111은 4와 2와 1을 쓴 것이니 7이고, 0110은 6입니다. 반대로 13을 바꾸려면 큰 자리부터 봅니다. 8을 쓰면 5가 남고, 4를 쓰면 1이 남고, 2는 남은 1보다 크니 0, 마지막 자리에 1을 쓰면 남는 값이 없습니다. 1101이 됩니다.

이제 7 더하기 6을 2진수로 합니다. 방법은 십진수 덧셈과 같습니다. 오른쪽 끝자리부터 더하고, 한 자리에 안 들어가면 왼쪽으로 올립니다. 이 올라가는 것을 자리올림이라고 부릅니다.

  0111   (7)
+ 0110   (6)
------
  1101

첫째 자리는 1 더하기 0이니 1입니다. 둘째 자리는 1 더하기 1이라 2가 되는데, 2진수에서 2는 한 자리에 못 들어가니 0을 쓰고 1을 올립니다. 셋째 자리는 1 더하기 1에 올라온 1까지 세 개라 1을 남기고 1을 또 올립니다. 넷째 자리에는 올라온 1만 있으니 1입니다. 부호 없이 읽으면 8 더하기 4 더하기 1, 13입니다.

3. 음수는 2의 보수로

컴퓨터는 음수도 같은 레지스터에 담아야 합니다. 빼기 기호를 따로 넣을 자리가 없습니다. 그래서 맨 앞 비트를 부호로 쓰기로 합니다. 0이면 양수, 1이면 음수입니다. 이 규칙을 적용하는 순간 같은 비트열이 다르게 읽힙니다. 방금 나온 1101은 부호를 안 볼 때는 13이지만, 부호가 있다고 보면 맨 앞이 1이니 음수입니다. 둘 중 어느 쪽으로 읽을지는 명령어가 정합니다.

부호 있는 수에서 음수를 만드는 방법을 2의 보수라고 부릅니다. 모든 비트를 뒤집고, 거기에 1을 더합니다. 5는 0101이고, 뒤집으면 1010, 1을 더하면 1011이 마이너스 5입니다. 0101과 1011을 더하면 자리올림이 맨 앞까지 올라가는데, 네 자리를 넘어간 자리올림은 레지스터 밖이라 버려집니다. 남는 네 자리는 0000이니 맞습니다.

거꾸로도 씁니다. 1101을 뒤집으면 0010, 1을 더하면 0011, 3입니다. 그러니 1101은 마이너스 3입니다. 이렇게 정해 두면 뺄셈 회로를 따로 만들 필요가 없습니다. 빼기는 부호를 뒤집어서 더하는 것입니다.

4. 오버플로와 그 조건

부호 규칙을 정하면 담을 수 있는 범위가 따라서 정해집니다. 4비트라면 부호에 한 자리를 쓰고 값에는 세 자리가 남습니다. 양수 쪽은 0이 한 자리를 차지하니 1부터 7까지, 음수 쪽은 마이너스 1부터 마이너스 8까지입니다. 음수 쪽이 하나 더 넓습니다. 32비트도 똑같이 한 자리가 부호, 서른한 자리가 값이라 −2³¹부터 2³¹−1까지, 대략 마이너스 21억에서 21억입니다.

계산 결과가 이 범위를 벗어나는 것을 오버플로라고 합니다. 오버플로는 단순히 자리가 모자란 상태가 아닙니다. 값이 자라다가 맨 앞 부호 자리를 침범한 상태입니다. 그래서 결과의 부호가 뒤집힙니다.

• 양수끼리 더했는데 결과의 맨 앞 비트가 1이면 넘친 것입니다.
• 음수끼리 더했는데 결과가 양수로 나와도 넘친 것입니다.
• 부호가 다른 덧셈은 결과가 두 값 사이에 놓이니 넘칠 수 없습니다.

뺄셈은 부호를 뒤집어 더하는 것이니 같은 규칙으로 판단합니다.

5. MIPS의 대응 — add와 addu

MIPS는 오버플로를 두 가지 방식으로 처리합니다. add와 addi는 오버플로가 나면 실행을 멈춥니다. 잘못된 값으로 계속 가지 않고 운영체제에 알립니다. addu와 addiu는 오버플로를 무시하고 지나갑니다. 끝에 붙은 u는 unsigned, 부호 없음입니다. 맨 앞 비트도 부호가 아니라 값으로 보겠다는 뜻입니다. 그렇게 보면 침범당할 부호 자리가 없으니 멈출 일도 없습니다.

시뮬레이터에서 확인할 수 있습니다. $t0에 32비트가 담을 수 있는 가장 큰 양수, 부호 자리만 0이고 나머지가 전부 1인 값을 넣고 addiu $t1, $t0, 1을 실행합니다. 자리올림이 끝까지 올라가 $t1은 맨 앞만 1이고 나머지가 전부 0인 값이 됩니다. addiu는 이 값을 그대로 두고 지나갑니다. 그런데 이 비트열을 부호 있는 수로 읽으면 가장 작은 음수입니다. 가장 큰 양수에 1을 더했더니 가장 작은 음수가 나왔습니다. 같은 계산을 addi로 하면 그 자리에서 산술 오버플로 메시지가 뜹니다.

6. 검출 회로는 XOR 하나

입력 비트를 받아 출력 비트 하나를 만드는 가장 작은 회로 부품을 게이트라고 하고, 게이트를 엮어 덧셈을 하게 만든 회로가 가산기입니다. 가산기는 자리마다 하나씩 있고, 아래 자리에서 올라온 자리올림을 받아 위 자리로 자리올림을 내보냅니다. 그러니 맨 앞자리의 가산기에는 자리올림이 두 개, 들어온 것과 나간 것이 있습니다. 이 둘이 서로 다르면 오버플로입니다.

• 양수끼리면 부호 자리의 두 비트가 모두 0이라 나가는 자리올림은 언제나 0입니다. 아래에서 1이 올라오면 결과의 부호 자리가 1이 됩니다. 들어온 1과 나간 0이 다릅니다.
• 음수끼리면 부호 자리가 모두 1이라 나가는 자리올림은 언제나 1입니다. 아래에서 0이 올라오면 결과의 부호 자리가 0이 됩니다. 들어온 0과 나간 1이 다릅니다.
• 부호가 서로 다른 덧셈에서는 이 둘이 항상 같습니다.

0111 더하기 0001, 4비트에서 7 더하기 1로 확인합니다. 부호 자리로 자리올림이 하나 올라와 결과의 부호 자리가 1이 되고, 밖으로 나가는 자리올림은 없습니다. 실제로 결과 1000은 8이 아니라 마이너스 8입니다. 두 입력이 서로 다를 때만 1을 내보내는 게이트가 XOR이니, 자리올림 두 개를 XOR 하나에 넣으면 검출기가 완성됩니다.

7. 곱셈은 손으로 하던 그대로

곱해지는 쪽을 피승수, 곱하는 쪽을 승수, 승수의 한 자리마다 나오는 중간 결과를 부분곱이라고 부릅니다. 312 곱하기 203을 손으로 하면 부분곱이 936, 0, 624이고, 이 셋을 한 칸씩 밀어 쓰고 더하면 63336입니다.

2진수도 방법은 같지만 훨씬 쉽습니다. 승수의 각 자리가 0 아니면 1뿐이라, 부분곱은 피승수 그대로이거나 전부 0입니다. 곱셈표가 필요 없습니다. 0010 곱하기 1001, 즉 2 곱하기 9를 보면 승수의 끝자리가 1이니 피승수를 그대로 쓰고, 가운데 두 자리는 0이니 부분곱도 0, 맨 앞자리가 1이니 피승수를 세 칸 밀어 씁니다. 더하면 18입니다.

8. 곱셈 회로를 세 단계로 줄이기

4비트 두 개를 곱하면 결과는 최대 8비트, 32비트 두 개면 64비트입니다. 곱은 항상 두 배 길이라 곱을 담는 레지스터는 64비트여야 합니다.

첫 번째 설계

곱 레지스터는 64비트, 처음에는 전부 0입니다. 피승수도 64비트 레지스터의 아래쪽 32비트에 담고 위쪽은 0으로 둡니다. 승수는 32비트 그대로이고, 더하기는 64비트끼리 하므로 가산기도 64비트입니다. 승수의 맨 끝 비트가 1이면 피승수를 곱에 더하고, 0이면 더하지 않습니다. 그다음 비트를 옆으로 밉니다. 이 동작을 시프트라고 부릅니다. 피승수는 왼쪽으로, 승수는 오른쪽으로 한 칸 시프트합니다. 이것을 서른두 번 반복합니다. 부분곱을 한 칸씩 밀어 쓰는 대신 피승수를 미는 것입니다.

두 번째 설계

첫 설계는 낭비가 큽니다. 피승수에서 값이 든 부분은 32비트뿐인데 나머지 절반에는 늘 0을 더하고 있습니다. 두 번째 설계는 피승수를 32비트 그대로 두고 움직이지 않습니다. 대신 곱 레지스터를 오른쪽으로 시프트합니다. 더하기는 곱의 위쪽 32비트에서만 일어나니 가산기가 32비트로 줄었고, 피승수 레지스터도 절반이 됐습니다. 피승수를 왼쪽으로 밀든 곱을 오른쪽으로 밀든, 둘이 겹쳐 더해지는 자리는 매번 한 칸씩 옮겨 가니 결과는 같습니다.

세 번째 설계

아직 레지스터가 피승수, 승수, 곱 세 개입니다. 곱 레지스터는 다 끝난 아랫자리부터 차례로 아래쪽이 채워지니, 계산 초반에는 아래쪽이 비어 있습니다. 반대로 승수는 처음에 전부 필요하고 쓸수록 줄어듭니다. 그래서 승수를 곱 레지스터의 아래쪽 32비트에 처음부터 넣어 둡니다. 그러면 곱 레지스터의 맨 끝 비트가 곧 이번에 검사할 승수 비트입니다. 오른쪽으로 시프트할 때마다 다 쓴 승수 비트는 밖으로 떨어지고, 위에서 내려온 곱이 그 자리를 채웁니다. 레지스터 하나와 시프트 회로 하나가 사라졌습니다.

9. 세 번째 설계로 2 × 9

곱 레지스터를 위쪽 네 자리와 아래쪽 네 자리로 나눠 봅니다. 피승수는 0010입니다.

붙여 읽으면 16 더하기 2, 18입니다. 처음에 손으로 구한 값과 같습니다. 더하기는 두 번, 시프트는 네 번이었습니다.

10. 연습 — 21 × 14와 −7 × 3

21 × 14

10101 곱하기 01110입니다. 5비트짜리 두 수이니 곱 레지스터는 10비트이고, 아래쪽 다섯 자리에 승수 01110을 넣고 시작합니다. 첫 번째 검사는 맨 끝이 0이니 시프트만, 이어지는 세 번은 1이니 더하고 시프트, 다섯 번째는 다시 0이라 시프트만 합니다. 더하기 세 번, 시프트 다섯 번이고, 결과는 294입니다. 시프트 횟수는 승수의 비트 수와 같고, 승수에 1이 몇 개 있느냐는 더하기 횟수만 바꿉니다.

음수가 섞이면

2의 보수로 담은 음수를 그대로 이 회로에 넣으면 답이 어긋납니다. 회로는 맨 앞 비트를 부호로 보지 않고 가장 큰 자리값으로 보기 때문입니다. 마이너스 7을 4비트에 담으면 1001인데, 회로는 이것을 9로 읽습니다. 그래서 부호를 먼저 뗍니다.

1. 음수인 값을 양수로 바꿉니다.
2. 양수끼리 곱합니다.
3. 원래 두 수의 부호가 서로 달랐으면 결과를 음수로 바꿉니다.

마이너스 7 곱하기 3이면 7 곱하기 3, 0111 곱하기 0011이 됩니다. 곱 레지스터는 위쪽 0000, 아래쪽 0011로 시작합니다. 맨 끝이 1이니 0111을 더하고 시프트해 위쪽 0011, 아래쪽 1001. 맨 끝이 또 1이라 0111을 더해 위쪽 1010, 한 칸 밀면 위쪽 0101, 아래쪽 0100. 남은 두 번은 시프트만 해서 위쪽 0001, 아래쪽 0101, 십진수로 21입니다. 두 수의 부호가 달랐으니 여덟 자리를 뒤집으면 11101010, 1을 더하면 11101011, 부호 있는 8비트로 읽으면 마이너스 21입니다.

정리

덧셈은 자리올림을 따라가는 것이고, 음수는 2의 보수로 담습니다. 오버플로는 값이 부호 자리를 침범한 상태입니다. 맨 앞자리 가산기에 들어온 자리올림과 나간 자리올림이 다르면 오버플로이고, XOR 하나면 잡아낼 수 있습니다. MIPS는 add로 멈추고 addu로 지나갑니다. 곱셈은 손으로 하던 계산을 회로에 옮긴 것이고, 설계가 나아가는 동안 64비트 가산기가 32비트가 됐고 레지스터 세 개가 두 개가 됐습니다. 곱은 언제나 두 배 길이라, 32비트끼리 곱하면 64비트가 나옵니다. mult의 결과가 Hi와 Lo에 나뉘어 담기는 이유가 이것입니다. 위쪽 32비트가 Hi, 아래쪽 32비트가 Lo입니다. 남은 나눗셈과 부동소수점은 다음 글에서 봅니다.