Arithmetic for Computer- Computer Architecture

Arithmetic for Computers

• 정수(integer) 영역의 작업(operation)
• 덧셈(Addition)과 뺄셈(Subtraction)
• 곱셈(Multiplication)과 나눗셈(division)
• 오버플로우(overflow)를 주의해야 함

• 부동 소수점(floating-point)의 실수(real numbers)
• 표현(representation)과 작업(operation)
 

Integer Addition

• 예시: 7(0b111) + 6(0b110) = 13(0b1101)

• 만약 결과가 정수형 표현 가능한 범위를 벗어나면 오버플로우(overflow)가 일어남
• 피연산자가 양의 값(+ve)과 음의 값(-ve)인 덧셈에서는 오버플로우가 발생하지 않는다.
• 모든 수식을 세분화하면 항상 두 값의 연산으로 나뉘어짐.
• 피연산자도 정수형 표현 범위 내의 값일텐데, 어떤 경우에서도 정수형 범위 안의 결과를 얻음.
• 피연산자 2개 모두 양의 값(+ve)이라면, 발생할 수도 있음.
• 부호비트(MSB)로 1이 넘어가면서 음수화.
• 피연산자 2개 모두 음의 값(-ve)이라면, 발생할 수도 있음(언더플로우, underflow).　　
• 부호비트(MSB)가 1에서, 1이 넘어오면서 0이 되어 양수화.

Integer Subtraction

• 2번째 피연산자(operand)가 음의 값인 덧셈처럼 비트 계산.
• 2번째 피연산자를 음수로 만들고 비트덧셈.

• 예시: 7 - 6 = 7 + (-6) = 1

• 만약 결과가 정수형 표현 가능한 범위를 벗어나면 오버플로우(overflow)가 일어남.
• 피연산자가 모두 양의 값(+ve)이거나, 모두 음의 값(-ve)이라면 오버플로우가 발생하지 않는다.
• (각각 +-의 덧셈 혹은 -+의 덧셈이므로, 표현 범위 내의 값의 차이는 표현 가능한 범위 안의 결과임.)

• 양의 값(+ve)에서 음의 값(-ve)을 뺀다면(+에+), 발생할 수도 있음.
• 부호비트(MSB)로 1이 넘어가면서 음수화.

• 음의 값(-ve)에서 양의 값(+ve)을 뺀다면(-에-), 발생할 수도 있음(언더플로우, underflow).
• 부호비트(MSB)가 1에서, 1이 넘어오면서 0이 되어 양수화.

2’s Comp - Detecting Overflow

오버플로우 처리

• 몇몇 언어(e.g., C)에서는 오버플로우를 무시한다(일어나도 그 값으로 둔다).
• MIPS instruction에서는addu, addui, subu가 무시

• 다른 언어(e.g., Ada, Fortran)는 예외를 발생(raise an exception)시킨다.
• MIPS instruction에서는 add, addi, sub가 예외발생시킴.
• 오버플로우가 발생하면, exception handler를 호출(invoke)한다.
• PC(Program Counter)를 exception program counter(EPC) 레지스터에 저장한다.
• 미리 정의된(predefined) handler의 주소로 점프한다.
• mfc0 (coprocessor 레지스터로부터 move) instruction은 수정 조치(corrective action) 후에 return하기 위해 EPC의 값을 찾아낼 수 있다.

Multiplication

Multiplication Hardware

 

Optimized Multiplier Hardware

MIPS Multiply Instruction

• product에 2개의 32-bit 레지스터를 사용한다. (결과는 64-bit으로 저장되기 때문에)
• HI: most-significant 32 bits. 상위 32비트.
• LO: least-significant 32 bits. 하위 32비트.

• Instructions
• mult　rs, rt　/ multu　rs, rt
• HI와 LO로 64-bit의 product를 생산(곱한다)
• mfhi　rd　/ mflo　rd
• HI/LO로부터 rd로 move
• 만약 product가 32 bits 보다 커서 오버플로우가 될지 HI의 값을 미리 보려고 할 때에 사용할 수 있다.
• mul　rd, rs, rt
• product의하위 32비트를 rd로.
• mult나 multu가 64비트 결과라면, mul은 32비트 결과.

Faster Multiplier

• 위의 sequncial version은, 4-bit의 수를 곱하려면 4번의 반복을 필요로 했음.
• (32-bit의 수라면 32번의 반복)

• 여러 개의 adder를 사용한다
• cost/performance 교환.
• 결과를 빨리 얻을 수 있지만(성능은 높지만), 하드웨어를 많이 사용하므로 비용이 많이 든다.

• pipeline화 가능하다.
• 각각의 곱 행동을 병렬적으로 수행한다. 이러면 적은 하드웨어 리소스로도 빠른 연산이 가능하다
 

Division

Division Approach

• divisor(제수, 나누는 수)가 0인지 확인한다.

