Ch3. Arithmetic

Introduction: 3단원이 하려는 일

• 3단원은 컴퓨터가 숫자를 어떻게 표현하고, 그 숫자들에 대해 덧셈, 뺄셈, 곱셈, 나눗셈, 부동소수점 연산을 어떻게 수행하는지를 다루는 단원이다.
• 2단원이 “명령어를 어떻게 쓰는가"에 가까웠다면, 3단원은 그 명령어 뒤에서 실제 숫자 연산이 어떤 원리로 이루어지는가를 설명한다.
• 슬라이드도 초반에 정수 연산, overflow 처리, multiplication/division, floating-point representation과 operation이 이 단원의 핵심이라고 정리한다.

1. Integer Addition and Subtraction

정수 덧셈의 핵심

• 정수 덧셈 자체는 비트 단위로 carry를 넘기면서 수행한다.
• 예를 들어 슬라이드는 7 + 6 예시를 들면서, 각 자리에서 carry가 다음 자리로 넘어가는 일반적인 이진 덧셈 과정을 보여 준다.
• 여기서 중요한 건 단순히 “더한다"가 아니라, 결과가 표현 가능한 범위를 벗어나는지, 즉 overflow가 발생하는지를 함께 봐야 한다는 점이다.

덧셈에서 overflow가 언제 나는가

• signed integer 덧셈에서는 다음 감각이 중요하다.
  • 양수 + 음수는 보통 overflow가 나지 않는다.
  • 양수 + 양수인데 결과 부호가 음수가 나오면 overflow다.
  • 음수 + 음수인데 결과 부호가 양수가 나오면 overflow다.
• 즉 덧셈에서 overflow는 “같은 부호끼리 더했는데 결과 부호가 뒤집힐 때“라고 기억하면 된다. 슬라이드의 overflow 표도 이 조건을 정리하고 있다.

뺄셈의 본질

• 뺄셈은 별도 회로를 새로 만드는 것이 아니라, 두 번째 피연산자의 음수를 더하는 것으로 처리한다.
• 즉 A - B = A + (-B) 다.
• 슬라이드도 7 - 6 = 7 + (-6) 예시를 들고, -6을 2의 보수로 만들어 덧셈으로 처리하는 흐름을 보여 준다.

뺄셈에서 overflow

• 뺄셈에서는 감각이 약간 다르다.
  • 양수 - 양수, 음수 - 음수는 보통 overflow가 나지 않는다.
  • 음수에서 양수를 빼는데 결과가 양수면 overflow다.
  • 양수에서 음수를 빼는데 결과가 음수면 overflow다.
• 직관적으로는, “실제로는 더 큰 절댓값 방향으로 가야 하는데, 비트수 제한 때문에 반대로 튀는 경우“라고 보면 된다.

2. Overflow를 왜 따로 신경 써야 하는가

비트 수는 유한하다

• 컴퓨터의 정수 표현은 비트 수가 정해져 있다.
• 즉 표현 가능한 범위가 항상 유한하다.
• 그래서 수학적으로는 맞는 결과라도, 정해진 비트 수 안에 안 들어오면 결과가 잘려서 엉뚱한 값처럼 보일 수 있다.
• 이게 overflow의 본질이다.

3단원에서 overflow가 중요한 이유

• 뒤에서 곱셈이나 부동소수점도 결국 같은 문제를 가진다.
• 즉 “비트가 한정되어 있으니, 표현 범위와 정밀도 한계가 있다"는 것이 3단원 전체를 관통하는 메시지다.
• 정수 overflow는 그중 가장 단순한 첫 사례라고 보면 된다.

3. Multiplication

곱셈은 long multiplication에서 출발한다

• 슬라이드는 곱셈을 우리가 손으로 하던 **세로셈(long multiplication)**에서 출발시킨다.
• 예를 들어 1000 × 1001을 보면, multiplier의 각 비트를 보면서 1이면 multiplicand를 해당 자리만큼 더하고, 0이면 아무것도 더하지 않는다.
• 즉 이진 곱셈은 결국 partial product들을 더하는 과정이다.
• 또 결과 길이는 피연산자 길이의 합만큼 필요할 수 있다. 즉 n비트 × n비트는 최대 2n비트 결과가 필요하다.

기본 곱셈 하드웨어의 아이디어

• 기본 회로는 대충 이렇게 움직인다.
  1. multiplier의 오른쪽 끝 비트를 검사한다.
  2. 그 비트가 1이면 multiplicand를 product에 더한다.
  3. multiplicand는 왼쪽으로 shift한다.
  4. multiplier는 오른쪽으로 shift한다.
  5. 이걸 반복한다.
