[Computer Architecture] Arithmetic

"Arithmetic"

[Adder]

▣ RCA(Ripple Carry Adder)

· Carry가 한 bit씩 전달 → 느림

▣ CLA(Carry Lookahead Adder)

· Carry를 미리 계산 → 빠름

· G(Generate) / P(Propagate) → 병렬 계산 가능

[Multiplier]

· Multiplier = 1 → Multiplicand 복사 / Multiplier = 0 → 0
· 결과 bit 수 = m + n (4-bit x 5-bit → 9-bit)

▣ Multiplier Logic

① 128-bit Product Register가 0으로 초기화

② 64-bit Multiplicand는 128-bit Product Register의 하위 절반에 배치

③ 각 단계마다 왼쪽으로 Shift되어 Multiplicand가 Product Register에 누적
④ Multiplier는 매 단계마다 오른쪽으로 Shift

▣ Revised Multiplier Logic

· Multiplier Register는 Product Register의 하위 부분에 위치시켜 제거 가능

· Multiplicand 크기 축소 (128-bit → 64-bit)

· Product Register는 오른쪽으로 Shift

· Multiplier가 1인 경우 Multiplicand가 Product에 더해짐 / Multiplier가 0인 경우 단순히 오른쪽으로 Shift

∴ 곱셈 연산 = Shift + Add 반복

< 2 x 3 >

· Bit 수만큼 Step 진행 (4-bit → 4-Step)

· {Product + Multiplier}의 LSB = 1 : Multiplicand를 상위 Bit에 더한 후, 우측으로 Shift / 0 : 우측 Shift만 진행

· 마지막 단계의 {Product + Multiplier} LSB = 1: Multiplicand를 상위 Bit에서 뺀 후, 우측으로 Shift / 0 : 우측 Shift만 진행

▣ Signed Multiplication

· 2의 보수 표현을 통해 부호를 제거하여 절댓값으로 변환

· Multiplicand와 Multiplier의 부호가 다르면 Product의 부호는 반전

· mul : 128-bit 곱의 하위 64-bit 반환

· mulh : 128-bit 부호 있는 곱의 상위 64-bit 반환

· mulhu : 128-bit 부호 없는 곱의 상위 64-bit 입력

▣ Avoiding Multiply Operations

· 덧셈/뺄셈 : 1 Cycle / 곱셈 : 여러 Cycle → 곱셈 연산은 오래 걸림

· Compiler는 곱셈 연산이 2의 거듭 제곱인 경우 곱셈 명령어를 Shift 명령어로 대체

[Divider]

· 나눗셈은 곱셈보다 사용 빈도는 낮지만 계산 방식이 독특 (나눗셈 = 반복적인 뺄셈)

· Dividend = Quotient x Divisor + Remainder

· Divisor를 빼보고 가능하면 Quotient = 1 / 불가능하면 복원 → 구현 매우 복잡

▣ Divider Logic

① 64-bit Quotient Register가 0으로 초기화, Remainder Register는 Dividend로 초기화
② Divisor는 Register의 상위 절반에 위치되고 각 단계마다 오른쪽으로 Shift

③ Devidend에서 Divisor를 뺀 결과가 양수 → Quotient = 1 / 뺀 결과가 음수 → 복원 + Quotient = 0

** Subtract → 실패 시 Restore

▣ Revised Divider Logic

· Quotient는 Remainder Register의 하위 절반 부분에 위치시켜 제거 가능

· Divisor 크기 축소 (128-bit → 64-bit)

· Remainder Register는 왼쪽으로 Shift

· Remainder가 양수인 경우 Quotient = 1 / Remainder가 음수인 경우 이전 값으로 복원 + Quotient = 0

∴ Shift + Subtract + Restore 반복

< 7 ÷ 2 >

· Bit 수만큼 Step 진행 (4-bit → 4-Step)

▣ Signed Division

· 2의 보수 표현을 통해 부호를 제거하여 절댓값으로 변환

