Multiplication
ALU에서 곱셈은 덧셈을 반복하는 식으로 이루어진다.
곱해지는 수를 multiplicand, 곱하는 수를 multiplier , 결과를 product라고 정의한다.
product의 길이는 곱하는 operand의 길이 즉, multiplicand(m bit)와 multiplier(n bit)의 합 (m+n)bit이다.
위 그림에서 LEGv8 ISA는 레지스터 크기가 64bit이기 때문에 ALU 또한 기본 단위가 64bit이므로 Multiplier도 64bit로 표현되어있고 Multiplicand는 Multiplier 비트만큼 shift연산을 하기 때문에 128bit로 크기가 정해져있고 product 또한 128bit이다.
연산 순서는 먼저 multiplier의 LSB를 파악해서 0이면 곱할게 없으니까 multiplicand와 multiplier모두 shift 연산만을 수행한다. 만약 LSB가 1이면 multiplicand를 product에 더한후 마찬가지로 shift 연산을 수행한다. 이 과정은 control test에 의해 모두 컨트롤 된다.
예제를 보자
multiplicand 0010 에 multiplier 0011을 곱하는 예제이다. 2*3
iteration 1을 보면 multiplier의 LSB가 1 이므로 product에 muliplicand를 더한다
이후 multiplicand는 left shift, multiplier는 right shifr를 수행한다.
이 과정을 multiplier bit만큼 반복하면 결과는 0110으로 6이 나온다.
하지만 64bit라 가정했을 때 한번 곱셈을 할 때 64*3 거의 200 cycle을 필요로 하기에 performance적인 면에서 효율적이지 못하다. 그래서 나온 것이 Optimized Multiplier이다.
기존과 비교해서 Multiplier register가 사라졌고 product register의 오른쪽에 붙어있다. 또한 add와 shift가 동시에 수행된다. 각 step을 병렬화 해서 속도를 개선하였지만 반복횟수는 동일하다.
그래서 Faster Muliplier에서는 여러 개의 Adder를 사용해 동시에 여러 부분 곱을 계산한다. 64비트의 곱셈의 경우는 log2(64)=6 단계의 덧셈으로 처리가 가능하다.
마지막으로 LEGv8에서 곱셈명령어는
- MUL: 하위 64비트 결과.
- SMULH: 상위 64비트 결과 (피연산자를 signed로 가정).
- UMULH: 상위 64비트 결과 (피연산자를 unsigned로 가정)
Division
divisor는 divisor 레지스터의 왼쪽에 들어가고 dividend 는 remainder register의 오른쪽에 값을 넣는다.
이후 remainder에서 divisor 값을 빼서 >=0 이면 qutotient을 left shift 후 1을 넣고, divisor을 right shift 한다.
만약 < 0 이면 divisor을 다시 더해서 remainder를 복구 시킨후 qutotient을 left shift 후 0을 넣고 divisor을 right shift 한다. 이 과정을 divisor의 비트수만큼 반복한다.
지금까지의 방식은 옛날의 Restoring 방식이다. 하지만, 이 방식은 뺄셈에서 음수가 나올때마다 remainder를 복구해야하므로 속도와 효율이 떨어진다. 이 방식을 개선한것이 Optimized Divider의 non-restoring 방식이다.
128bit 였던 Divisor register가 64비트로 감소했고 마찬가지로 Remainder의 오른쪽 64비트에는 dividend로 초기화되어있지만 각 단계에서 left shift 되면서 최종적으로는 왼쪽 64비트는 dividend, 오른쪽 64비트는 quotient로 채워진다.
예제를 통해서 살펴보자
dividend = 0110 = 6
divisor = 0010 = 2
Step 1
- Left Shift: 0000 110X
- 상위 4비트(0000) − Divisor(0010) = 1110 (음수)
- 음수 → 복원(0000으로 되돌림), Quotient LSB=0
- 결과: 0000 1100
Step 2
- Left Shift: 0001 100X
- 상위 4비트(0001) − Divisor(0010) = 1111 (음수)
- 음수 → 복원(0001로 되돌림), Quotient LSB=0
- 결과: 0001 1000
Step 3
- Left Shift: 0011 000X
- 상위 4비트(0011) − Divisor(0010) = 0001 (양수)
- 양수 → 유지(0001), Quotient LSB=1
- 결과: 0001 0001
Step 4
- Left Shift: 0010 001X
- 상위 4비트(0001) − Divisor(0010) = 1111 (음수)
- 음수 → 복원(0001로 되돌림), Quotient LSB=0
- 결과: 0001 0010
최종 결과
- Quotient = 0011 (십진수 3)
- Remainder = 0000
즉, 6 ÷ 2 = 몫 3, 나머지 0