• 슬라이드의 기본 multiplier hardware도 이 흐름을 따른다. product는 처음에 0으로 시작한다.

2 × 3 예시로 보는 shift-and-add

• 슬라이드의 대표 예시는 4비트로 2 × 3, 즉 0010 × 0011이다.

• 여기서는

  • multiplier의 LSB가 1이면 product에 multiplicand를 더하고
  • 그다음 multiplicand는 left shift
  • multiplier는 right shift

  를 반복한다.

• 그래서 결국 0000 0110, 즉 6이 나온다.

• 즉 하드웨어 수준의 이진 shift-and-add 곱셈 과정이다.

optimized multiplier

• 기본 회로는 multiplicand와 multiplier를 따로 shift시키는데, 이를 더 효율적으로 바꾸면 product register 안에 multiplier 일부를 같이 담고, add와 shift를 더 병렬적으로 처리할 수 있다.
• 슬라이드는 optimized multiplier에서 한 cycle마다 partial-product addition 하나를 처리하는 구조를 보여 준다.
• 핵심은 “같은 일을 더 적은 hardware movement로 하도록 구조를 재배치했다"는 점이다.

faster multiplier

• 더 빠른 곱셈기는 아예 여러 adder를 사용해서 partial product들을 병렬적으로 줄여 나간다.
• 이건 당연히 더 비싸다.
• 즉 여기서는 전형적인 cost/performance tradeoff가 나온다.
• 대신 pipeline도 가능해서 여러 곱셈을 겹쳐 수행할 수 있다.

MIPS multiplication

• MIPS에서는 곱셈 결과가 64비트가 될 수 있으므로 HI/LO 두 레지스터를 사용한다.
  • HI: 상위 32비트
  • LO: 하위 32비트
• 주요 명령은
  • mult, multu
  • mfhi, mflo
  • mul
• mult/multu는 64비트 결과를 HI/LO에 넣고, mfhi/mflo로 꺼내 온다.
• mul은 결과의 하위 32비트만 목적 레지스터에 넣는다.
• 또 HI 값을 보면 곱셈 결과가 32비트를 넘쳤는지 확인할 수 있다.

4. Division

나눗셈도 long division에서 출발한다

• 나눗셈도 곱셈과 마찬가지로, 사람이 손으로 하는 long division에서 출발한다.
• 아이디어는 이렇다.
  • divisor가 현재 dividend/remainder 부분보다 작거나 같으면 뺀다.
  • 그러면 quotient에 1비트를 세운다.
  • 너무 크면 못 빼므로 quotient에 0비트를 넣고 다음 자리로 넘어간다.
• 즉 나눗셈은 “뺄 수 있으면 빼고 1, 못 빼면 0"을 반복하는 과정이다.

restoring division

• 슬라이드에서 소개하는 기본 방식은 restoring division이다.
• 먼저 divisor를 빼 본 다음, remainder가 음수가 되면 “아, 너무 많이 뺐네” 하고 divisor를 다시 더해 원상복구한다.
• 그래서 restoring이라는 이름이 붙는다.

signed division

• signed division은 절댓값으로 먼저 나눈 뒤, 마지막에 quotient와 remainder의 부호를 조정하는 식으로 생각하면 된다.
• 즉 핵심 나눗셈 알고리즘 자체는 unsigned 쪽 감각으로 보고, sign 처리를 나중에 붙이는 구조다.

division hardware

• 나눗셈 하드웨어는 divisor와 remainder를 두고,
  • remainder에서 divisor를 빼 보고
  • 결과가 음수인지 검사한 뒤
  • quotient 비트를 정하고
  • divisor를 shift하는 방식으로 동작한다.
• 슬라이드 그림에서도 divisor는 왼쪽 절반에 크게 맞춰 놓고 시작하고, remainder 쪽과 ALU가 상호작용하는 구조를 보여 준다.

7 ÷ 2 예시

• 슬라이드는 Dividend = 7, Divisor = 2 예시를 상세 표로 보여 준다.

• 결과는

  • quotient = 3
  • remainder = 1

• 이다.

• 표를 보면, 각 단계마다

  • R = R - D
  • 음수면 restore
  • quotient에 0 또는 1 반영
  • divisor shift

  가 반복된다.

• 결국 7을 2로 나눈 몫 3, 나머지 1을 하드웨어 단계로 풀어낸 예시다.

optimized divider

• optimized divider는 곱셈기처럼 회로를 더 정리해서 한 cycle마다 partial remainder subtraction을 수행하게 만든 구조다.
• 슬라이드가 “looks a lot like a multiplier"라고 표현하듯, optimized multiplier와 optimized divider는 구조적으로 꽤 닮아 있다.
• 심지어 같은 hardware를 어느 정도 공유할 수도 있다는 점을 강조한다.

