Arithmetic

Addition & Subtraction

• 2진수에서 더하기는 Carry(올림수)가 발생
• 빼기는 뒤의 수를 음수취급하여 더함
• MSB(Most Significand Bit)가 1일때, 음수를 취급하는 signed num 때문에 Overflow 발생

Overflow (A + B)

1. 두 수가 양수인데 더해서 MSB가 1이 되어 음수가 된 경우 (본래는 결과가 양수)
2. A는 양수, B는 음수인데 A - B의 상황이라 MSB가 1이 되어 음수가 된 경우 (본래는 결과가 양수)
3. A는 음수, B는 양수인데 A - B의 상황이라 MSB가 0이 되어 양수가 된 경우 (본래는 결과가 음수)
4. 두 수가 음수인데 더해서 MSB가 0이 되어 양수가 된 경우 (본래는 결과가 음수)

Multiplication

• Multiplicand(피승수), Multiplier(승수)를 곱해 Product(곱하기결과)

First version of the multiplication HW

원리 설명

1. Multiplier의 LSB(제일 오른쪽)에서 하나를 꺼냄
1-a. 1이면 Multiplicand를 그대로 내려 product와 더함
1-b. 0이면 버림
2. Multiplicand를 왼쪽으로 shift(자리수 올림)
3. Multiplier를 오른쪽으로 shift(아까 1의 과정에서 LSB를 썼으므로 버림)
4. 32번까지 반복했으면 끝

Refind version of the multiplication HW

• 기존은 64-bit ALU, 64bits Multiplicand, 추가적인 Multiplier을 사용했음
• 32-bit ALU, 32bits Multiplicand로 줄이고, Multiplier을 Product 레지스터에 통합
• Multiplier를 Product의 절반인 32bit에 초기화함으로써, 추가적인 레지스터를 낭비하지 않음

Faster versio nof the multiplication HW

원리 설명

• 계산된 결과를 재활용하며 불러오기에 좀 더 빨라짐
• 하지만 ALU가 많이 사용되어 비쌈
• 나눗셈에는 적용할 수가 없음 (숫자를 빌려빼야하는지, 아닌지 구분을 못함)

Multiply in MIPS

• 32bit × 32bit = 64bit이므로 결과를 2개의 레지스터에 나눠 저장 (Hi, Lo 비트)
• mult rs, rt, multu rs, rt를 하게되면 MSB는 Hi 레지스터에, LSB는 Lo 레지스터에 저장
• mfhi rd를 통해 MSB에 해당하는 레지스터의 값을 가져옴 (move from high)
• mflo rd를 통해 LSB에 해당하는 레지스터의 값을 가져옴 (move from low)
• mul rd, rs, rt를 통해 rs 와 rd를 곱한 값의 LSB 32bit를 rd에 저장

Division

• Dividend(피제수) = Divisor(제수) × Quotient(몫) + Remainder(나머지)

First version of the division HW

원리 설명
초기화: Remainder를 Dividend의 값으로, Quotient를 0으로 초기화, Divisor은 64bit중 절반의 MSB 왼쪽에 32bit저장
1. Remainder에서 Divisor을 뺀다
1-a. Remainder가 양수면 Quotient를 shift left하고 Qoutiont의 LSB에 1을 저장
1-b. Remainder가 음수면 Quotient를 shift left하고 Qoutiont의 LSB에 0을 저장후 다시 Divisor을 더해서 restore
2. Divisor을 shift right
3. 33번 반복했으면 끝
↑ 0000 0111(7) ÷ 0010 (2)의 예시, divisor이 0010 0000인 이유는 절반을 MSB인 왼쪽에 저장하는 규칙을 따랐기 때문

Refind version of the division HW

• 기존은 64-bit ALU, 64bits Divisor, 추가적인 Dividend를 사용했음
• 32-bit ALU, 32bits Divisor 줄이고, Dividend를 Remainder 레지스터에 통합, 또한 Quotient도 Remainder에 통합
• Multiplier를 Product의 절반인 32bit에 초기화함으로써, 추가적인 레지스터를 낭비하지 않음

원리 설명

• First version에서는 Divisor를 shift right하며 계산하지만, 여기서는 Divisor가 유지
• 제일 처음 몫은 0이라 가정하고 Remainder를 shift left 한 번 하고 시작
• Remainder의 MSB방향 32비트에 Dividend를 저장

1. Dividend(Remainder)에서 Divisor을 뺀다.
   1-a. Remainder가 양수면 Remainder shift left하고 LSB에 1을 저장
   1-b. Remainder가 음수면 Reminader에 Divisor을 더해 복구하고, shift left하고 LSB에 0을 저장

• 연산이 진행되는 매 과정마다 Remainder은 shift left가 됨
• 그래서 Dividend가 한자리씩 감소하므로 이는 Divisor가 shift right되는 효과와 같음
• Remainder의 MSB방향 32비트는 처음에 Dividend가 저장되었다가 계속 연산될수록 빼지므로 나머지가 저장
• Remainder의 LSB방향 32비트는 처음에 0이 저장되었다가 계속 연산될수록 Qoutient가 저장되므로 몫이 저장

Faster version of the division HW

• Multiplication은 Faster version이 가능하지만, Division은 이전의 숫자가 무엇이 올지 모르므로 값을 예측할 수 없음
• SRT division으로 Quotient를 한번에 두자리씩 예측하는 알고리즘이 있지만, 이 또한 예측이므로 정확하지 않음

Division in MIPS

• Remainder가 64bit이므로 결과를 2개의 레지스터에 나눠 저장 (Hi, Lo 비트)
• div rs, rt, divu rs, rt를 하게되면 rs mod rd는 Hi 레지스터에, rs / rt는 Lo 레지스터에 저장
• mfhi rd를 통해 나머지에 해당하는 레지스터의 값을 가져옴 (move from high)
• mflo rd를 통해 몫에 해당하는 레지스터의 값을 가져옴 (move from low)

Instruction 정리