컴퓨터의 산술연산

• 컴퓨터의 words는 이진수로 표현되어 있다.

Q) 컴퓨터가 이진수 연산(더하기, 빼기, 곱하기, 나누기)을 효율적으로 하기 위해선 어떻게 디자인 해야 하는가?

더하기 / 빼기

• 더하기 : 주어진 숫자들로 이진수 덧셈을 진행한다.

• 예시) 7+6

• 뺄셈 : 두번째 피연산자를 반전하고 덧셈을 진행한다.(2's complement을 이용하면 더 쉽게 반전이 가능하다.)

• 예시) 7-6

덧셈과 뺄셈을 위한 Circuit design

• Half adder
  • carry input이 없는 1비트 연산이다
    • input : 2개의 1비트 데이터 A,B
    • Output : sum(S), carry(C)

cf) XOR : 두개중 1개만 1일 때 출력값 1

• Full adder
  • carry-input을 가진 1비트의 adder
    • input : 두개의 1비트 데이터 A, B 와 carry(Cin)
    • Output: sum(S), carry(Cout)

• N-비트 평행한 이진 덧셈기
  • 처음 carry input은 0이다.
  • i번째 adder는 (i-1)번째 adder가 carry를 생성할 때 까지 carry를 기다린다.((i-1)번째의 carry out은 i번째의 carry in이 된다.)

• Adder with subtractor(2's complement)
  • Subtract = 0 또는 1(subtract == 1이면 Bi는 반전된다.)
  • Subtract는 또한 initial carry로 이용된다. (만일 subtract==1이면 1이 더해진다.)
    - subtract가 1이라면 모든 비트를 반전하고 +1을 한다.

• MIPS -based 컴퓨터는 32비트의 words를 연산 작업에서 사용한다.
  • 16비트의 immediate operand에 포함되어 있는 상수는 32비트로 연장된다.

Overflow

• 오버플로우는 연산 결과가 너무 클 때 발생한다.(범위를 넘어감)

cf) carry의 overflow는 무시된다. (overflow 확인 시 sign bit만 체크한다.)

• 오버플로우는 이런 상황에 발생한다.
  • 두개의 양수 또는 두개의 음수를 더했을 때 결과의 sign이 다른 수로 나왔을 때
  • 양수에서 음수를 뺐을 때 결과의 sign이 1이 나올 때
  • 음수에서 양수를 나왔을 경우에 결과의 sign이 0이 나왔을 때

• 오버플로우 탐지는 어떻게 해야될까?

  • add, addi, sub 지시사항을 이용한다.
    • 오버플로우에서 예외처리를 한다.(프로그햄은 미리 정의된 exception handler 주소로 jump한다.)
    • e.g) 포트란 언어는 오버플로우를 허용하지 않는다. MIPS 포르탄 컴파일러는 항상 add, addi, sub를 이용한다.

• 오버플로우 무시하려면 어떻게 해야 할까?

  • addu, addui, subu 지시사항을 이용한다.(u는 unsigned를 의미한다.)
    • 오버플로우에서 예외처리를 하지 않는다.
    • e.g) C는 오버플로우를 무시한다. MIPS C 컴파일러는 항상 addu, addui, subu를 이용한다.

곱셈

• 다음 곱셈 연산을 해보자

• 만일 multiplicand 와 multiplier가 m과 n 숫자를 가지고 있다면 product는 최대 m+n 숫자를 가지고 있다.
  • MIPS를 기반으로 한 컴퓨터는 연산작업을 하기 위해 32비트의 words를 가지고 있다.
  • MIPS를 기반으로 한 컴퓨터는 product로 최대 64 digits를 가지고 있다.

HW에서 곱셈 연산에서의 최적화 버전

• 32비트 Multiplicand 레지스터 / ALU

• 64비트 product 레지스터(multiplier는 product와 레지스터를 공유한다.)

  • 실제로 product register 왼쪽에 adder의 carry out을 저장할 수 있는 1비트가 추가로 있다.

