[Computer Architecture] Multiplication & Division

위의 사진은 많은 ALU를 사용하여 적은 cycle 수로 처리하는 multiplier이다.

cycle 수도 줄고, 속도는 빨라진다. depth 5의 tree 형태로 형성되어 있기 때문에 5번의 addition이면 연산을 수행할 수 있다. 게다가 pipeline 형식으로 첫 번째 라인을 통과하면 새로운 곱셈을 수행할 값을 입력할 수 있다.(쓰루풋은 유지된다)

MIPS Multiplication

• mult rs, rt / multu rs, rt
  레지스터 두 가지를 넣어 결과를 HI/LO 레지스터에 저장한다.
• mfhi rd / mflo rd
  HI(상위)또는 LO(하위)의 32bit 값을 가져온다. e.g. HI의 값으로 오버플로우를 확인할 수 있다.
• mul rd, rs, rt
  오버플로우 확인 필요없이 하위 32bit을 rd에 바로 저장하고 싶을 때 사용하는 명령어이다.

Division

Division은 사람이 이해하기 조금 어려운 방식으로 수행한다.
나눗셈의 절차는 다음과 같다.

• 0으로 나누는지 확인한다.
• 나누는 수가 나뉘는 수보다 작거나 같으면 수를 빼고 shift를 수행한다.
• 나누는 수가 더 크면, 그냥 shift한다.

Restoring divison(미리 빼기)

크기를 확인하려면 하드웨어는 일단 빼봐야한다. 만약 뺐을 때, 음수이면 다시 복구를 해야한다.(나누어지지 않으니)

Signed divison(-, +의 나눗셈)

음수 양수를 사용하여 나눈다면, 절댓값을 사용하고 이후에 부호를 맞춰준다.
두 음수를 사용하여 나누었을 때, 나머지에 음수를 허용할지 양수만 사용할지를 고려한다.

Divisor 1

나눗셈의 절차를 확인해보자.

• Remainder는 dividend를 저장한다. divisor-remainder를 수행하고 음수면 이전 수로 복원한다.
• Divisor는 나누는 수를 저장한다. 이를 오른쪽으로 shift하며 나눗셈의 성질을 만족한다.
• Quotient는 remainder-divisor의 결과값이 양수면 최하위 비트에 1을 저장하고 왼쪽으로 shift한다.

remainder엔 자연스럽게 나머지가 남을 것이다.

Divisor 2

Remainder는 dividend을 저장한 초기의 상태이고 최종적으로 몫과 나머지를 저장한다.
Divisor는 나누는 수를 저장한다.

• remainder-divisor를 수행한다.
• Remainder를 왼쪽으로 shift한다.
• Quotient는 remainder-divisor의 결과값이 양수면, remainder에 최하위 비트에 1을 저장한다.

둘이 똑같이 생겼네? 같이 multiplier와 같이 사용할 수 있다.

MIPS Division

• div rs, rt / divu rs, rt: HI와 LO에 각각 나머지와 몫을 저장한다.
• mfhi rd / mflo rd: HI 와 LO의 값을 rd 레지스터에 저장한다.