· Divisor와 Dividend의 부호가 다르면 Quotient와 Remainder의 부호는 반전)

· div : 나눗셈 연산 수행

· divu : 부호 없는 나눗셈 수행

· rem : 부호 있는 나눗셈의 나머지를 반환

· remu : 부호 없는 나눗셈의 나머지를 반환

[Real Number]

▣ Normalization

· 소수점 왼쪽에 항상 1자리만 존재 (0.123 x 10⁴ 또는 10.23 x 10² → 비정상)

▣ IEEE 754 Floating Point Standard

· MSB([31]) : 부호

· 8-bit([30:23]) : 지수 부분

· 23-bit([22:0]) : 소수 부분

· 0 = 32-bit 모두를 0으로 설정

> Fraction

· 소수점 왼쪽 부분은 암묵적으로 1 (Fraction = 0.101 → 실제 = 1.101) → 1 + ([22]x2^-1 + [21]x2^-2 + … + [0]x2^-23)

> Exponent

· Bias 표기법 사용 (Exponent = 129₁₀ → 실제 = 129 - 127 = 2) → Exponent의 실제 범위 = -126~127

** Exponent = 00…001 → 소수점 앞 = 1 → 1.xxxx × 2^{1 - Bias} / Exponent = 00…000 → 소수점 앞 = 0 → 0.xxxx × 2^{1 - Bias}

∴ (-1)^Sign x 2^{(Exponent - 127)} x (1 + Fraction)

Ex. - 0.75

① - 0.75 = - (0.5 + 0.25) = - (2^-1 + 2^-2)

② - (2^-1 + 2^-2) = - 2^-1 x (1 + 2^-1)

③ Sign = 음수 / Exponent - 127 = -1 / Fraction = (1 + 2^-1)

∴ 1_01111110_10000000000000000000000

Ex. 1_10000001_01000000000000000000000

① Sign = 음수

② Exponent = 129 → 2

③ Fraction = 1.01 = (1 + 2^-2)

∴ (-1)¹ x 2² x (1 + 2^-2) = - 5.0

▣ Denormalized Numbers

∴ (-1)^Sign x 2^{(Exponent - 127)} x (Fraction)

▣ Trade-Off Between Fraction & Exponent

· Fraction bit 수↑ : Fraction 부분의 정밀도↑ / Exponent bit 수↑ : 숫자의 범위 확장

[Overflow/Underflow]

· Overflow : 지수가 너무 커서 표현 불가한 경우 / Underflow : 0이 아닌 소수 부분이 너무 작아서 표현 불가한 경우

▣ Double Precision

· Overflow/Underflow 발생 가능성을 줄이는 방법 = 지수와 소수 부분을 표현하는 데 더 많은 bit(64-bit) 사용

· MSB([63]) : 부호

· 11-bit([62:52]) : 지수 부분

· 52-bit([51:0]) : 소수 부분

▣ Exceptions & Traps

<FCSR>

· 일반 CPU : Overflow/Underflow 발생 시 Exception이 발생하여 현재 실행을 중단하고 CPU의 제어권을 OS로 넘김

    → OS는 미리 정의된 Procedure를 실행하여 예외 처리

· RISC-V : Overflow/Underflow에 대해 Exception 발생 X

    → 단순히 FCSR(Floating-Point Control and Status Register)에 Overflow/Underflow가 발생했음을 표시

[Adding Floating-Point]

· 9.999 x 10¹ + 1.61 x 10^-1

① 지수 맞추기 : 지수가 다르면 바로 더할 수 없으므로 작은 값을 큰 값 기준으로 맞춤 (1.61 x 10^-1 → 0.0161 x 10¹)

② 정밀도 제한 : HW는 bit 수 제한이 존재하여 손실 발생 (0.0161 → 0.016)

③ 덧셈 : (9.999 x 10¹ + 0.016 x 10¹ = 10.015 x 10¹)

