컴퓨터구조(3) Computer Arithmetic

 

 

1. 정수의 연산

 

(1) Overflow

일반적인 수학에서는 무수히 많은 number들을 아무런 제약 없이 표현 가능하다. 그러나 digital systems에서는 number를 일정한 길이의 bits로 표현한다. 예를 들어 8bits, 16bits, 32bits 등 말이다. 8-bit number system의 경우, 표현할 수 있는 숫자의 개수는 2⁸ = 256개다. 양의 정수를 표현하는 경우 표현 가능한 숫자의 범위는 0(0000 0000) ~ 255(1111 1111)이다. 일반적으로 n-bit binary number system에서 unsigned number의 범위는 0 ~ (2ⁿ - 1)이다. 

Digital system에서 addition / subtraction 등 산술 연산 결과 값이 표현 가능한 숫자의 범위를 벗어날 때, overflow가 발생했다고 한다. 즉, 결과 값의 정확한 표현을 위해 정해진 word length n bits 이상이 필요한 경우를 의미한다. overflow발생 시 결과로서 남는 것은 원래 값과 다른 값을 갖게 된다. 

 

overflow의 예

 

위의 addition에서 bit position 4에 존재하는 carry는 버려지게 된다. 덧셈의 경우, MSB가 그 윗자리로 올라가는 carry가 1일 경우 overflow가 발생한다. 위의 overflow에서 정확한 연산 결과 값은 18이지만, 결과로서 남는 것은 2다. 정확한 결과 값을 2ⁿ로 나눈 나머지가 결과로서 남는 셈이다. 18 mod 16 = 2 = (0010)₂

 

 

subtraction을 살펴보자.  위의 식에서 M >= N 이면 2ⁿ는 버려지는 carry이므로 결과적으로 (M - N)이 남는다. 반대로 M < N이면 2ⁿ는 버려지는 carry가 아니게 되고, 결과로서 남는 것은 2ⁿ + M - N으로 잘못된 결과가 도출된다. 이러한 경우를 subtraction에서의 overflow라고 하며, borrow가 발생했다고 한다. 뺄셈은 carry가 0일 때 overflow가 발생한다. 

 

(2) Arithmetic in Sign and Magnitude

 

Sign and Magnitude	Sign	Magnitude	원리
뺄셈	.	.	(M - N) -> (M + (-N))
덧셈 (M, N의 sign이 같은 경우)	공통으로 가지는 sign	M + N	덧셈을 수행한다.
덧셈 (M, N의 sign이 다른 경우)	크기가 더 큰 것의 sign	M - N ( |M| > |N| 인 경우)	크기가 더 큰 숫자의 sign, 크기가 더 큰 숫자에서 뺄셈.

 

(3) Arithmetic in One's Complement

 

Sign and Magnitude	원리
뺄셈	(M - N)   -->   (M + (-N))
덧셈 (M, N이 모두 positive)	M + N
덧셈 (M, N이 모두 negative)	M + N + carry
덧셈 (M, N의 부호가 다름, M은 양수, N은 음수) (M <= N)	M + N'
덧셈 (M, N의 부호가 다름, M은 양수, N은 음수) (M > N)	M + N' + carry

 

4, 5번째 경우의 예시

 

1의 보수 덧셈은 unsigned number의 덧셈처럼 수행하되 carry가 1일 경우, 1을 더해서 보정한다.

 

(4) Arithmetic in Two's Complement

 

Sign and Magnitude	원리
뺄셈	(M - N)   -->   (M + (-N))
덧셈 (M, N이 모두 positive)	M + N
덧셈 (M, N이 모두 negative)	M + N (carry는 버린다.)
덧셈 (M, N의 부호가 다름, M은 양수, N은 음수) (M <= N)	M + N'
덧셈 (M, N의 부호가 다름, M은 양수, N은 음수) (M > N)	M + N'  (carry는 버린다.)

 

4, 5번째 경우의 예시

 

2의 보수 덧셈은 unsigned number의 덧셈처럼 수행한다. carry는 무조건 버린다. 

unsigned number와 마찬가지로 sigened number에서도 표현 가능한 범위를 벗어날 시 overflow가 발생한다. 2의 보수는 (- 2^n-1) ~ (+ 2^n-1 - 1)의 범위를 벗어날 때 overflow가 발생한다. 같은 sign인 두 수의 addition 또는 서로 다른 sign인 두 수의 subtraction에서 발생할 수 있다. [1] unsigned number에서의 overflow 검출은 덧셈의 경우 carry가 1일 때 overflow가 발생하고, 뺄셈의 경우 carry가 0일 때 overflow가 발생한다. [2] 2의 보수에서의 overflow 검출은 MSB로 올라오는 carry(carry-in)와 MSK에서 윗자리로 올라가는 carry(carry-out)가 서로 다를 경우 overflow가 발생한다. 

 

 