faster division은 왜 곱셈보다 까다로운가

• 곱셈은 partial products를 병렬적으로 더하는 방식이 쉬운 편인데, 나눗셈은 “이번 subtraction 결과의 부호"가 다음 동작을 결정하므로 완전 병렬화가 더 어렵다.
• 그래서 faster divider는 여러 quotient bit를 한 번에 추정하는 방식(SRT 같은 방식)을 쓰지만, 여전히 여러 단계가 필요하다.

MIPS division

• MIPS division도 HI/LO를 사용한다.
  • HI: remainder
  • LO: quotient
• 명령은 div, divu이다.
• 중요한 점은 MIPS가 overflow나 divide-by-zero를 자동으로 검사해 주지 않는다는 것이다.
• 필요하면 software가 직접 체크해야 한다.
• 결과는 mfhi, mflo로 꺼낸다.

5. Floating Point

왜 floating point가 필요한가

• 정수만으로는 소수, 아주 큰 수, 아주 작은 수를 유연하게 표현하기 어렵다.
• 그래서 컴퓨터는 실수를 scientific notation 비슷한 방식으로 표현한다.
• 슬라이드는 이를 \pm 1.xxxxx \times 2^y 꼴의 이진 과학적 표기라고 설명한다.
• 즉 floating point의 핵심은 **가수(significand)**와 **지수(exponent)**로 수를 나누어 표현하는 것이다.

IEEE 754 standard

• 부동소수점 표현은 IEEE 754 표준을 따른다.
• 이 표준이 중요한 이유는, 예전에는 시스템마다 표현 방식이 달라 scientific code portability에 문제가 있었기 때문이다.
• 표준화 덕분에 대부분의 시스템이 비슷한 방식으로 float/double을 다루게 되었다.

single / double precision

• single precision은 32비트, double precision은 64비트다.

• 구성은 대략

  • sign bit
  • exponent
  • fraction

  으로 나뉜다.

• normalized number에서는 맨 앞이 항상 1.xxxx 꼴이므로, leading 1은 저장하지 않고 숨긴다. 이것이 hidden bit다.

• exponent는 bias를 더한 형태로 저장한다.

  • single bias = 127
  • double bias = 1023

• 이 구조를 이해해야 뒤의 encoding/decoding 예시를 볼 수 있다.

표현 가능한 범위

• single precision은 대략 \pm 1.2 \times 10^{-38} \sim \pm 3.4 \times 10^{38} 정도 범위를 가진다.

• double precision은 훨씬 더 넓다.

• 또 exponent의 all-0, all-1 패턴은 특별한 의미를 가진다.

  • 아주 작은 값
  • infinity
  • NaN

  같은 것들이다.

예시: -0.75를 표현하기

• -0.75는 이진수로 보면 -0.75 = -0.11_2 = -1.1_2 \times 2^{-1} 꼴로 쓸 수 있다.

• 그래서

  • sign = 1
  • exponent = -1 + bias
  • fraction = 1000...

  식으로 들어간다.

• 슬라이드는 single과 double 각각에 대해 이 비트 패턴을 보여 준다.

예시: 비트 패턴을 실수로 해석하기

• 반대로 11000000101000...00 같은 single-precision 비트열을 주고, 이게 어떤 수인지 해석하는 예시도 나온다.

• 여기서는

  • sign = 1
  • exponent = 129
  • fraction = 01000...

  이므로 최종 값은 -5.0이 된다.

• 즉 floating point 문제는 “수 → 비트"와 “비트 → 수"를 둘 다 할 줄 알아야 한다.

6. Floating-Point Addition

FP 덧셈은 정수 덧셈보다 훨씬 복잡하다

• 정수 덧셈은 그냥 자리 맞춰 더하면 되지만, 부동소수점 덧셈은 먼저 지수를 맞춰야 한다.
• 슬라이드는 과정을 4단계로 설명한다.
  1. exponent alignment
  2. significand addition
  3. normalization
  4. rounding
• 즉 FP addition의 본질은 “소수점 자리를 맞춘 뒤 더하고, 다시 normalized form으로 돌려놓는 과정“이다.

binary example

• 슬라이드 예시에서는 1.000_2 \times 2^{-1} + (-1.110_2 \times 2^{-2}) 같은 식을 다룬다.
• 먼저 더 작은 exponent 쪽을 shift해서 지수를 맞춘 뒤,
• significand를 더하고,
• 결과가 0.001 × 2^{-1}처럼 나오면 다시 normalize해서 1.000 \times 2^{-4} 로 바꾼다.
• 즉 정답 숫자만 보는 게 아니라, alignment → addition → normalization의 흐름을 따라가는 게 중요하다.

