[컴퓨터 구조] chapter3 정리 (컴퓨터 연산 : 덧셈, 뺄셈, 곱셈, 나눗셈)

컴퓨터 연산에서 배울 내용들은 정수 연산(사칙연산, 오버플로우), 부동소수점, 컴퓨터가 수를 표현하는 방법 및 산수 연산 알고리즘, 알고리즘을 수행하기 위해 하드웨어를 어떻게 설계해야 하는지에 대한 것입니다. 

 

정수 덧셈 및 뺄셈

ex) 7 + 6

다음과 같이 올림수가 발생하면 오른쪽에서 왼쪽으로 옮겨줍니다.  

 

ex) 7 - 6 = 7 + (-6)

MSB에서 Carry나 Borrow한 값을 무시해 주면 값이 1이 나옴을 확인할 수 있게 됩니다. 역부호화(부호화 + 1)한 후 덧셈을 하는 과정이라고 보면 될 것 같습니다.

 

오버플로(Overflow)

오버플로는 데이터를 저장하는데 사용되는 메모리 영역에 더 많은 데이터가 들어가려고 할 때 발생하는 상황을 말합니다. 주로 산술 연산이나 메모리 할당과정에서 발생하고, 메모리 영역을 초과하여 데이터를 넣을 경우 데이터가 손실될 우려가 있게 됩니다.

 

연산 오버플로는 연산 시에 연산 결과를 사용가능한 하드 웨어(32bit word)로 표현할 수 없을 대 발생하고, MSB를 크기 비트들이 침범해서 값이 이상하게 바뀔 우려가 있습니다. (다른 부호끼리 덧셈, 같은 부호끼리의 뺄셈은 발생하지 않습니다. 절댓값이 작아지기 때문)

 

발생할 수 있는 상황 (절댓값이 증가할 경우)

• 같은 부호끼리의 덧셈 
• 다른 부호끼리의 뺄셈

오버플로 탐지는 MSB (부호 비트)를 크기 비트들이 침범(overflow)해서 값이 바뀌게 됩니다. 결과적으로 부호비트로 올림수가 올라가게 되어 이상한 값이 도출됩니다.

예시 (같은 부호끼리의 덧셈)

2의 보수법을 사용했을 시에 오버플로 탐지를 MSB가 바뀜으로써 인지할 수 있었습니다. 그러면 부호 없는 정수는 어떤지 알아보겠습니다.

 

부호 없는 정수에서 오버플로를 무시하는 MIPS 명령어

addu, addiu, subu 

C언어는 오버플로를 무시하기 때문에 MIPS C 컴파일러는 변수의 형에 관계없이 언제나 부호 없는 버전인 addu, addui, subu 명령어를 생성합니다. 하지만, MIPS Fortran 컴파일러는 피연산자의 데이터형에 따라서 적절한 산술 명령어를 생성합니다.

 

부호 없는 덧셈의 오버플로 검사

 

부호 있는 덧셈의 오버플로 검사

곱셈 

첫 번째 피연산자를 피승수(multiplicand), 두 번째 피연산자를 승수(multiplier)라고 부릅니다. 최종 결과를 곱(product)라고 부릅니다.

두 번째 그림은 승수의 LSB가 1이면 피승수를 곱에 더하고, 그렇지 않으면 다음 단계로 넘어갑니다. 다음 단계에서 피승수를 왼쪽으로 자리이동하고, 승수를 오른쪽으로 자리이동합니다. 이러한 세 가지 단계를 32번 반복합니다. 

세 번째 그림은 곱셈 하드웨어의 첫 번째 버전입니다. 피승수 레지스터, ALU(산술논리장치), 곱 레지스터는 모두 64비트이고, 승수 레지스터만 32비트입니다. 시작할 때는 32비트 피승수가 피승수 레지스터의 오른쪽 절반에 있다가, 매 단계마다 왼쪽으로 1비트씩 자리이동합니다. 승수는 피승수와 반대로 작용합니다. 

 

0010 * 0011 곱셉 연산 과정

다음과 같이, LSB가 1인 경우 피승수를 곱에 더하고, 그렇지 않은 경우에는 다음 단계로 넘어가는 것을 확인할 수 있습니다. (매 단계마다 피승수를 왼쪽으로 Shift하고, 승수를 오른쪽으로 Shift하는 것을 알 수 있습니다)

 

ALU(산술논리연산장치)

• 프로세서에서 실제적인 연산을 담당하는 장치
  1. 산술연산장치 : 산술 연산(+,-,*,/) 수행
  2. 논리연산장치 : 논리 연산(AND, OR, XOR, NOT, ...) 수행
  3. 시프트 레지스터 : 비트들을 좌우로 이동시키는 기능
  4. 보수기 : 데이터에 대해서 2의 보수를 취함

곱셈의 개선된 하드웨어 (add/shift 병렬적 처리 가능)

 