(5) 덧셈기, Adder

[1] 가장 기초적인 덧셈기인 Half Adder는 2개의 bit a[i]와 b[i]를 더하는 덧셈기다. 2개의 operand와 같은 자리의 sub bit s[i]와 한 자리수 위의 carry bit c[i+1]을 만들어낸다. 

 

 

 

[2] 각 자리에서의 덧셈은 2개의 operand bits a[i], b[i] 외에 아래 자리에서 올라온 carry c[i]를 고려해야 한다. Full Adder란 carry input bit를 포함해서 총 3개의 bits를 더하는 덧셈기를 말한다. 

 

 

 

[3] 위의 full adder들을 연결해서 만든 n-bit 덧셈기를 Ripple-Carry Adder라고 한다. 아래 그림은 4-bit ripple-carry adder를 나타낸다. 이들은 carry가 순차적으로 전달되는 구조를 가지며, carry가 모두 전달되는데 걸리는 delay가 크다. low speed. 

-> 여기서 c_in(c₀)는 왜 필요할까? 

 

 

[4] 32-bit 덧셈/뺄셈을 위한 하드웨어는 다음과 같다. sub = 0이면 덧셈을 수행하며, Result = a + b이다. sub = 1이면 뺄셈을 수행하며, Result = a + b' + 1 = a - b이다. 대부분의 경우 adder는 logical operation까지 같이 수행하는 ALU의 형태로 존재한다. 

 

32-bit addtion/subtraction

 

overflow 검사

 

(6) MIPS, ARM의 덧셈 및 뺄셈 명령어

 

MIPS	명령어	설명
Overflow를 detect함	add, addi, sub	overflow가 감지되면 exception을 발생시킴
Overflow를 무시함	addu, addiu, subu	overflow를 모두 무시함 -> unsigned 아님, addiu는 signed임  -> 위 명령어들과 동일한 덧셈, 뺄셈

 

MIPS의 명령어는 위와 같다. Exception이란 명령어 실행의 흐름을 변경하는 예기치 않은 이벤트다. interrupt라고 생각해도 된다. 이는 unscheduled procedure call로서, [1] exception을 발생시킨 instruction의 주소를 EPC(Exception Program Counter)라는 레지스터에 저장한다. [2] EPC 값은 $k0 혹은 $k1에 복사된다. 명령어 mfc0를 사용하여 mfc0 $k1, $epc와 같은 문법 구조를 가진다. [3] Exception에 대해서 정해진 address로 jump한다. 이 정해진 address가 jal 명령어의 타겟 주소다. [4] 작업이 종료된 후 jr $k0 혹은 jr $k1을 사용하여 return한다. $k0, $k1은 모두 operating system이 사용하도록 예약되어 있는 레지스터이고, 이들을 제외한 모든 register들은 exception 발생 이전의 값을 유지해야 한다. 

참고로 C에서는 arithmetic overflow를 무시하기 때문에 MIPS C compiler는 덧셈 및 뺄셈에 대해서 항상 addu, addiu 및 subu를 사용한 code를 생성한다. 

 

ARM	명령어	설명
V flag == 1일 때	BVS	branch if overflow set (V flag == 1)
V flag == 0일 때	BVC	branch if overflow set (V flag == 0)

 

ARM의 명령어는 위와 같다. ARM에서는 연산 overflow 시에 exception이 발생하지 않는다. 대신 overflow가 발생했을 경우 branch할 수 있는 2가지의 conditional branches가 존재한다. 

 

(7) multiplication

 

 

우리가 곱셈을 하는 방식은 위와 같다. 일반적으로 m bits x n bits 곱셈의 결과는 (m+n) bits다. 

 

MIPS	명령어	설명
Hi register Lo register	.	64-bit product의 상위 32bits 저장 64-bit product의 하위 32bits 저장
Multiply	mult $r1, $r2	$r1과 $r2를 signed로 곱하고 product를 {Hi, Lo}에 저장
Multiply unsigned	multu $r1, $r2	$r1과 $r2를 unsigned로 곱하고 product를 {Hi, Lo}에 저장
Move from Hi	mfhi $r1	Hi register를 $r1으로 가져옴
Move from Lo	mflo $r1	Lo register를 $r1으로 가져옴

 