ex) N = 4일때(4-비트 ALU / multiplicand, 8-비트 product), 2 X 3 = ?

• 우리는 적은 값의 레지스터를 가지고 곱셈 연산을 진행할 수 있다.

Signed multiplication

• multiplicand 와 multiplier를 양수로 반환을 한 후에 곱셈연산을 한다.
  • 31번의 반복을 진행한다.(sign 비트 이외에 반복)
  • 곱셈연산 이후에 결과값을 반전시킨다.(요구된다면)
• 더 좋은 해결책 : Booth's Algorithm
  • 2's complement signed 숫자의 곱셈 작업을 더 효율적인 방법으로 진행한다.
  • unsigned number의 곱셈과 거의 동일한 하드웨어를 요구한다.

MIPS에서의 곱셈

• product에 2개의 32비트 레지스터가 이용된다.
  • HI : 32비트의 most significant bits
  • LO : 32비트의 least significant bits

• instruction
  • mult rs, rt / multu rs, rt
    • 결과는 HI/LO에 저장된다.
  • mfhi rd / mflo rd
    • HI/LO에서 rd로 옮긴다.

MIPS-base computer의 곱셈 연산

• ex) mult $t0, $t1

• $t0(multiplicand)는 multiplicand register로 이용된다.

• 처음에 $t1(multiplier)의 값은 LO register로 load된다.

• 곱연산을 진행하고 64비트의 product를 HI 와 LO register에 저장한다.

나눗셈

• 주어진 나눗셈 작업을 진행해 보자

• 만약 Dividend 와 Divisor가 M과 N이라면, Quotiet의 길이 <= M - N +1 이고 remainder의 길이 <= N 이 된다.

• MIPS-기반으로 한 컴퓨터에서 32비트는 Dividend와 Divisor를 표현하는데 이용된다. 그러므로, Quotient와 Remainder <= 32 이다.

• 다음은 32 비트 divisor register/ALU이고

• 64비트 remainder register이다.(dividend와 quotient는 remainder와 레지스터를 공유한다.)

• ex) N = 4(4비트 ALU / divisor, 8비트 remainder)에서 7/3 =?

Signed division

• divisor와 dividend를 바꾼 후에 나눗셈을 진행한다.
  
• divison 이후에
  • divisor와 dividend의 sign값이 다를 경우에만 quotient를 반전시킨다.
  • 0이 아닌 remainder의 부호가 dividend와 동일하게 맞춘다.
  • 7(Dividend) / -3(Divisor) = -2(quotient)... 1(remainder)
  • -7 / 3 = -2(quotient)... -1(remainder)

MIPS에서 나눗셈

• 2개의 32비트 레지스터가 product에 이용된다.
  • HI : Remainder
  • LO : Qoutient
• instructions
  • div rs, rt / divu rs, rt ($rs / $rt를 진행해라)
  • 결과는 (remainder & quotient)는 HI와 LO에 저장되어 있다. (오버 플로우가 없거나 zero division 문제가 없을 시)

MIPS-based 컴퓨터의 division

• ex) div $t0, $t1

• 처음에 $t0(dividend)에 존재하는 값이 LO 레지스터에 load된다.

• 처음에 $t1(divisor)가 dividor 레지스터로 이용된다.

• 나눗셈을 진행하고 remainder와 quorient를 HI와 LO 레지스터에 저장한다.

요약 : 연산 작업을 위한 디자인

• 덧셈과 뺄셈을 할 때 같은 HW를 이용한다.
  • 32비트의 평향한 adder
  • 추가적인 XOR 연산자 + subtract bit

• 곱셈과 나눗셈을 할 때 같은 최적화된 HW를 이용한다.
  • multiplicand, divisor를 위한 single 32비트 레지스터
  • single 32비트 ALU
  • 나눗셈과 곱셈의 결과를 HI와 LO 레지스터