• 긴 나눗셈의 접근법
• 현재까지의 dividend 자릿수가 divisor 자릿수보다 크거나 같다면,
• 몫의 현재 비트에 1을 넣고, dividend에서 divisor만큼 뺀다.
• 그렇지 않다면,
• 몫의 현재 비트에 0을 넣고, dividend의 비트자리를 한단계 뒤로 추가한다(bring down next dividend bit).

• Restoring(복원) division
• dividend에서 divisor만큼 뺐는데 음수가 된다면, 다시 divisor를 더해서 복원해줘야 한다.

• Signed(부호) division
• 절대값(부호없는)을 써서 나눗셈을 해야한다.
• 그리곤 몫과 나머지의 부호를 조정해야 한다.
 

Division Hardware

Optimized Divider

MIPS Divide Instruction

• 결과용으로 HI / LO 의 2개의 레지스터를 사용한다.
• HI: 32-bit의 remainder(나머지)
• LO: 32-bit의 quotient(몫)

• Instructions
• div rs,rt / divu rs,rt
• 오버플로우는 발생하지 않는지, 0으로 나누는지 확인한다.
• 필요하다면 소프트웨어 단계에서 체크도 가능
• 결과에 접근하기 위해 mfhi, mflo를 사용한다.
 

부동소수점 (Floating Point)

• 정수가 아닌 수 (실수)를 표현하기 위해서
• 아주 작은 수 (0.000,,,) 나 아주 큰 수를 포함

• scientific notation
• 정수부가 일의 자리인 표현을 정규화된 표현, 아니면 not normalized scientific notation
• -2.34 * 10^56 ⇒ normalized
• 0.002 * 10^(-4) ⇒ not normalized
• 987.02 * 10^9 ⇒ not normalized

• binary
• +- 1.xxxxxx_2 * 2^(yyyy)

• C에서는 float, double형이 있음

Floating Point Representation

• 여전히 모든 것을 32 bit에 맞춰야 한다.

Floating Point Standard

• IEEE(전기전자기술자협회)에 의해 IEEE 754로 정의됨

• 표현하는 방식이 많아지게 되자 개발됨
• scientific code의 이식성 문제를 해결하고자

• 현재 대부분 보편적으로 채택하고 있음

• 2개의 표현법
• single-precision (단정도, 32-bit)
• double-precision (배정도, 64-bit)

• 그 외
• half-precision: 16-bit
• quadruple-precision: 128-bit
• octuple-precision: 256-bit
 

IEEE 754 FP Standard

• 요즈음의 대부분의 컴퓨터는 IEEE 754 floating point standard를 채택한다.
• single-precision, double-precision 모두
• single precision은 E: 8-bits, F: 23-bits
• double precision은 E: 11-bits, F: 52-bits

• F는 normalized된 포맷으로 저장되어 있다. (1.xxx)
• 1은 그렇기 때문에 저장할 필요가 없다. - hidden bit

• Floating point 소팅을 간단히 하기 위해서, excess(biased) notation을 사용한다.
• 즉 나타내기 위한 exponent에 Bias를 더하여 표현한다.
• Single precision: Bias = 127
• Double precision: Bis = 1023

Floating-Point Example

• -0.75를 나타내라
• -0.75 = -1 * 1.1_2 * 2^(-1)
• S = 1
• Fraction = 1.10000..00_2
• Exponent = -1 + Bias
• Single: -1 + 127 = 126 = 01111110_2
• Double = -1 + 1023 = 1022 = 01111111110_2
• Single: 1011111101000..00
• Double: 1011111111101000..00
 

• S = 1

• Fraction = 01000…00_2

• Exponent = 10000001 = 129 - 127 = 2

• x = -1 * (1+0.1_2) * 2^2
= -1 * 1.25 * 2^2
= -5.0

IEEE 754 FP Normalized Form

• Normalized Form (single) with a hidden bit
• E: 0000 0001 ~ 1111 1110
• Bias를 제외하고 -126 ~ 127 제곱까지 사용할 수 있다.
• F: Any

• Examples (in normalized format)
• Smallest+: 0 00000001 00000000…00 = 1 x 2^(-126)
• Largest+: 0 11111110 1.111111…11 = (2 - 2^(-23)) x 2^127
 

IEEE 754 FP standard Encoding

Denormal Numbers

• exponent가 0b000…000 이라면, fraction의 숨겨진 비트를 0으로 한다.

• 표준 범위보다 더 작은 값을 위해
• 정도를 줄여서 점진적으로 작은 값을 허용

• fraction 값에 의해 값이 결정 됨.
• fraction이 0b000…00 이라면 값은 딱 0.0이 가능하다.

Denormalization Numbers

Infinities and NaNs

• Exponent = 111…1, Fraction = 000…0
• +- Infinity
• subsequent calculation에 사용될 수 있다.