ARM	명령어	설명
Multiply (32 x 32   ->   32)	MUL r2, r0, r1	r0와 r1을 곱하여 product의 low 32bits를 r2에 저장
Multiply unsigned (32 x 32   ->   64)	UMULL r2, r3, r0, r1	r0와 r1을 unsigned로 곱하여 product를 {r2, r3}에 저장
Multiply signed (32 x 32   ->   64)	SMULL r2, r3, r0, r1	r0와 r1을 signed로 곱하여 product를 {r2, r3}에 저장

 

각각 MIPS, ARM의 곱셈 관련 명령어들이다. ARM은 64bit product 전체를 저장하거나, 하위 32bits만 저장하는 방식으로 구성된다. 하위 32bits는 signed, unsigned일 때 동일한 값을 가지므로 1개의 명령어만 존재한다. 

 

(8) Divison 

 

 

우리가 나눗셈을 하는 방식은 위와 같다. Divisor를 뺄 수 있으면 해당 quotient bit는 1, 뺄 수 없으면 0. 

 

MIPS	명령어	설명
Hi register Lo register	.	Divison의 remainder 결과 저장 Division의 quotient 결과 저장
Divide	div $r1, $r2	$r1과 $r2를 signed로 나누고 quotient, remainder를 각각 저장
Divide unsigned	divu $r1, $r2	$r1과 $r2를 unsigned로 나누고 quotient, remainder를 각각 저장
Move from Hi	mfhi $r1	Hi register를 $r1으로 가져옴
Move from Lo	mflo $r1	Lo register를 $r1으로 가져옴

 

MIPS의 나눗셈 관련 명령어들이다. ARM은 나눗셈 명령어가 따로 존재하지 않는다. 

 

 

2. 실수의 연산

 

(1) scentific notation 

지금까지 다룬 수는 모두 정수(integer)다. 실수를 표현하는 방법 중 하나인 scientific notation를 알아보자. 

 

 

위 공식은 10진수에 대한 scientific notaion이다. Leading zero (0)가 없으며, decimal point 왼쪽에 단 1개의 digit만이 존재하는 scientific notation을 normalized number이라고 한다. 

 

normalized의 예시

 

 

위 공식은 2진수에 대한 scientific notaion이다. 동시에 normalized form의 예시기도 하다. 2진수를 위와 같은 형태로 표현하기 위해선 binary point를 이동시키고, 그에 합당하게 exponent를 조정해야 한다. 

 

(2) Floating point

Floating point란 binary point가 고정되지 않은 숫자를 나타내는 컴퓨터 연산이다. 컴퓨터에서는 floating point numver를 아래처럼 normalized form을 사용하여 표현한다. 해당 표현을 사용할 경우 실수 간 자료 교환이 간편해지며, 실수 연산이 간편해지며, 불필요한 leading zero들이 없기에 word에 저장되는 숫자의 정확성을 증가시킨다는 장점을 가진다. 

 

normalized form

 

IEEE 754 standard에 따르면 실수의 형식은 아래와 같다. 대부분 컴퓨터들이 이 표준을 따르고 있다. 

 

 

위 식에서 S는 sign으로 S=0이면 양수, S=1이면 음수다. E는 exponentm, Fraction은 xxx..xxx를 표시한다. 보다시피 IEEE 754에서는 implicit한 leading 1이 존재한다. IEEE 754는 biased notation을 사용하고, Bias = 01111111₂(127)이다. 즉 normalized number의 exponent 범위는 (- 126) ~ (127)이 된다. 

 

Significand는 24-bit, Fraction은 23-bit 숫자.

 

예를 들어 fraction bits가 01010111.. 이면, fraction은 .01010111..이고, significand는 1.01010111..이다. 

Simple comparison을 위한 IEEE 754 특징을 알아보자. 실수도 정수처럼 간단히 비교할 수 있다. [1] Sign bit가 MSB다. less than, greater than, or equal to 0의 비교를 간단하게 수행한다. [2] Exponent를 fraction 앞에 위치시킨다. Exponent가 큰 경우, exponent와 fraction을 합친 전체 bits의 크기가 크며, 실제로도 더 큰 값이다. 따라서 exponent와 fraction을 합친 bits들을 interger인 것처럼 비교하며, 실수의 크기 비교를 수행할 수 있다. [3] negative exponent는 biased notation을 사용하여 표기한다. 다른 표기법들은 더 작은 크기의 실수가 더 큰 수처럼 보이게 되지만, biased notation은 그렇지 않다. 최종적으로 표현하면 아래와 같다. 

 

 