④ 정규화 : 항상 1.xxx 형태로 만들어야 함 (10.015 x 10¹ → 1.0015 x 10²)

⑤ Overflow/Underflow 확인

⑥ 반올림 : Fraction 길이 제한 (1.0015 x 10² → 1.002 x 10²)

** 부호가 같은 경우 : 덧셈 진행 후, 양수 부호 사용 / 부호가 다른 경우 : 뺄셈 진행 후, 절댓값이 큰 수의 부호 사용

Ex. 0.5 + (- 0.4375)

· 0.5 = (-1)⁰ x 2^-1 x (1 + 0) = 1.0 x 2^-1 / - 0.4375 = (-1)¹ x 2^-2 x (1 + 2^-1 + 2^-2)

① (-1)¹ x 2^-2 x (1 + 2^-1 + 2^-2) → (-1)¹ x 2^-1 x (2^-1 + 2^-2 + 2^-3)

② {(1 + 0) - (2^-1 + 2^-2 + 2^-3)} x 2^-1 = 2^-3 x 2^-1 = 2^-4

③ Overflow/Underflow 확인

④ (1 + 0) x 2^-4 = 0.0625

[Multiplying Floating-Point]

Ex. (1.11 x 10¹⁰) x (9.2 x 10^-5) (Decimal Multiplication)
· 지수는 더함 / 가수는 곱함

** (10 + 127) + (-5 + 127) → X (Bias를 한 번에 계산)

① 곱셈 : (1.11 x 10¹⁰) x (9.2 x 10^-5) = 10.212 x 10⁵

② 정규화 : 10.212 x 10⁵ → 1.0212 x 10⁶

③ Overflow/Underflow 확인

④ 반올림 : 1.0212 x 10⁶ → 1.021 x 10⁶

Ex. 0.5 x (- 0.4375)

· 0.5 = (-1)⁰ x 2^-1 x (1 + 0) = 1.0 x 2^-1 / - 0.4375 = (-1)¹ x 2^-2 x (1 + 2^-1 + 2^-2)

① 곱셈 : (1.0 x 2^-1) x (-1)¹ x 2^-2 x (1 + 2^-1 + 2^-2) = (-1)¹ x 2^-3 x (1 + 2^-1 + 2^-2) = - 0.21875

② Overflow/Underflow 확인

③ Sign = 1 / Exponent = 124 / Fraction = 11000…

[Floating-Point Instructions]

· Single Precision(32-bit) / Double Precision(64-bit) 각각 지원

· 정수 Register와 별도로 Floating-Point 전용 Register 32개 존재 (정수 : x0 ~ x31 / 실수 : f0 ~ f31)

① 메모리에서 데이터 Load

② 실수 나눗셈

③ 실수 뺄셈

④ 실수 곱셈

⑤ 함수 반환

[Accuracy of Floating-Point]

· Floating-Point 수는 실수를 정확히 저장하는 것이 아니라, 실수를 근사해서 저장 → Rounding

· Rounding을 정확하게 하기 위해 HW가 추가로 보는 Bit 존재

▣ Guard Bit

· 저장할 마지막 Bit 바로 다음 Bit로, 가장 먼저 잘려나가는 Bit → 버려지는 부분이 어느 정도 큰지를 판단

▣ Round Bit

· Guard Bit 다음에 오는 Bit로, 이 Bit까지 함께 보면, 단순히 "조금 넘었는지" 아니면 "꽤 넘었는지"를 더 잘 판단 가능

▣ Sticky Bit

· Sticky Bit는 그 뒤에 나오는 나머지 모든 Bit의 OR (뒤에 남은 Bit들 중 하나라도 1 : Sticky Bit = 1 / 전부 0 : Sticky Bit = 0)

→ 잘려나간 부분이 단순히 "정확히 절반인지", "절반보다 큰지" 구별하는 데 도움

[Reference]

· 3_arithmetic (Computer Architecture) - William J. Song