CPU 기초

2019-03-08

Computer Engineering

CPU = ALU + CU + Register

ALU(Arithmetic Logic Unit)
- 산술논리연산 장치
- +, -, *, /, &, |, ^의 비교, 판단, 연산 담당
CU(Control Unit)
- 제어 장치
- 명령어 해석과 실행을 담당

CPU의 메모리
32bit 컴퓨터는 레지스터도 32bit

EAX, ECX 등등

# 아래 연산이 이루어질때
# a = 10, b = 20, c = 30이 RAM에 기록됨
# 하지만 연산 과정은 RAM에서 a의 값이 CPU 레지스터 EAX에, b는 ECX에 기록
# 그리고 ALU를 통해 연산된 후, c = 30이 EAX에 기록된 다음, RAM으로 다시 값이 기록
# RAM에서 계산되는 것이 아니다!
a = 10
b = 20
c = a+b

print(c)
>> 30

CPU 정수의 곱셉과 나눗셈
- CPU는 전가산기로 계산되기 때문에 빼기는 보수기(2의 보수)를 통해 연산
- 곱셉과 나눗셈은 Shifter(비트 이동)를 통해 연산
  - 곱셉은 레지스터 2개 필요
  - Shifter 되는 수 = 지금 사용되는 bit의 수
  - 4비트 값이 계산되면 Shift는 4번 됨(비트의 수만큼 Shift 됨)

실수(real number)

고정소수점 : 정밀도가 높으나, 표현 범위가 좁아 쓰지 않는다.
부동소수점(floating point) : 정밀도가 낮으나, 표현 범위가 넓기 때문에 쓰인다.
- 부동소수점은 IEEE 표준에 따름
- 소수점이 이동한다고 하여 floating point라고 함
- 1023.0 x 10^0 = 102.3 x 10^1 = 10.23 x 10^2 = 1.023 x 10^3
- 1023.0은 가수부(mantissa), 10^2는 지수부(exponent)라고 한다.(10은 기수[radix])
- 2진수 예) 1010 = 101.0 x 2^1 = 10.10 x 2^2 = 1.010 x 2^3

단정도
- 32bit = 4byte
- 부호(1bit) + 지수(8bit) + 가수(23bit)
배정도
- 64bit = 8byte
- 부호(1bit) + 지수(11bit) + 가수(52bit)

부호(sign), 지수(exponent), 가수(mantissa)
지수부를 넓힌다는 건 표현 범위를 넓힌다는 것
가수부를 넓힌다는 건 정밀도를 높힌다는 것

정규화

정수 부분을 0이 아닌 자연수로 만드는 것
ex) 5234의 정규화 : 5.234 x 10^3
정규화를 함으로써 맨 앞의 한자리는 mantissa에 포함시키지 않는다.

정규화 식 : 2진수로 바꿔서 나타냄

±1.mantissa x 2^(exp - bias)

- exp : 실제로 메모리에 저장되는 것
- bias : 2^(n-1) - 1
- float일 경우, bias = 2^(8 - 1) - 1 = 127
- double일 경우, bias = 2^(11 - 1) - 1 = 1023
- 계산된 exp의 값을 2진수로 바꿔서 메모리에 저장

digit(자리수) = 정밀도
- 10진수 1자리를 표현하기 위해 2진수 4자리가 필요하다.
- 계산기로 2진수 1111을 치면 10진수 = 15(적어도 10진수 한 자리수는 모두 표현 가능)
- 2진수 7자리 수는 10진수 2자리 수를 보장한다.(99까지 표현이 가능)
- 2진수 10자리 수는 10진수 3자리 수를 보장한다.
- 2진수 24자리 수는 10진수 7자리 수를 보장한다.
- 2진수 53자리 수는 10진수 15자리 수를 보장한다.
- double 형에서 정밀도는 소수점 아래 15자리를 보장하는 것이 아니다.
- double 형에서 정밀도는 10진수 15자리를 이야기하는 것이다.

epsilon의 정의

1.0(2) x 2^0과 다음으로 표현할 수 있는 수 사이의 차이

double 형이 더 정밀하는 것을 알 수 있다.

# float 형에서의 epsilon = 2^-23
f_ep = 2**(-23)
print(f_ep)
>> 1.1920928955078125e-07

# double 형에서의 epsilon = 2^-52
d_ep = 2**(-52)
print(d_ep)
>> 2.220446049250313e-16

Comparison

아래와 같이 a와 b 모두 0.3으로 참이 나와야 하는데 거짓이 나온다.
1
2
3
4
a = 0.3
b = 0.1*3
a == b
>> False
이 문제를 해결하기 위한 비교 방법들이다.

절대 비교 기법(Absolute comparison)

두 수의 차를 절대값으로 만든다.
‘1.0e-10’과 같이 기준을 잡아서 비교하는 것이다.
하지만 ‘1.0e-10’이라는 기준이 너무 막연하고 모호하다.

기준으로 잡는 수를 변경할 수 있도록 매개변수로 잡는 방법도 있다.