이제, denormalized number들에 대해 설명하겠다. [1] Zeros는 implicit leading 1이라는 제약 조건 때문에 normalize하게 표현할 수 없다. Zeros는 exponent bits와 fraction bits가 모두 0이다. [2] Infinity는 실수 연산의 결과 overflow가 발생 시 (exception 발생이 아니라) +-무한대의 결과를 도출하는 방법에 적용된다. Dived by zero 연산 시에도 +-무한대의 결과를 도출을 위해 Infinity가 필요하다. exponent bits는 1111 1111이고, fraction bits는 0이다. [3] NaN란 말 그대로 '수가 아닌 것'이다. 0×∞, 0/0, ∞/∞ 등의 연산의 결과를 표현하기 위한 것이다. IEEE 754에는 Signaling NaN 및 quiet NaN 2가지를 규정하고 있다. 

 

Zeros

Infinity

NaN에 대한 IEEE 754의 표현 : 나중에 공부해보자 !

 

Denormalized Number란 0과 '가장 작은 normalized number' 사이의 gap을 채우기 위한 숫자다. exponent bits는 0이며, exponent value는 -126이다. fraction bits에는 최소 1개의 nonzero가 존재하며, impliciy leading 1이 존재하지 않는다. 가장 작은 수가 2^-149로서, 가장 작은 두 수 사이의 gap과 정확히 일치하는 값이다. 

 

 

앞서 설명한 IEE 754의 foating point에 대한 format으로 모든 실수를 당연히 표기할 수 없다. 그래서 overflow, underflow라는 2가지 경우가 발생할 수 있다. [1] Overflow는 연산 결과의 값이 너무 커서, exponent가 표현 범위를 벗어날 때 발생하며, [2] Underflow는 연산 결과의 값이 너무 작아서, exponent가 표현 범위를 벗어날 쌔 발생한다. Denormalized number의 경우도 underflow다. 이 경우를 특히 gradual underflow라고 한다. 이들은 더 넓은 범위의 수 표현이 가능한 Double precision으로 줄일 수 있다. double precision은 64bits로 표현되며, Bias는 1023이다. c언어에서 double이라는 자료형에 속한다. 

 

 

single precision을 정리한 표

double precision을 정리한 표

 

(3) Floating-Point arithmetic

부동 소숫점의 연산은 까다롭다. 'exponent'랑 'significant'를 분리하여 연산할 필요가 있다. 부동 소숫점 연산을 위한 하드웨어는 정수 연산 하드웨어와 비교해서 매우 복잡하고, 비용도 훨씬 더 크다. 

덧셈(addition)의 경우를 들어보자. [1] 지수가 더 큰 쪽으로 exponent 값을 통일한다. [2] significant 덧셈 연산을 수행한다. [3] normalize화한다. [4] fraction bit에 맞게 반올림 후, 잘라낸다. 

곱셈(multiplication)의 경우를 들어보자. [1] 지수의 값들을 더해준다. 예를 들어, 2와 2를 곱하는 경우라면 (-1) + (-2)를 수행해야 한다. 이런 경우 bias가 두 번 사용되어 중복되므로, bias를 한 번 빼야 한다. (-1 + 127) + (-2 + 127)이 되므로 해당 값에 (-127)을 더해주면, 124라는 결과가 exponent 결과 값이 된다. [2] significant 곱셈 연산을 수행한다. [3] normalize화한다. [4] fraction bit에 맞게 반올림 후, 잘라낸다. [5] 부호를 설정한다.

 

(4) Floating-Point intructions

MIPS를 예로 들면, 32개의 floating-point register들($f0 ~ $f31)이 별도로 존재한다. 이렇게 별도로 존재하는 이유는 [1] 더 많은 비트를 사용하지 않으면서 레지스터 수가 2배 증가하고, [2] 부동 소숫점 연산할 때 레지스터들을 customize할 수 있기 때문이다. 실제로 과거엔 floating-point unit이 coprocessor라는 별도의 chip으로 구현되었다. 

 

MIPS	single precision	double precision
덧셈	add.s	add.d
뺄셈	sub.s	sub.d
곱셈	mul.s	mul.d
나눗셈	div.s	div.d
비교 (x = eq, ne, lt, le, gt, ge)	c.x.s	c.x.d
로드 명령어	lwc1	lwc1
저장 명령어	swc1	swc1

 

ARM은 32개의 floating-point register들(s0 ~ s31)이 별도로 존재한다. double precision 연산 시 [1] MIPS는 even/odd pair가 묶여, 항상 Instruction format에서는 even 레지스터가 지정된다. [2] ARM은 odd/even pari가 묶이고, 32개의 sx 레지스터들을 16개의 dx 레지스터들로 pairing할 수 있어서 {s1, s0}의 묶음을 d0로 표현할 수 있다. 

 

(5) 실수 연산에 대한 몇 가지 고찰

제한된 precision으로 인한 rounding 효과 때문에 덧셈의 교환 법칙이 성립하지 않는 경우도 발생한다.