[컴퓨터 구조] Division

 

 

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.10.22 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Add, Sub, OverFlow

[컴퓨터 구조] Add, Sub, OverFlow

2022.10.22 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Multiplication

[컴퓨터 구조] Multiplication

---

1. Division에 들어가기에 앞서

 

 

Division은 Multiplication보다 훨씬 복잡합니다.

용어는 위와 같습니다.

Divison을 당하는 값은 Dividend(dend), Division을 하는 값은 Divisor(dor), 몫은 Quotient, 나머지는 Remainder입니다.

 

우리는 나눗셈을 할 때, Dividend의 맨 처음부터 Divisor을 빼고, 만약에 빼진다면 Quotient에 1을 적습니다.

만약 빼지지 않는다면, 그 다음 비트에서 Divisor을 뺍니다.

 

해당 개념이 Divisor을 이해하는데 필수적입니다.

이때 해당 수식이 성립해야 합니다.

 

Dor은 0이 되면 안 되므로 dor은 항상 0이 아닙니다.

---

2. Division

 

 

 

Division의 회로

Divisor register의 좌측 32-bit는 Divisor로 초기화됩니다. 그리고 register는 shift right를 수행합니다.

Remainder register의 우측 32-bit는 Dividend로 초기화됩니다.

(실제로 32-bit Dividend에서는 상위 32-bit에 0이 추가되어서, 그대로 Remainder Register에 넣음)

 

Multiplication처럼 shift를 하면서 자릿수를 맞춰나갑니다.

차이점은 Mul의 경우 multiplier의 LSB를 보고 판단하지만, Div는 우선 뺄셈을 진행하고 실행합니다.

 

1. Remainder register에서 Divisor을 뺀다.
2. 값이 음수(MSB = 1)이라면 Remainder를 복구한다. 그리고 Quotient는 0으로 shift 한다.
3. 값이 양수(MSB = 0)이라면 Remainder를 놔둔다. 이때 Quotient register의 LSB 자리에 1을 넣음으로써 shift 한다.

 

0000 0111 / 0010을 해보겠습니다.

 

shift를 함으로써 자릿수를 내려주는 효과를 냅니다.

몫 또한 shift를 하면서 값을 맞춥니다.

 

해당 iteration은 5번 진행합니다.

원래는 bit 수만큼 shift를 해야 정상이지만, 하나의 iteration이 sub, control, shift가 하나의 세트라서 5번의 iteration을 합니다.

 

이 회로 또한 크기 때문에 Optimized 한 Division이 있습니다.

---

3. Optimized Divison

 

 

 

Optimized Divison

Remainder Register의 우측 32-bit는 Dividend로 초기화합니다.

(실제로 32-bit Dividend에서는 상위 32-bit에 0이 추가되어서, 그대로 Remainder Register에 넣음)

 

연산을 진행함에 따라 Remainder Register의 좌측은 Remainder, 우측은 Quotient가 위치합니다.

 

그렇다면 실제 0000 0111 / 0010 연산을 예로 보겠습니다.

1. 우선 Remainder Register에서 Divisor을 뺀다.
2. Remainder Register의 MSB가 1이라면 복구하고, shift left(0이 추가)를 한다.
3. Remainder Register의 MSB가 0이라면 그대로 놔두고, Remainder Register에 shift left(1이 추가)를 한다.
4. 해당 과정을 bit + 1만큼 반복하고, Remainder Register의 좌측 절반을 right shift 한다.

우선 Remainder Register를 shift left를 하는 이유는 Dividend의 자릿수를 올림으로써 나눗셈을 진행하기 위함입니다.

 

최종적으로 마지막에 Remainder Register의 left half를 right shift 하는 이유는 

마지막에 0011 - 0010을 하고 0001이 남는데, MSB가 1이므로 LSB에 1을 추가하며 shift를 해야 합니다.

따라서 몫 bit는 5개가 되고, 나머지 bit는 3개가 되므로, 몫 bit 하나를 없앰으로써 (shift right) 자리를 맞춥니다.

---

4. Singed Division

 

 

부호가 있는 나눗셈을 할 때는,

Remainder의 부호와 Dividend의 부호를 맞춰줍니다.

 

-7 / 2라면 Q는 -3, R는 -1이 됩니다.

 

실제로는 절댓값으로 quotient, remainder를 계산한 후에 remainder과 dividend의 부호를 맞춥니다.

---

5. 기타

 

 

division 연산은 병렬화가 불가능합니다.

병렬로 한다면 sub을 진행한 후, MSB가 1이라면 복구를 해야 하는데, 못하기 때문입니다.

 

RISC-V에서는 signed, unsigned를 위한 명령어가 있습니다.

• div : divide
• divu : divied unsigned
• rem : remeinder
• remu : remainder unsigned

 

참고로 2의 제곱 수를 곱하거나 나눌 때는 단순히 shift를 통하여 연산을 끝냅니다.