[MIPS] Division in MIPS

MIPS version 나눗셈 연산을 알아보기 전에 나눗셈 format을 살펴보겠습니다.

 

 

                                     0001001                  # quotient

----------------

                                            1000   |      1001010                  # Divisor and Dividend     

- 1000        

       ----------------       

                                                          10                      # Partial remainder

........

----------------

                                                   10                 # Remainder

 

 

본격적으로 MIPS 나눗셈 수행 방식을 알아보겠습니다.

 

알고리즘은 아래와 같습니다.

partial에서 remainder가 divisor보다 크거나 작으면 quotient bit가 1이 됩니다.

반대로 작으면 quotient bit는 0이 됩니다.

 

 

MIPS에서 나눗셈 수행 결과는 HI register와 LO register에 담기는데 

나머지(remainder)는 HI register

몫(quotient)은 LO register

에 담깁니다.

 

 

나눗셈도 곱셈과 마찬가지로 Quotient 부분이 Dividend/Remainder 하드웨어와 하나로 합쳐집니다.

하드웨어 갯수가 줄어듭니다.

 

 

7/2 연산을 해보겠습니다.

나눗셈은 곱셈과 다르게 shift left logic을 수행합니다.

0000	0111	SLL
0000	111?	SUB
- 0010
1110	1110	Put 0
+ 0010		Restore
0000	1110	SLL
0001	110?	SUB
- 0010
1111	1100	Put 0
+ 0010		Restore

0001	1100	SLL
0011	100?	SUB
- 0010
0001	1001	Put 1
0011	001?	SLL
- 0010		SUB
0001	0011	Put 1
0001	0011	Result

✓  SLL - SUB - Put 0 or 1(in last bit) - Restore or not

이 하나의 수행 cycle 이라고 생각하시면 됩니다.

 

✓  SLL은 shift left logic으로 하나씩 왼쪽으로 비트를 shift 시키면 마지막 bit는 공백으로 남습니다.

✓  공백인 상태로 SUB divison을 시킵니다.

✓  SUB의 수행 결과에서 1번째 bit가 1이면 마지막 bit에 0를 넣고

Restore 즉, 빼준 값을 다해 더해줍니다.

0000 111□

- 0010            

--------------

                           1110 111□                # Put 0

↓

1110 1110

                             + 0010                       # Restore

--------------

0000 1110

 

 

✓  SUB의 수행 결과에서 1번째 bit가 0이면 마지막 bit에 1를 넣고

Restore은 수행하지 않은 상태에서 다시 SLL로 넘어갑니다.

0011 100□

- 0010            

--------------

                            0001 100□               # Put 1

↓

1110 1001

    

 

 

 

Q) 나눗셈의 부호는 어떻게 결정되나요?

A) Quotient의 경우에는 divisor과 dividend 부호의 곱셈 결과이고,

Remainder의 경우는 dividend 부호를 따라갑니다.

 

 

Example

dividend/divisor = Quotient, Remainder

7/2 = 3, 1

-7/2 = -3, -1

7/-2 = -3, 1

-7/-2 = 3 -1

 

✓ Quotient의 부호 → Dividend의 부호 X Divisor의 부호

✓ Remainder의 부호 → Dividend의 부호 

 

 

 

◡̈