1/25 월 ~ 1/31 일 : 6시간 3분
1/27 수 : 2시간 1분
1/30 토 : 2시간 2분
1/31 일 : 2시간
3장 컴퓨터 연산
3.1 서론
- 소수나 실수는 어떻게 표헌?
- 컴퓨터로 표현할 수 있는 것보다 더 큰 수가 계산의 결과로 나오면?
- 하드웨어가 실제로 어떻게 곱셈, 나눗셈을 수행?
이 장의 목표는
1. 실수의 표현
2. 연산 알고리즘
3. 이러한 알고리즘을 수행하는 하드웨어
4. 이 모든 것들이 명령어 집합에 미치는 영향
3.2 덧셈과 뺄셈
손으로 계산할 때처럼 오른쪽에서 왼쪽으로 한 비트씩 더하고,
이때 생기는 올림수는 바로 왼쪽 자리로 보낸다.
연산 결과를 사용 가능한 하드웨어(이 경우 32비트 워드)로 표현할 수 없을 때
오버플로가 발생함을 상기하라.
덧셈에서는,
피연산자의 부호가 같을 경우에는 오버플로가 발생할 수 있다.
피연산자의 부호가 다를 경우에는 오버플로가 발생하지 않는다.
뺄셈에서는,
피연산자의 부호가 같을 경우에 오버플로가 발생하지 않고
피연산자의 부호가 다른 경우에 오버플로가 발생할 수 있다.
TABLE. 덧셈과 뺄셈에서의 오버플로 발생 조건
|
Operation |
Operand A |
Operand B |
Result indicating overflow |
|
A + B |
≥ 0 |
≥ 0 |
< 0 |
|
A + B |
< 0 |
< 0 |
≥ 0 |
|
A - B |
≥ 0 |
< 0 |
< 0 |
|
A - B |
< 0 |
≥ 0 |
≥ 0 |
실제로 오버플로가 발생했을 때는 탐지하는 방법
부호 비트를 크기를 나타내는 비트로 바꾼다.
연산시에 부호 비트로 올림수가 올라가므로 실제 연산 결과의 부호와 다른 부호가 저장된다.
따라서 두 양수를 더한 값이 음수가 되면 오버플로
두 음수를 더했는데 합이 양수가 되는 경우에도 오버플로가 발생한다.
여기까지가 컴퓨터에서 2의 보수법 사용 시 발생하는 오버플로의 탐지 방법이다.
그러면 부호없는 정수에서는 어떠한가?
부호없는 정수는 오버플로가 무시되는 메모리 주소에 사용된다.
그러므로 컴퓨터 설계자는 어떤 경우에는 오버플로를 무시하고
다른 경우에는 이를 인식하는 방법을 제공하여야 한다.
MIPS는 이 두 가지 선택을 지원하기 위해 두 가지 산술 명령어를 제공한다.
- 오버플로가 발생하면 예외(exception)을 발생
add(add), add immediate(addi), subtract(sub)
- 오버플로가 발생해도 예외를 발생시키지 않음
add unsigned(addu),add immediate unsignel(addiu), subtract unsigned(subu)
[하드웨어 소프트웨어 인터페이스]
컴퓨터 설계자는 연산 오버플로를 어떻게 처리할지 결정해야 한다.
C나 Java 같은 언어들은 정수 오버플로를 무시하지만,
Ada나 Fortran 같은 언어는 프로그램에게 알려지기를 요구한다.
따라서 프로그래머나 프로그래밍 환경은 오버플로 발생 시
어떻게 할 것인지를 결정하여야만 한다.
MIPS는 오버플로를 탐지하면 예외(exception) or 인터럽트(interrupt)를 발생시킨다.
예외나 인터럽트는 본질적으로 계획되지 않은 프로시저 호출이다.
오버플로가 발생한 명령어의 주소는 레지스터에 저장되고,
컴퓨터는 적절한 처리를 하기 위해서 해당 루틴으로 점프한다.
인터럽트가 걸린 주소를 저장해서,
해당 처리를 한 다음에 프로그램 실행을 계속할 수 있게 한다.
[요약]
수의 표현 방식과는 무관하게 산술연산 실행 결과는
고정된 크기의 컴퓨터 워드로는 표현할 수 없는 큰 결과가 발생할 수 있다는 점이 이 절의 요점이다.
3.3 곱셈
첫 번째 피연산자는 피승수(multiplicand)
두 번째 피연산자는 승수(multiplier)
최종 결과는 곱(product)
부호 비트를 무시한다면
n 비트의 피승수에 대한 m 비트 승수의 곱셈 결과는 n + m 비트의 길이를 갖는다.
따라서 곱셈에도 오버플로 문제가 있다.
곱셈 하드웨어와 알고리즘이 지난 수 세대 동안 어떻게 진화해 왔는지를 단계적으로 살펴보겠다.
당분간은 양수만을 곱한다고 가정하자.
[곱셈 알고리즘과 하드웨어의 순차적 버전]
곱셈 하드웨어의 첫 번째 버전
피승수(Multiplicand) 레지스터, ALU, 곱(Product) 레지스터는 모두 64비트이고,
승수(Multiplier)레지스터만 32비트이다.
시작할 때는 32비트 피승수가 피승수 레지스터의 오른쪽 절반에 있다가
매 단계마다 왼쪽으로 1비트씩 자리이동된다.
승수는 매 단계마다 오른족으로 1비트씩 자리이동된다.
알고리즘은 곱 레지스터를 0으로 초기화하고 시작된다.
제어는 피승수 레지스터와 승수 레지스터를 언제 자리이동 할지,
또 새로운 값을 언제 곱 레지스터에 쓸지를 결정한다.
곱셈 하드웨어 첫 번째 버전의 곱셈 알고리즘
최종 결과를 얻기 위해서 는 이러한 세 단계를 32번 반복해야 한다.
각 단계에서 한 클럭 사이클씩 필요하다면,
이 알고리즘은 32비트 숫자 두 개를 곱하는 데 거의 100개의 클럭 사이클이 걸린다.
이 알고리즘과 하드웨어는 매 반복이 한 클럭 사이클만 걸리도록 쉽게 바꿀 수 있다.
연산을 병렬로 수행함으로써 이러한 속도 향상이 가능해진다.
곱셈 하드웨어의 수정된 버전
첫 번째 버전과 비교해 보면,
피승수 레지스터, ALU, 승수 레지스터는 전부 32비트이고,
곱 레지스터만이 64비트이다.
이번에는 곱이 오른쪽으로 자리이동된다.
별도의 승수 레지스터는 없어졌다.
대신 승수를 곱 레지스터의 오른쪽 절반에 넣는다.
[부호있는 곱셈]
승수와 피승수를 양수로 변환하고 원래의 부호를 기억한다.
부호를 계산에서 제외시키고 31번 반복한 후,
피연산자들의 부호가 서로 다를 때만 곱을 음수로 바꾼다.
[더 빠른 곱셈]
빠른 곱셈 하드웨어
[MIPS에서의 곱셈]
MIPS는 64비트 곱을 저장할 수 있는 한 쌍의 32비트 레지스터를 별도로 제공한다.
이 것을 Hi 와 Lo 라고 불린다.
프로그래머는 32비트 정수 곱을 범용 레지스터로 가져오기 위해 mflo(move from lo) 명령어를 사용한다.
[요약]
곱셈 하드웨어도 단순히 자리이동과 덧셈을 수행한다.
더 많은 하드웨어를 사용하면 덧셈을 병렬로 더 빠르게 수행할 수도 있다.
3.4 나눗셈
나눗셈에서 피연산자는 피제수(dividend)와 제수(divisor) 두 개이고,
몫(quotient)이라 불리는 결과와 나머지(remainder)라고 불리는 두 번째 결과가 있다.
피제수 = 몫 x 제수 + 나머지
[나눗셈 알고리즘과 하드웨어]
존재하지 않는 이미지입니다.
나눗셈 하드웨어의 첫 번째 버전
제수(Divisor) 레지스터, ALU, 나머지(Remainder) 레지스터는 모두 64비트이고,
몫(Quotient) 레지스터만이 32비트이다.
32비트 제수는 제수 레지스터의 왼쪽 절반에서 시작해서
반복할 때마다 오른쪽으로 한 비트씩 자리이동한다.
나머지 레지스터는 피제수로 초기화된다.
제어는 언제 제수와 몫 레지스터를 이동시킬지,
그리고 언제 나머지 레지스터에 새로운 값을 저장할지를 결정한다.
위의 나눗셈 하드웨어를 이용하는 나눗셈 알고리즘
단계 1에서 나머지가 양수이면, 단계 2a에서 몫에 1를 저장한다.
단계 1에서 나머지가 음수이면, 단계 2b에서 몫에 0을 저장하고,
제수를 나머지에 더하여 단계 1의 뺄셈 이전 상태로 회복시킨다.
단계 3의 마지막 자리이동은
다음 번 반복의 계산을 위해 피제수에 맞추어 제수를 정렬시키는 것이다.
이러한 과정이 33번 반복된다.
[부호있는 나눗셈]
두 피연산자의 부호가 다를 경우에는 몫의 부호를 음수로 하고,
나머지가 0이 아니면 그 부호는 피제수의 부호를 따르게 한다.
[더 빠른 나눗셈]
곱셈과 같이 나눗셈에도 Moore의 법칙이 적용될 수 있으므로
하드웨어를 추가해서 나눗셈 성능을 향상시킬 수 있다.
[MIPS에서의 나눗셈]
MIPS는 곱셈과 나눗셈용 64비트 레지스터로 32비트 Hi와 Lo 레지스터를 사용한다.
위의 알고리즘에서 예측할 수 있듯이, 나눗셈 명령이 완료된 뒤
Hi는 나머지를, Lo는 몫을 갖는다.
MIPS 어셈블러는 범용 레지스터 세 개를 사용하는 나누기 의사명령어를 제공한다.
이 의사명령어는 mflo와 mfhi 명령어를 사용하여 원하는 결과를 범용 레지스터에 넣는다.
[요약]
MIPS는 같은 하드웨어가 곱셈과 나눗셈을 지원하므로,
32비트 레지스터 한 쌍을 두어서 곱셈과 나눗셈 양쪽에 모두 사용하고 있다.
여러 몫 비트를 동시에 예측하고 예측이 틀렸으면
나중에 바로잡는 방법으로 나눗셈을 빠르게 할 수 있다.
TABLE. MIPS assembly language
|
Category |
Instruction |
Example |
Meaning |
Comments |
|
Arithmetic |
multiply |
mult $s2, $s3 |
Hi, Lo = $s2 x $s3 |
64-bit signed product in Hi, Lo |
|
multiply unsigned |
multu $s2, $s3 |
Hi, Lo = $s2 x $s3 |
64-bit unsigned product in Hi, Lo |
|
|
divide |
div $s2, $s3 |
Lo = $s2 / $s3 Hi = $s2 mod $s3 |
Lo = quotient, Hi = remainder |
|
|
divide unsigned |
divu $s2, $s3 |
Lo = $s2 / $s3 Hi = $s2 mod $s3 |
Unsigned quotient and remainder |
|
|
move from Hi |
mfhi $s1 |
$s1 = Hi |
Used to get copy of Hi |
|
|
move from Lo |
mflo $s1 |
$s1 = Lo |
Used to get copy of Lo |
[하드웨어 소프트웨어 인터페이스]
MIPS 나눗셈 명령은 오버플로우를 무시하므로,
몫이 너무 커서 오버플로가 발생하거나 0으로 나누기 같은 부적절한 연산은 소프트웨어로 검사해야 한다.
3.5 부동소수점
프로그래밍 언어는 부호있는 정수와 부호없는 정수뿐만 아니라
소수 부분을 갖는 수도 다룰 수 있어야 한다.
수학에서는 이러한 수를 실수(reals)라고 부른다.
과학적 표기법
- 소수점의 왼쪽에는 한 자리 수만이 나타나게 하는 표기법
정규화된 수
- 선행하는 0이 없는 부동소수점 표기법으로 나타낸 수
이진수를 정규화된 형태로 표현하기 위해서는
소수점 왼쪽에 0 아닌 숫자가 한 자리만 나타나게 숫자를 자리이동한 후
자리이동 횟수만큼 증가시키거나 감소시킬 수 있는 기수(base)가 필요하다.
십진 소수점(decimal point)의 기수는 10
이진 소수점(binary point)의 기수는 2
이런 수를 지원하는 컴퓨터 연산은 부동소수점(floating point) 연산이라고 한다.
- 소수점의 위치가 고정되어 있지 않은 수로 표현하는 컴퓨터 연산
C 언어는 이러한 수를 나타내기 위해서 float라는 변수형을 사용한다.
실수를 정규화된 형태의 표준 과학적 표기법으로 나타내면 세 가지 좋은 점이 있다.
1. 부동소수점 숫자를 포함한 자료의 교환을 간단하게 한다.
2. 숫자가 항상 이런 형태로 표현된다는 것을 알고 있으므로 부동소수점 산술 알고리즘이 간단해진다.
3. 불필요하게 선행되는 0을 소수점 오른쪽에 있는 실제 숫자로 바꾸기 때문에 한 워드 내에 저장할 수 있는 수의 정밀도를 증가시킨다.
부동소수점 표현
부동소수점 표현 방식을 설계하는 사람은
소수부분(fraction)의 크기와 지수(exponent)의 크기 사이에서 타협점을 찾아야 한다.
소수부분의 크기를 증가시키면
소수부분으로 표현할 수 있는 수의 정밀도가 높아지고,
지수의 크기를 증가시키면
표현할 수 있는 수의 범위가 늘어난다.
MIPS의 부동소수점 표현
(-1)s X F X 2E
|
31 |
30 - 23 |
22 - 0 |
|
s |
exponent |
fraction |
|
1 bit |
8 bits |
23 bits |
표현 범위 : 2.0ten X 1038 ~ 2.0ten X 10-38
s는 부동소수점 수의 부호
지수는 8비트 지수 필드의 값(지수의 부호 포함)
소수부분은 23비트 수
이와 같은 표현 방식은 부호와 크기(sign and magnitude) 표현 방식이라고 한다.
왜냐하면 부호가 수의 나머지 부분과 떨어져 독립된 비트로 표현되기 때문이다.
오버플로 인터럽트는 정수 연산에서 뿐만 아니라 부동소수점 연산에서도 발생할 수 있다.
오버플로
- 양수 값을 갖는 지수가 지수 부분에 표현될 수 없을 만큼 큰 상황
언더플로
- 음수 값을 갖는 지수가 지수 부분에 표현될 수 없을 만큼 큰 상황
오버플로와 언더플로의 발생 가능성을 줄이는 방법으로
지수 부분이 더 큰 다른 표현 형식을 사용할 수 있다.
C 언어에서는 이것을 double이라고 부른다.
double 형식을 갖는 수의 연산은 2배 정밀도(double precision) 부동소수점 연산이다.
- 2개의 32비트 워드로 표현된 부동소수점 값
(float 형식은 단일 정밀도)
|
31 |
30 - 20 |
19 - 0 |
|
s |
exponent |
fraction |
|
1 bit |
11 bits |
20 bits |
|
fraction (continude) |
|
32 bits |
표현 범위 : 2.0ten X 10308 ~ 2.0ten X 10-308
이것들을 IEEE 754 부동소수점 표준으로서,
1980년 이후에 만들어진 컴퓨터는 거의 모두 이 표준을 사용하고 있다.
유효자리 부분에 더 많은 수를 담기 위해서
IEEE 754 표준은 정규화된 이진수의 가장 앞쪽 1비트를 생략하고 표현하지 않는다.
따라서 실제적으로 유효자리는
단일 정밀도 표현에서는 24비트의 길이를 갖고 2배 정밀도에서는 53비트의 길이를 가진다.
유효자리(significand)라는 용어는 숨겨진 1을 포함하는 24 또는 53비트를 나타내는 데 사용하고,
23 또는 52비트를 나타낼 때는 소수부분이라는 용어를 사용한다.
0을 제외한 나머지 수는 앞서 설명한 형식을 사용하므로 숨겨진 1을 덧붙이면
(-1)s X (1 + Fraction) X 2E
IEEE 754는 비정상적인 사건을 표현하는 특수 심벌이 있다.
TABLE. IEEE 754 부동소수점 수의 인코딩 방법
|
Single precision |
Double precision |
Object represented |
||
|
Exponent |
Fraction |
Exponent |
Fraction |
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
Nozero |
0 |
Nonzero |
± denormalized number |
|
1-254 |
Anything |
1-2046 |
Anything |
± floating-point number |
|
255 |
0 |
2047 |
0 |
± infinity |
|
255 |
Nonzero |
2047 |
Nonzero |
NaN (Not a Number) |
IEEE 754 설계자들은 정수 비교에 의해 쉽게 정렬(sorting)될 수 있는 부동소수점 표현을 원했다.
less than, greater than, equal to 0 테스트를 빠르게 할 수 있도록
부호 비트가 최상위 비트에 놓이게 되었다.
지수를 유효자리 앞에 두면 부호가 같은 수를 비교할 때
지수가 큰 수가 지수가 작은 수보다 더 큰 정수처럼 보인다.
이것은 부동소수점 수를 정수 비교 명령어로 정렬하는 일을 쉽게 해준다.
하지만 음수 지수는 숫자 정렬을 어렵게 만든다.
만약 음수를 나타내기 위해 2의 보수법이나 지수의 최상위 비트를 1로 만드는 다른 표현법을 사용한다면,
지수가 음수일때 매우 큰 수처럼 보일 것이다.
따라서 바이어스된 표현법(biased notation)을 이용해
가장 음수인 지수를 00...00으로, 가장 양수인 지수를 11,,,11로 표현한다.
바이어스는 실제 값을 구하기 위해 부호없이 표현된 수에서 빼야하는 상수를 말한다.
단일 정밀도 표현 방식은 바이어스 값이 127
2배 정밀도 표현 방식은 바이어스 값이 1023이다.
이것은 부동소수점으로 표현된 값이 실제로는 다음과 같음을 의미한다.
(-1)s X (1 + Fraction) X 2(Exponent - Bias)
부동소수점 덧셈
부동솟수점으로 표현된 수들의 덧셈을 이해하기 위해
먼저 과학적 표기법으로 표시된 두 수 9.999 X 101과 1.610 X 10-1을 손으로 더해보자.
유효자리에 네자리, 지수에 두 자리의 십진수를 저장할 수 있다고 가정한다.
단계1. 작은 수의 유효자리를 큰 수의 것과 일치할 대까지 오른쪽으로 자리이동시킨다.
1.610 X 10-1 = 0.01610 X 101
단계2. 유효자리를 서로 더한다.
9.999 + 0.0161 = 10.015
단계3. 이 합은 정규화된 과학적 표기법이 아니므로 정돈
10.015 X 101 = 1.0015 X 102
지수가 증가하거나 감소할 때마다 오버플로와 언더플로를 검사해야 한다.
단계4. 유효자리가 네 자리라고 가정했기 때문에 수를 자리맞춤(rounding) 헤야 한다.
1.0015 X 102 ---반올림---> 1.002 X 102
부동소수점 덧셈
일반적인 경우 단계3과 단계4는 한 번만 수행된다.
그러나 자리맞춤이 합을 비정규화하는 경우에는 단계 3을 반복해야 한다.