from math import fabs  # math 모듈에서 fabs라는 절대값 함수를 가져옴

def is_equal_abs(a,b):
    return fabs(a-b) <= 1.0e-10

if is_equal_abs(a,b):
    print('이 정도 차이면 같다.')
else:
    print('같은 수가 아니다.')
>> 이 정도 차이면 같다.

상대 비교 기법(Relative comparison)

sys 모듈에서 epsilon 값을 적용한다.
절대값을 취한 a와 b 사이 중 큰 값을 이용한다.

매개변수를 추가하여 정밀도 범위 조정을 가능하게 한다.

from math import fabs
import sys

def is_equal_rel(a,b, w=0):
    """
    is_equal(a, b, w=0) -> bool
    w는 가중치입니다.
    w를 0부터 늘려가며 상대 오차 범위를 조정해주세요.
    """
    ep = sys.float_info.epsilon  # sys 모듈에서 epsilon 값을 적용
    diff = fabs(a-b)

    return diff <= max(fabs(a), fabs(b))*ep*(2**w)

a = 0.3
b = 0.3
if is_equal_rel(a,b):
    print('같다.')
else:
    print('다르다.')
>> 같다.

정밀도 범위 조정

s = 0.0
a = 0.01
t = 1.0

for _ in range(100):
    s+=a

# 정밀도 범위를 조정하지 않은 경우
if is_equal_rel(s, t):
    print('같다.')
else:
    print('다르다.')
>> 다르다.

# 정밀도를 조정한 경우
if is_equal_rel(s, t, 2):
    print('같다.')           
else:
    print('다르다.')
>> 같다.

알고리즘 성능을 가늠하는 기준 : 시간

절대 시간 : 컴퓨터 성능에 의해 기준 자체가 모호하므로 기준으로 삼기 어려움
상대 시간 : 데이터의 개수(n)에 따른 연산 횟수를 가지고 비교
- 알고리즘 성능을 상대 시간으로 결정하기로 함
- 연산 횟수는 알고리즘 안에서 헤비하게 쓰이는 연산을 기준으로 삼음
- 보통 비교 연산 부분을 기준으로 삼음(if문, for문…등등)

알고리즘의 성능 3가지
- 최선의 경우 : 알고리즘 성능에서는 잘 사용하지 않는다.
- 평균의 경우 : quick sort Algorithm에서 쓰인다.
- 최악의 경우 : 알고리즘 성능에서 많이 쓰인다.
O(n)
- 오
- upper bound
- 최악의 경우에 이 정도까지 나타낸다는 의미
Ω(n)
- 오메가
- under bound
- 최선의 경우에 이 정도까지 나타낸다는 의미
θ(n)
- 세타
- upper bound + under bound

T(n) = 3n^2 + 5n - 1

- 위 식에서 그래프의 미분율이 중요함
- 그래프가 어디서 시작하는지는 중요하지 않음
- 그래프의 생김새를 결정하는 맨 앞자리(3n^2)로 빅오(O) 판단

빅오(O)의 가장 좋은 5가지(속도 순)
1. O(상수)
  - 상수 시간(constant)
  - 연산 횟수가 늘어나도 상수 시간이 정해져 있음
    - 배열의 인덱싱(array indexing) = search()
    - linked list의 insert(), delete()
2. O(log(n))
  - 로그 시간
  - 데이터 양이 많아져도 시간이 조금씩 늘어남
  - 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
    - binary seach
    - BST insert(), search(), delete() 계열 모두
3. O(n)
  - 선형 시간
  - 데이터 양에 따라 시간이 정비례함
    - array의 insert(), delete()
    - linked list의 search()
4. O((n)log(n))
  - 데이터 양이 n배 많아진다면, 실행 시간은 n배보다 조금 더 많아짐(정비례 X)
  - 두 수를 직접 비교해서 정렬하는 알고리즘은 O((n)log(n))보다 좋아질 수 없다는 것이 증명되었음
    - quick sort, merge sort, heap sort
5. O(n^2)
  - 데이터 양에 따라 걸리는 시간은 제곱에 비례함
  - 효율이 좋지 않음
  - 그래프의 모양이 4번보다 가파름
    - 2중 for문
    - bubble sort, insertion sort, selection sort
- 4번과 5번의 성능 차이는 엄청 크다.(비교할 수 있는 성능이 아님)
빅오(O)를 무조건 믿으면 안되는 이유
- 만약 O(n)의 알고리즘을 쓴다고 할 때, 성능이 좋지 않은 경우가 있다.
- 이럴 경우, CPU가 RAM에서 받아오는지 Hard Disk에서 받아오는지 알아야 한다.
- CPU가 RAM에서는 20-100cycle이지만, Hard Disk에서는 500,000-5,000,000cycle이다.
- 따라서 벤치마킹을 살펴보는 것이 중요하다.

지눅쿠의 개발 블로그

StudyPython and CE

CPU 기초

Computer Engineering

실수(real number)

Comparison

알고리즘 성능을 가늠하는 기준 : 시간