기존 하드웨어는 승수 레지스터만 64비트였지만, 개선된 하드웨어에서는 곱 레지스터만 64비트이고, 승수 레지스터가 없어졌습니다. 대신 승수를 곱 레지스터 오른쪽 절반에 넣어줍니다. (승수 레지스터는 덧셈기의 올림수를 저장할 수 있도록 실제로는 65비트가 되어야 하지만, 개선된 부분만을 강조하기 위해 64비트로 표시)

 

순서대로 설명드리겠습니다.

1. 승수를 곱의 오른쪽 32비트에 두고 시작합니다.
2. 승수의 LSB 확인 후, 1이면 피승수를 곱의 처음 32비트에 더합니다.
3. ALU에 더해서 왼쪽 32비트에 저장하면서 shift를 동시에 수행합니다. 

더 빠른 곱셈 (다중 덧셈기 활용)

Product63과 Product0을 예시로 들면, 각각 자리수의 MSB, LSB 이므로 Product에 사전할당을 해줍니다. 부호 있는 곱셈은 양수로 변환하고, 31비트 곱(부호비트가 0이므로, 1비트에 부호 저장)을 해준 후, 부호를 돌려놓습니다. 이러한 과정을 통해, 파이프라인화되어 더 빨라질 수 있게 됩니다.

 

MIPS 곱셈 명령어

두개의 32-bit 레지스터를 가용

• HI : MS 32 bits (큰 값들)
• LO : LS 32bits (작은 값들)

명령어 

• mult rs, rt / multu rs, rt (오버플로 무시, 64-bit product / HI/LO)
• mfhi rd / mflo rd (HI/LO로부터 rd로 move)
• mul rd, rs, rt

나눗셈

 

나눗셈의 피연산자는 피제수(dividend), 제수(divisor), 몫(quotient), 나머지(remainder)로 구성

 

피제수 = 몫 * 제수 + 나머지 

 

 

 제수와 피제수가 모두 양수라고 가정하고, 피제수가 제수보다 클 경우에는 몫에 1을 두고 뺄셈을 합니다. 그렇지 않은 경우 몫에 0을 두고 제수의 자릿수를 줄입니다. 

 

나눗셈 알고리즘 및 하드웨어 

1. 나머지가 양수이면 제수가 피제수에 들어갈 수 있으므로 몫에 1을 저장합니다. 
2. 나머지가 음수이면 제수는 피제수에 들어갈 수 없기에 몫에 0을 저장하고, 제수를 나머지에 더하여 뺄셈 이전 상태로 회복시킵니다. 
3. 다음번 반복의 계산을 위해 피제수에 맞춰 제수를 정렬시키는 것입니다. (제수를 오른쪽으로 한 칸 shift 시킴)

나눗셈 하드웨어는 제수 레지스터, ALU, 몫 레지스터가 모두 32비트입니다. 몫 레지스터는 32비트 0의 초기값을 가지게 되고, 나머지가 양수인지 음수인지 테스트해 주고 뺄셈 과정이나 회복을 거치게 됩니다. 제수가 64비트 레지스터의 왼쪽 32비트에 있게 됩니다.

 

 예시 : 7 ÷ 2

 

• 초기값 = 나머지 (피제수)
• 나머지 - 제수 < 0 이면 나머지 + 제수를 통한 나머지 복구 이후, 몫을 왼쪽으로 한칸 Shift 이후 LSB에 0 추가
• 나머지 - 제수 > 0 이면 몫을 왼쪽으로 한 칸 Shift하고 LSB에 1 추가
• 제수를 오른쪽으로 한 칸 Shift 

나눗셈 하드웨어의 개선된 버전

곱셈 연산기와 동일하며, Divisor와 ALU가 32비트로 감소하면서 제수가 오른쪽으로 Shift 하지 않도록 설계되었습니다. 피제수 레지스터가 없으며 초기에 나머지 레지스터에 채워집니다. 추가적으로 몫 레지스터는 나머지 레지스터 오른쪽 절반에 결합시켰습니다.

 

상위 32비트에서 재수를 뺀 결과를 상위 32비트에 넣습니다. 

• 양수이면, 나머지 레지스터를 왼쪽으로 shift 하고 맨 오른쪽 비트를 1로 둡니다.  
• 음수이면, 나머지를 원래 상태로 돌림과 동시에 왼쪽으로 shift 하고 맨 오른쪽 비트를 0으로 둡니다. 
• 왼쪽 상위 32비트는 나머지, 오른쪽 하위 32비트는 몫이 위치하게 됩니다.

오늘은 컴퓨터 구조에서 기본적인 연산이 어떻게 하드웨어적으로 설계되고, 설계된 하드웨어에 입각한 알고리즘에 대해서 알아보았습니다.

다음 시간에는 부동소수점에 관해서 설명드리겠습니다.