• Exponent = 111…1, fraction ≠ 000…0
• NaN
• illegal or undefined result
• divided by zero
• subsequent calcualtion에 사용될 수 있다.
 

Exception Events in Floating Point

• Overflow는 positive exponent가 너무 커서 표현할 수 없는 경우

• Underflow는 negative exponent가 너무 작아서 표현할 수 없는 경우

• 해결 방법 double precision

Support for Accurate Arithmetic

• IEEE 754 FP rounding modes
• 항상 올림
• 항상 내림
• 버림
• 양수는 작아지고, 음수는 커짐
• Round to nearest even 반올림
• 위의 자리맞춤 연산들은 확률적으로 공평하지 않다.
• Guard || Round || sticky are 100
• 반올림을 했을 때 LSB가 항상 0이 되도록
• 계산된 결과 값이 두 값의 가운데에 위치할 때 최하위 비트가 홀수이면 더하기 1, 짝수이면 잘라내는 것이다.
• 즉, 정가운데일 때 이 방법은 항상 최하위 비트를 0으로 만들어 준다.
 

• G가 0이라면 내림

• G가 1이라면
• R이 1이라면 올림
• R이 0이라면
• S는 뒤쪽에 나오는 모든 비트를 확인하여 하나라도 1이 나오면 S는 1
• S가 1이라면 올림
• S가 0이라면 짝수의 방향으로 내림 혹은 올림된다.
• LSB가 0이 되는 방향
 

부동소수점 덧셈

1. F1, F2의 hidden bit을 복구시킨다.

2. E1과 E2의 자릿수를 맞춰준다 ( 높은 방향으로 )

3. F2와 F1을 더해 F3을 만든다

4. F3을 정규화한다

5. Round to nearest even(반올림) 해준다.

6. F3, E3을 이용해 부동소수점 표현으로 바꾸어준다.

10진수 소숫점 4자리의 예시　

1. 소숫점 정렬
1. 작은 수를 큰 수에 맞춤(작은 수를 조정).
1. 9.999 * 10^1 + 0.0161 * 10^1

2. significand끼리 더함
1. 9.999 + 0.0161 = 10.0151. 즉, 1.00151 * 10^1

3. 결과를 정규화하고, 오버플로우/언더플로우 하지 않았는 지 검사
1. 1.0015 * 10^2. 1.0015e2

4. 필요하다면 반올림하거나 비정규화한다.
1. (ㆍ1.002e2, 10^2, 100)

binary 소숫점 4자리의 예시　

1. 소숫점 정렬
1. 작은 수를 큰 수에 맞춤(작은 수를 조정).
2. 1.000_2 * 2^(-1) + -0.1110_2 * 2^(-1)

2. significand끼리 더함
1. 01.000_2 + 11.001_2 = 00.001_2 = 0.001_2. 즉, 0.001_2 * 2^(-1)

3. 결과를 정규화하고, 오버플로우/언더플로우 하지 않았는지 검사
1. 1.000_2 * 2^(-4)

4. 필요하다면 반올림하거나 비정규화한다.
1. (ㆍ2^(-4), 0.0625)
 

부동소수점 가산기

• integer adder(정수 가산기)보다 훨씬 더 복잡함

• 한 번의 clock cycle 안에 작업을 하기엔, cycle이 아주 오래 걸리게(느리게) 될 수 있음.
• integer operation보다 훨씬 느림.
• 느린 clock은 전체 instruction들을 전체적으로 불리하게(느리게) 만듦.

• 그러므로, FP adder는 일반적으로 여러 번의 cycle로 동작한다.
• pipeline화(병렬적으로) 될 수 있다.
• 하나의 명령에는 여러 cycle이 걸리지만, throughput을 높여 여러 개의 명령어를 동시에 실행하므로,　단위 시간당 FP adder의 가능한 작업의 수는 증가.
 

부동소수점 곱셈

1. F1과 F2의 hidden bit을 복구시킨다.

2. 지수간의 곱을 먼저 진행해준다.
1. 즉 E3 = E1 + E2 - bias 이다.

3. F1과 F2를 곱하여 F3를 double precision 형태로 표현해준다.

4. F3를 정규화한다.

5. Round to nearest even(반올림) 해준다.

6. E3과 F3을 이용해 부동소수점 표현으로 바꿔준다.

예시문제

MIPS Floating Point Instructions

• MIPS 부동소수점 load, store instruction

lwc1 $f1, 54($s2) # $f1 = Memory[$s2 + 54]
swcl $f1, 58($s4) # Memory[$s4 + 58] = $f1

• IEEE 754 single precision

add.s $f2,$f4,$f6 # f2 = $f4 + $f6

• IEEE 754 double precision

add.d $f2, $f4, $f6 # $f2 || f3 = $f4 || $f5 + $f6 || $f7

Right Shift and Division