[Chapter 3.3 컴퓨터 구조 및 설계] 2진수 나눗셈, 나눗셈 하드웨어

본 정리는 CS422-컴퓨터 구조 및 설계 : 하드웨어/소프트웨어 인터페이스. David A. Patterson, 존 헤네시 책을 바탕으로 하고 있음을 미리 알립니다.

 

2진수 나눗셈

---

2진수 곱셈이 어떻게 이루어지는지 보기에 앞서 십진수의 1001010 나누기 1000을 하는 과정을 살펴보자.

Dividend를 보통 피제수(나눗셈을 당한다)

Divisor를 보통 제수

Quotient를 몫

나머지를 Remainder라고 부른다.

 

 보통 초등학교에서 배운 나눗셈 방법은 얼마나 큰 수를 뺄 수 있는지를 검사해서 몫의 자리 수를 하나하나 구한다. 위의 십진수 예는 0과 1 만을 사용하도록 선택하였으므로 제수가 피제수에 얼마나 많이 들어갈 수 있는지 쉽게 알 수 있다.

 

이진수에는 0과 1만 있으므로, 이진수 나눗셈은 이 두가지 중 한가지 선택만으로 제한되므로 계산이 간단하다.

 

 

초기의 나눗셈 하드웨어

초기 나눗셈 하드웨어

일단, Quotient(몫) 레지스터를 0으로 초기화해서 시작하고,

 

이 알고리즘을 매번 반복할 때마다 제수를 오른쪽으로 한 비트씩 자리 이동 시켜야하므로 제수를 64비트 Divisor(제수) 레지스터의 왼쪽 절반에 넣고 시작한다.

 

그리고 피제수와 자리를 맞추기 위해 반복할 때마다 오른쪽으로 한 비트씩 자리이동 시킨다. 

 

Remainder 레지스터는 피제수로 초기화 된다.

 

컴퓨터는 사람처럼 divisor가 dividened보다 크다는 것을 인지하지 못한다.

 

즉, 먼저 dividend에서 divisor를 빼야한다. 이후, 결과가 양수이면, 제수는 피제수와 같거나 더 작으므로 몫에 1을 넣고, 만약 결과가 음수이면 제수를 나머지 레지스터에 다시 더함으로써 값을 회복하고 몫에는 0을 넣는다.

 

제수는 오른쪽으로 자리이동 되고 다시 이 과정을 반복한다.

 

 

 

이 과정을 한번 십진수의 1001010 나누기 1000을 하는 과정으로 살펴보자

 

우선 Divisor는 1000 0000 0000 ... 의 큰 수(1000의 2^32배 수)로 초기화 되어있을 것이고,

Quotient는 0000...

Remainder는 00000...0001001010으로 초기화 되어있을 것이다.

 

우선 Divisor를 shift right시키고 그 수를 Remainder에서 빼보자.

어떤가?

 

Divisor에는 1000의 2^31배 수가 들어있고 이를 Divisor에서 빼면 음수가 나올 것이다.

 

음수가 나왔으므로 다시 Remainder에 Divisor 값을 더하고 몫에는 0을 넣어준다

 

이 과정을 계속 반복하다가, Divisor가 작아져서 0000....0001000000이 되는 순간Remainder - Divisor = 000..0001010으로 양수가 나올 것이고, 몫에는 1이 들어가게 된다.

 

또 음수가 나오는 과정을 두번 반복하고 몫에는 이제 100이 들어있고, 나머지엔 그대로 000..0001010이 들어있을 것이다.

 

이제 Divisor를 마지막 32번째 shift right시키면 1000이 될 것이고,

Remainder - Divisor = 000..0000010으로 양수가 나올 것이고,

몫에 1이 들어가면 몫에는 1001 나머지에는 10의 수가 들어가 있어서 원하는 값을 얻게 된다.

 

초기 나눗셈 하드웨어 알고리즘

 

 

 

개선된 나눗셈 하드웨어

Divisor 레지스터가 32비트로 변했고,

Remainder 우측의 32비트를 몫 레지스터로 사용한다.

 

우선은 Remainder의 우측 32bit를 마찬가지로 dividened로 초기화시킨다.

이 후 Remainder를 한 bit씩 shift left해주면서 Remainder의 좌측 32bit 에서 Divisor값을 빼고 결과가 양수이면, 제수는 피제수와 같거나 더 작으므로 몫에 1을 넣고, 만약 결과가 음수이면 제수를 나머지 레지스터에 다시 더함으로써 값을 회복하고 몫에는 0을 넣는다.

 

이 과정을 32번 반복하면 remainder의 좌측 32bit는 나머지가 되고 우측 32bit는 몫이 된다.

 

마찬가지로, 이 과정을 한번 십진수의 1001010 나누기 1000을 하는 과정으로 살펴보자.

 

우선 Remainder는 0000..001001010의 수로 초기화 되어 있을 것이다.

 

이떄 remainder를 shift left를 1만큼 0시키고 divisor를 좌측 32bit에서 빼보자.

000...000 - 000...001000 은 음수이므로, 다시 remainder좌측 32bit에 더해주어 000...000으로 복귀시킨다.

remainder의 우측 32bit에는 당연히 몫으로 0의 값이 들어왔을 것이다

 

이 과정을 계속 반복하다보면, remainder의 좌측 32bit에 remainder에 원래 있던 1001010의 값이 보이기 시작할 것이다.

즉, 1001까지 shift right 되면, 여기서 1000을빼면 1이 남고 양수이므로, 몫에 1이 들어오고,

또, 1010까지 shift right 되면, 여기서 1000을빼면 10이 남고 양수이므로, 몫에 1이 들어오고 32번 반복되었으므로 종료된다.

 

마지막 좌측 32bit는 shift left 되지 않는다.

 

실제로 마지막 까지 해보면, 남은 수까지 shift left되어 100이 남아버릴텐데 마지막은 몫만 shift left하여 더하고 나머지는 하지 않는다고 한다.

 

즉, 1001의 몫과 10의 나머지를 얻을 수 있게된다.

 

MIPS에선 나머지를 hi레지스터에 몫을 lo 레지스터에 넣는다.

div $s0, $s1 # lo = $s0 / $s1 
# hi = $s0 mod $1

프로그래머는 32비트 정수 나눗셈 몫과 레지스터를 범용 레지스터로 가져오기 위해 mflo(move flom lo) rd, mfhi(move flom hi) rd 명령어를 사용한다.