[마이크로프로세서] ARM 2진수 곱셈 나눗셈 처리 하드웨어

2진수 곱셈

곱셈에서는 곱해지는 수, 곱하는 수, 결과 세 가지 요소가 존재합니다.

이를 multiplicand, multiplier, product 라고 칭합니다.

 

4비트의 곱셈을 생각해보면 덧셈의 연속이라 할 수 있습니다. (실제 프로세서에서는 64비트 곱셈)

평소에 곱셈하는 방법을 생각해보면 multiplicand에 multiplier 의 한 자릿수씩 곱하고 더해 곱셈을 완료합니다.

같은 방식으로 2진수의 곱을 진행해보면

multiplier의 일의 자리부터 차례대로 더해나갈 것입니다. 이때 자릿수에 1이 있다면 더하면 될 것이고, 0이 있다면 0을 곱하고 더하는 것이니 더하지 않고 넘어가면 될 것입니다.

곱 ver1.

먼저 오른쪽 끝을 체크하고 1이면 더하고 0이면 더하지 않습니다.

그리고 multiplicand를 왼쪽으로 1bit shift 합니다. multiplier는 오른쪽으로 1bit shift 합니다.

left shift 하는 이유는 다음 자릿수를 곱하기 위해서 이며
right shift의 이유는 multiplier의 가장 오른쪽 비트의 0 / 1 을 체크하는데 계속 다음 자릿수를 확인해야하기 때문입니다.

동작을 반복합니다. 

곱셈 동작을 위한 하드웨어를 살펴보겠습니다. 

앞서 설명한 것처럼 오른쪽의 multiplier의 오른쪽 끝 비트를 체크하고 1이면 multiplicand 를 product에 더합니다. 
그리고 multiplier 를 shift right, multiplicand 를 shift left 하고 반복합니다. 

64번 반복하면 128비트의 Product 결과값을 얻을 수 있습니다. 

---

곱 ver2.

첫 번째 경우에는 128비트의 ALU, 128비트의 Multiplicand가 필요했습니다.
그리고 multiplicand 를 left shift 하였습니다.

곱셈 연산 하드웨어를 간소화하기 위해서 multiplicand를 left shift 하고 product에 더하는 것이 아닌 
product 를 right shift 하여 더한다는 아이디어를 적용해보겠습니다.

이때 ALU 에서는 product 의 상위(왼쪽) 64비트에 덧셈 연산을 하게 됩니다. 
때문에 처음에는 오른쪽 64비트가 비어있는데 이 공간까지 활용하기 위해서
오른쪽 64비트 부분에 multiplier 를 넣을 것입니다.

multiplier 또한 product 처럼 덧셈 후 right shift 동작을 하기에 이 동작까지 충족시킬 수 있습니다. 

2진수 나눗셈

나눗셈에서도 나눠지는 수, 나누는 수, 몫 로 세 가지 요소가 존재합니다.

나눠지는 수(나머지와 함께 사용)를 remainder, 나누는 수를 divisor, 몫을 Quotient 라고 합시다.

평소에 나눗셈을 어떻게 하는지 생각해보면 뺄셈의 연속입니다.

큰 자릿수부터 나눠지는지 확인을 해보며 몫을 계산하고, 몫을 divisor와 곱한 값을 빼고 나머지로 반복합니다. 

 

나눗셈 ver1

사람의 나눗셈 연산과 비슷하게 2진수 나눗셈을 구성해봅시다.

remainder 의 왼쪽 끝부터 divisor를 빼가면서 결과를 구해야합니다.

때문에 divisor의 경우 128비트의 왼쪽 64비트에 divisor 값를 넣고,
remainder의 경우 128비트의 오른쪽 64비트에 나눠지는 수의 값을 넣고 시작합니다. 

remainder에서 divisor을 빼고 그 값이 음수가 아니라면 Quotient(몫)에 1을 넣습니다. 
뺀 값이 음수라면 나눠지지 않았다는 의미이므로 Quotient(몫)에 0을 넣습니다.
이때는 remainder 값을 다시 돌려줘야하므로 divisor 값을 더해 복구해줍니다.

그리고 다음 자릿수에서 연산하기 위해 divisor을 right shift 하고,
몫을 계속 채워줘야하기에 Quotient를 left shift 하고 연산을 반복합니다.

하드웨어 구성을 보면 다음과 같습니다.

위의 remainder와 divisor의 최초 비트 구성을 보면 첫 번째 연산에서는 아무 값이 없는 0을 빼주게 됩니다.
때문에 64번이 아닌 65번의 뺄셈을 반복해야 결과가 나오게됩니다.

나눗셈 ver2

곱셈과 마찬가지로 간소화해보겠습니다. 

divisor를 right shift 하는 것이 아닌 remainder를 left shift 하는 아이디어를 적용해봅시다.

또 remainder에 처음에 64비트의 공간을 비워두고(0인 상태) 시작하는데 이 부분을 Quotient로 사용할 수 있습니다.

때문에 remainder의 왼쪽 64비트에 값이 들어가고
오른쪽 64비트에는 몫(quotient)이 들어가며 left shift를 진행하게 됩니다.

 

나머지의 왼쪽 64비트에 대해 Divisor와 뺄셈 연산을 진행하고 오른쪽 64비트에 몫을 넣는 것을 볼 수 있습니다.

나눗셈에서는 주의해야할 점이 하나 있습니다. 나머지를 계속 left shift 하다보니
마지막 연산 후 나머지가 left shift 된 상태로 존재합니다. 

때문에 이 수를 정상 상태로 돌려주기 위해 왼쪽 64비트 대상으로만 right shift가 한 번 필요합니다.