FP adder hardware

• FP adder는 integer adder보다 훨씬 복잡하다.
• exponent 비교, shift, add, normalize, round 같은 단계가 필요하기 때문이다.
• 그래서 보통 한 cycle에 끝내기 어렵고, 여러 cycle에 걸쳐 수행되며 pipeline도 가능하다.

7. Floating-Point Multiplication

FP 곱셈의 핵심 흐름

• FP multiplication은 FP addition보다 구조가 오히려 더 직관적이다.
• 기본 단계는
  1. exponent를 더한다
  2. significand를 곱한다
  3. normalize한다
  4. round한다
  5. sign를 결정한다
• 이다.

binary example의 감각

• 슬라이드 예시에서는 1.000_2 \times 2^{-1} \times (-1.110_2 \times 2^{-2}) 를 다룬다.
• exponent는 -1 + -2 = -3,
• significand는 1.000 × 1.110 = 1.110,
• sign는 양수 × 음수이므로 음수,
• 그래서 최종 결과는 -1.110_2 \times 2^{-3} , 즉 -0.21875가 된다.

FP arithmetic hardware

• FP multiplier도 FP adder만큼 복잡하다.

• 다만 significand 연산에서 adder 대신 multiplier를 쓴다는 차이가 있다.

• 실제 FP hardware는 보통

  • add
  • sub
  • mul
  • div
  • reciprocal
  • square root
  • FP↔integer conversion

  등을 지원한다.

• 역시 여러 cycle이 걸리고 pipeline 가능하다.

8. FP Instructions in MIPS

coprocessor 1

• MIPS에서 floating-point hardware는 coprocessor 1로 취급된다.
• 정수 레지스터와 별도의 FP 레지스터 집합을 사용한다.
• 즉 FP 연산은 정수 레지스터가 아니라 $f0 ~ $f31 같은 FP 레지스터에서 일어난다.

주요 명령

• load/store:
  • lwc1, ldc1, swc1, sdc1
• single:
  • add.s, sub.s, mul.s, div.s
• double:
  • add.d, sub.d, mul.d, div.d
• compare:
  • c.xx.s, c.xx.d
• branch:
  • bc1t, bc1f
• 즉 정수 MIPS와 별개로, FP용 instruction set이 따로 있다고 보면 된다.

화씨 → 섭씨 예시

• 슬라이드는

float f2c(float fahr) {
    return ((5.0/9.0) * (fahr - 32.0));
}

• 예시를 MIPS FP 명령으로 바꿔 보여 준다.
• 여기서는 상수 5.0, 9.0, 32.0을 memory에서 FP register로 load하고,
• div.s, sub.s, mul.s를 차례로 수행해 결과를 $f0에 둔다.
• 이 예시는 FP register가 어떻게 쓰이는지 감 잡기 좋다.

9. Accurate Arithmetic, SIMD, Associativity

rounding과 정확도

• IEEE 754는 단순한 표현 형식만 정하는 게 아니라, rounding control도 포함한다.
• guard, round, sticky bit 같은 추가 비트를 두어 반올림 정확도를 높인다.
• 하지만 모든 하드웨어가 모든 옵션을 구현하는 것은 아니고, 대부분의 언어/라이브러리는 기본 설정만 사용한다.
• 즉 정확도는 항상 hardware complexity와 tradeoff를 가진다.

subword parallelism / SIMD

• 그래픽, 오디오처럼 짧은 데이터 여러 개에 같은 연산을 반복하는 경우에는 SIMD가 유용하다.

• 예를 들어 128-bit adder 하나로

  • 16개의 8-bit 덧셈
  • 8개의 16-bit 덧셈
  • 4개의 32-bit 덧셈

  을 병렬적으로 처리할 수 있다.

• 즉 같은 명령 하나로 여러 데이터에 동시에 연산하는 data-level parallelism이다.

associativity가 깨질 수 있다

• 수학에서는 보통 (x+y)+z = x+(y+z) 라고 생각하지만, floating point에서는 rounding 때문에 꼭 그렇지 않다.
• 슬라이드는 큰 수와 작은 수를 섞으면 연산 순서에 따라 결과가 달라질 수 있음을 보여 준다.
• 그래서 병렬 프로그램에서는 특히 “연산 순서가 바뀌어도 결과가 같은가?“를 조심해야 한다.

왜 FP accuracy가 중요하냐

• scientific code에서는 당연히 중요하고,
• 소비자 입장에서도 “조금 틀려도 되지 않나?“가 잘 통하지 않는다.
• 슬라이드는 Intel Pentium FDIV bug를 예로 들며, 시장은 정확성을 기대한다고 말한다.