3.컴퓨터 산술과 논리 연산 & 4.제어 유니트 & 5.기억장치

3. 컴퓨터 산술과 논리 연산

3.1 ALU의 구성요소

CPU : ALU, CU, R-S

산술 연산장치 : 산술 연산들(사칙연산)을 수행
논리 연산장치 : 논리 연산들(AND, OR, XOR, NOT등)을 수행
시프트 레지스터 : 비트들을 좌측 혹은 우측으로 이동시키는 기능을 가진 레지스터
보수기 : 2진 데이터를 2의 보수로 변환(음수<->양수 : 보수화)
상태 레지스터 : 연산 결과의 상태를 나타내는 플래그

3.2 정수의 표현

2진수 체계 : 0, 1, 부호 및 소수점으로 수를 표현 ex) -13.625 = -1101.101
부호 없는 정수 표현(양수만 나타냄)

소수와 음수의 표현
소수 표현

2^n, n자리로 소수를 표현

음수 표현

부호화-크기 표현 : 크기앞에 0(양수), 1(음수) 부호로 표현, 실제로 사용x
1의 보수 표현 : 모든 비트를 반전 0->1, 1->0
2의 보수 표현 : 1의 보수 + 1
8bit음양수 표현 1의 보수: -(2^7-1) ~ + (2^7 - 1), 2의보수 : 2^7 ~ + (2^7 -1), 양수만 0~255

비트확장 : 확장된 만큼 부호비트 복사

3.3 논리 연산

CPU의 기능

3.4 시프트 연산

기본적인 논리 연산들

NOT, AND, OR, XOR
N-bit논리 연산은 각 비트별로 연산모듈을 병렬연결하여 각각출력

AND 연산 / OR 연산 : 이미지를 잘라내거나 붙여 넣을 때 많이 쓰임
XOR 연산 / NOT 연산 : 데이터를 반전시킬 때 쓰임

선택적-세트(1로만드는) 연산 / 선택적 보수 연산

선택적-세트 연산 : 10010010 OR 00001111 : 앞 4비트는 그대로 뒤 4개는 1
선택적-보수 연산 : 10010010 XOR 00001111 : 앞 4비트는 그대로 뒤 4비트만 반전
-이러한 특징으로 이미지를 부분적 수정가능

마스크 연산 : 11010101 AND 00001111 : 앞 4비트는 0 뒤 4비트는 그대로 (선택적 제거)
삽입 연산 : 10010101 AND로 앞 4비트 지움, OR로 지운부분 원하는 값 삽입

비교 연산 : 결과가 모두 0이면 같은값(Z flag register값이 1로 세트)

시프트 연산 : c언어 <<, >>(논리, 산술)
논리적 시프트 : 왼쪽 혹은 오른쪽으로 비트를 한 칸씩 이동(빈자리는 0으로 채워짐)
시프트 레지스터(D flip-flop으로 만듬) : AND, AND, OR, D-flip-flop X4로 구성

순환 시프트 : 끝값이 첫값으로 들어감(역순가능), 
직렬 데이터 전송할 때 사용(내부(순환)->외부(시프트), CLK = 비트길이만큼, 시계열로 바꿔줘야 하기 때문에), 병렬(내부)

산술적 시프트 : 계산 <<, >>, 부호는 그대로, 수의 크기를 나타내는 비트만 시프트
1 1 1 0 (-2) : 초기 상태 (2의 보수)
1 1 0 0 (-4) : 산술적 좌측-시프트 결과
1 1 1 0 (-2) : 산술적 우측-시프트 결과
1 1 1 1 (-1) : 산술적 우측-시프트 결과
-위의 논리로 *2, %2연산 간단한 코딩가능

C(캐리) 플래그 : 계산했을 때 계산결과가 들어가는 플래그(큰값 연산)

3.5 정수의 산술 연산

실제 모두 2의 보수를 이용한 연산

A <- A' + 1 : 보수화(2의 보수 변환)
사칙연산, 1증가, 1감소

3.5.1 덧셈

2의 보수를 이용한 덧셈

-2^(n-1) ~ +(2(n-1)-1)
full-adder를 비트수만큼 병렬 연결하여 병렬 가산기 구성 
4비트 병렬가산기: V = C3 XOR C4(오버플로우), 

3.5.2 뺄셈 (덧셈으로 구현)

A-B = A+(-B)

덧셈회로에서 B->(보수기(ALU) 통과)->(-B)로 계산
뺄셈 오버플로우 = C3 XOR C4, 0110+0100=1010=-6, 6-(-4) = 10

3.6 부동소수점 수의 표현

부동소수점 표현(floating-point)
소수점의 위치를 이동시킬 수 있는 수 표현 방법->수 표현 범위 확대

N = (-1)^S M X B^E
S: 부호, M:가수, B:기수, E:지순
정규화된 표현(모든 수를 한 가지로 통일)
+- 0.1bbb..b X 2^E

ex) 0.1101 X 2^5 = S 0 E 00000101 M 11010000000000000000

2의 보수를 쓰지 않고 지수를 바이어스된 수로 표현

-13.625
13.625 = 1101.101 = 0.1101101 X 2^4
지수(E) = 00000100 + 10000000 = 10000100 (바이어스 128을 더한다)
S 1 E 10000100 M (0.1)101101000000000000 실제로 (24자리)
음/양수 언더/오버플로우 (0/무한대)

IEEE 754 표준 부동소수점

N = (-1)^S 2^(E-127) (1.M)     0.1 대신 1.으로씀
지수 필드 : 바이어스 127 사용

64비트일때 E = 11이므로 바이어스 1023사용

지수 E = -00000010 + 01111111 = 01111101
E = 255고 M != 0 이면 NaN / M = 0이면 오버플로우
E = 0이고 M != 0 이면 1에 가까운 숫자 / M = 0이면 언더플로우

3.7 부동소수점 산술 연산

덧셈 뺄셈

지수가 큰값에 맞춰 지수를 조정하고 정규화(1.M)
파이프라인 만큼 속도 향상(배열들의 덧셈에서 유용)

곱셈 나눗셈

곱셈 : 가수는 곱하고 지수는 더하고
나눗셈 : 가수는 나누고 지수는 뺀다.

오버/언더플로우

지수는 어쩔 수 없음
가수 언더플로우 : 00000000001 반올림
가수 오버플로우 : 소수점 위치를 변경해서 정규화

4. 제어 유니트

4.1 제어 유니트의 기능

명령어 코드의 해독
명령어 실행에 필요한 제어 신호들의 발생
1.Hardwired control(변경불가)

2.소프트웨어로 control

마이크로명령어 : 명령어 사이클의 각 주기에서 실행되는 마이크로-연산들에 대응되는 비트들로
이루어진 단어로서, 제어 단어라고도 함
마이크로프로그램 : 마이크로명령어들의 집합
루틴 : CPU의 특정 기능을 수행하기 위한 마이크로명령어들의 그룹

4.2 제어 유니트의 구조

구성 요소들

명령어 해독기 : IR의 OPCODE를 해독하여 루틴의 시작주소를 결정
제어 주소 레지스터(CAR) : 제어 메모리 값 임시저장 -> MAR에 주소보낼 때 쓰임
제어 기억장치 : 마이크로명령어들로 이루어진 마이크로프로그램 저장(ROM-바뀌면 안됨)
제어 버퍼 레지스터(CBR) : 제어 기억장치로부터 읽혀진 명령어 임시저장 -> 해독기로 신호발생
서브루틴 레지스터(SBR) : 서브루틴 호출될 때 CAR 임시저장
순서제어 모듈 : 마이크로명령어의 실행 순서를 결정하는 회로들의 집합

CPU의 명령어 세트 설계 과정

1. 명령어들의 종류와 비트 패턴 정의
2. 명령어들의 실행에 필요한 하드웨어 설계
3. 각 명령어를 위한 실행 사이클 루틴 작성(마이크로프로그래밍)
4. 마이크로프로그램 코드들을 제어 기억장치(CPU)에 저장

명령어 해독

사상(mapping)을 이용한 해독 방법
-opcode를 제어 메모리속 시작주소와 mapping, ex) 0001 -> 1000100

4.3 마이크로 명령어의 형식

연산 필드 두 개(마이크로-연산 동시 수행가능) 3bit : None, MAR <- PC, M[MAR] <- MBR등

조건(CD)필드는 분기에 사용될 조건 플래그를 지정, (간접 사이클 또는 값에 따른 분기 조건등)

분기(BR)필드는 분기의 종류와 다음에 실행할 마이크로명령어의 주소를 결정하는 방법을 명시
-분기 동작을 지정, 분기/JUMP/CALL, RED(서브루틴 복귀 SBR->CAR), MAP 1XXXX001 (opcode)

주소 필드(ADF)의 내용은 분기가 발생하는 경우에 목적지 마이크로 명령어의 주소로 사용
-JUMP/CALL일때 먼저 불렷다가 다음 CAR+1실행

4.4 마이크로 프로그래밍

4.4.1 인출 사이클 루틴의 마이크로명령어 루틴

FETCH(시작주소) PCTAR       : MAR <- PC
               READ, INCPC : BR <- M[MAR], PC = PC + 1
               BRTIR       : IR <- MBR, 해당 실행 사이클 루틴으로 분기 

4.4.2 간접 사이클 루틴

INDRT : IRTAR로 PC만 IR(addr)로만 바뀜

4.4.3 실행 사이클 루틴

사상(mapping)을 이용하여 opcode의 실행 사이클 루틴의 시작 주소 결정
시작주소 : 1(opcode(4bit))00
NOP, LOAD, STORE, ADD, SUB, JUMP등
제어 유닛에 실행사이클 ADD와 같은 명령어 만들어 넣는것

4.5 마이크로프로그램의 순서 제어

순서제어 : 다음에 실행항 마이크로명령어 주소 결정

CAR 초기값 = 0, 인출 사이클 루틴의 첫 주소
MUX1: 다음에 실행할 주소 선택
00 - CAR 1씩증가
01 - ADF
10 - SBR(서브루틴)
11 - 실행루틴(ADD등등)

MUX2: 조건 플래그를 선택하여 주소선택 회로로 전송
00 - 무조건 점프
01 - INDRT
10 - 음수일 때 어디로갈지
11 - AC내용이 0이면 Z = 0, 어디로 점프하라

주소 선택 방법

BR = 00(JUMP), 01(CALL)일 때
- C = 0, 다음 위치의 마이크로명령어 선택, C = 1, ADF로 점프 혹은 CALL
BR = 10(RET), CAR <- SBR 적재 복귀, BR = 11 mapping결과를 CAR에 적재

제어 신호의 생성

제어 기억장치로부터 인출된 마이크로명령어 내 연산 필드의 비트들이
제어 유니트의 외부로 출력되어, 각각 제어 신호로 사용됨

수직적 마이크로프로그래밍

연산 필드에 코드화된 비트로 만듬 3bit -> 8가지, 3*8디코더로 만들어 제어 신호들 확장
장점 : 제어 기억장치 용량 최소화
단점 : 해독에 딜레이 발생(추가 하드웨어 필요)

수평적 마이크로프로그래밍

디코더 없이 비트와 제어 신호를 1:1로 대응시키는 방식
장점 : 지연시간이 없음
단점 : 제어 기억장치 용량이 증가

5. 기억장치

5.1 기억장치 분류와 특성

기억장치 엑세스

CPU가 어떤 정보를 기억장치에 쓰거나 기억장치로부터 읽는 동작

1.순차적 엑세스 : 저장된 정보를 처음부터 순서대로 엑세스하는 방식 ex)자기 테이프
2.직접 엑세스 : 원하는 위치로 이동하여, 순차적 검색을 통해 최종 위치에 도달하는 방식
-FAT(실제 저장X, 기본적내용저장(테이블 이동)) ex)디스크, CD-ROM
-NTFS(윈도우), UFS(유닉스)
3.임의 엑세스 : 주소에 의해 직접 기억 장소를 찾아 엑세스(디코더 이용) ex) RAM, ROM
4.연관 엑세스 : 특정 비트를 비교하여 일치하는 내용을 엑세스 ex) 캐시

기억장치 설계 / 전송단위 / 주소지정 단위

설계요소 : 용량, 엑세스 속도, 가격
전송 단위 : CPU가 한 번의 기억장치 엑세스에 처리 가능한 비트 수 ((주)word, (보조)block)
주소지정 단위 : 보통 바이트 단위 혹은 word 단위

엑세스 속도와 관련된 파라미터

엑세스 시간 : 엑세스 시작부터 완료되는 순간까지의 시간  (한번에)
기억장치 사이클 시간 : 엑세스 시간 + 데이터 복원 시간
데이터 전송률 : (1/엑세스 시간) * (한 번에 읽혀지는 비트 수) bps

5.2 계층적 기억장치시스템

5.2.1 필요성 및 효과

계층 : 레지스터->캐시->메모리->usb->하드->테이프

필요성 : 속도, 용량, 가격

엑세스 속도 / 비트당 가격 비례
용량 / 비트당 가격 반비례
용량 / 엑세스 속도 반비례

효과 : 계층별로 비율조정하여 기억장치 시스템의 가성비 향상

지역성의 원리

기억장치 엑세스 시간이 단축됨
캐시에서 다시

기억장치 계층

내부 기억장치 : CPU가 직접 엑세스할 수 있는 기억장치, ex) CPU 레지스터, 캐시, RAM
외부 기억장치 : 직접 엑세스할 수 없고 제어기로할 수 있는 기억장치, ex) 디스크,CD-ROM

캐시 기억장치 / 디스크 캐시

캐시 기억장치 : CPU - RAM의 엑세스 속도 향상(CPU가 덜기다리게 됨)
디스크 캐시 : DISK - RAM의 엑세스 속도 차이를 줄이기 위하여

5.3 반도체 기억 장치

5.3.1 RAM : 읽기 / 쓰기

메모리의 단위 : bit

DRAM(Dynamic) : 주기억장치, capacity 전하축적 이용하기 떄문에 재충전 해야함
-집적도 높고 비교적 가격이 저렴함
SRAM(Static) : 캐시메모리 (flip-flop 안정회로)
-집적도 떨어지지만 빠르고 가격이 비쌈

64bit RAM 내부조직 : (3X8디코더)8(주소bit)X8(데이터bit)
                  : 16x4 (4x16디코더)
                  : 64x1 (3x8디코더 2개필요)
16M X 4 조직
4096x4096x4
주소 비트 12/12 필요(행열 주소 사용하기 떄문에 실제 주소선 12개사용)

5.3.2 ROM 읽기

영구 저장이 가능한 반도체 기억장치
PC의 BIOS프로그램, 서브루틴(기본)에 사용

PROM : 한번 쓰는 것 가능한 ROM
EPROM : 자외선으로 내용을 지울 수 있는 PROM, 여러번 쓰기가능
EEPROM : 전기적으로 지울 수 있는 EPROM, 데이터 갱신 횟수 제한
플레시 메모리 : 블록(64페이지) 단위로 삭제, 페이지 단위로 읽기/쓰기가 가능한 EEPROM
EEPROM보다 삭제시간빠르고(2ms), 직접 밀도도 더높다

메모리의 구성 예

1K(10bit 주소버스필요) x 8bit : 주소갯수 x 주소당 데이터수 <-> 데이터 버스(8bit)
CS(칩선택신호) 1, RD 1, WR(0) : 읽기 동작
4K x 4bit

5.4 기억장치 모듈의 설계

워드길이 확장

각 메모리 칩의 데이터의 길이가 원하는 데이터의 길이보다 작을 때
원하는 길이를 맞추어 설계 (칩 병렬연결(동시))
16진수(2진수 4bits)

워드용량 확장

메모리 칩의 주소공간이 부족할 떄 여러 개를 직렬(따로)로 연결하여 전체 주소공간을 확장
2^4 x 4 : 2개 일 때 2^5x4 에서 남는 한 bit는 칩 선택용(CS, CS')

워드길이 및 워드용량 확장

워드의 길이 및 워드의 용량이 모두 모자랄 떄 둘 다 확장하는 방법

RAM과 ROM을 차례로 연결

전체 주소 공간에서 둘을 모두 연결하여 사용할 때
ex) 8bit 마이크로컴퓨터 기억장치
256*4 : 1KByte RAM(0부터), 10bit : 1KByte ROMS(800H(1000)부터)

5.5 캐시 기억장치 SRAM

사용 목적 : CPU와 주기억장치 속도 차이 개선
가격 및 제한된 공간 떄문에 용량이 적다
용어

캐시 적중(cache hit) : CPU가 원하는 데이터가 (레지스터에 없을 때)캐시에 있는 상태
캐시 미스(cache miss): CPU가 원하는 데이터가 캐시에 없는 상태 -> RAM으로감
적중률(hit ratio) : H = 캐시 적중 횟수 / 전체 기억장치 엑세스 횟수
캐시의 미스율 : 1 - H
평균 기억장치 엑세스 시간(Ta) : Ta = H X Tc + (1 - H) X Tm

지역성에 따라 성능이 좌우된다

시간적 지역성 : 다시 엑세스 될 가능성 높다
공간적 지역성 : 메모리에 인접하여 저장되어 연속적으로 엑세스 될 가능성이 높다
순차적 지역성 : 분기가 발생하지 않는 한, 명령어들이 순서대로 인출된다

캐시 설계의 공통적 목표

1.캐시 적중률 극대화
2.캐시 엑세스 시간의 최소화
3.캐시 미스에 따른 지연 시간의 최소화
4.주기억장치와 캐시간의 데이터 일관성 유지(슈퍼컴퓨터) 및 그에 따른 오버헤드 최소화
일관성 : 캐시에서 바뀐걸 RAM에 갱신

인출방식

요구인출 : CPU가 필요할 때 CM <- MM
선인출 : 미리 연속되는 내용 인출(블록(라인)단위, 지역성 높은 경우 효과적)
태그 : 어떤 블록이 인출됬는지 표시

캐시 사상 방식
직접사상

여러개의 블록이 한개의 라인을 공유함, 한시점에 한라인당 한블록(tag로 블록 구분)
장점 : 하드웨어, 저렴
단점 : 히트율이 줄어듬

완전-연관 사상
심플하지만 구현불가

주기억장치 블록이 캐시의 어떤 라인으로든 적재 가능
line X, 모든 tag비교 해봐야함(line갯수 많아지면 안좋음)
장점 : 지역성에 매우 좋고, 라인 선택이 자유로움
단점 : 복잡한 하드웨어 필요, 시간증가

세트-연관 사상
실제 시스템에서 사용하는 방식, 직접 + 완전

tag / set / word 필드
세트연관 사상은 적중률을 어느 정도 향상시킬 수 있다.

동작 원리

한세트속에 두개 이상의 라인이 있음(공유) : tag를 세트당 라인수 만큼 비교

주기억장치 2^24바이트, 블록(4바이트) 2^22개
캐시 2^16바이트 , 라인(4바이트) 2^14개 / 2(2way) : set 13bit

태그 9 세트 13 단어 2

캐시의 교체 알고리즘
세트-연관 사상에 해당

주기억장치로부터 새로운 블록이 캐시로 적재될 때
만약 세트 내 모든 라인이 채워져 있다면, 어떤 블록을 교체할지
정하는 알고리즘

최소 최근 사용(LRU) 알고리즘 : 가장 오래 사용되지 않은 블록 교체
FIFO 알고리즘 : 가장 오래된 블록을 교체
최소 사용 빈도(LFU) 알고리즘 : 참조 횟수가 가장 적은 블록 교체

캐시의 쓰기 정책

캐시 블록이 변경되었을 때 그 내용을 주기억장치에 갱신하는 시기와 방법
1.Write through : 모든 쓰기 동작들이 캐시, 주기억장치에 동시 수행
장점 : 내용이 둘 다 항상 같다
단점 : 쓰기 시간이 길어진다, 연산하는 동안 가져가면 공유 문제 발생

2.Write back : 캐시에서 데이터가 변경되어도 주기억장치에서는 갱신X(블록교체할 때 생신)
장점 : 쓰기 동작 횟수 감소, 쓰기 시간 짧아짐
단점 : 내용이 서로 다를 수 있다.(일관성 유지X : 다중프로세서의 병렬처리에서 공유 문제)

다중캐시 속도 L1 > L2 > L3 > MM
*온-칩 캐시 : CPU칩내 캐시(엑세스 시간 단축 L1)

계층적캐시 : L2는 L1의 슈퍼-세트, L2에는 L1의 모든 내용이 존재

분리캐시 : L1(명령어, 데이터) = 파이프라인(명령어 인출 유니트 / 실행 유니트) 충돌 방지용

Question

1.a, b 두 변수의 값을 swap할 때 변수를 하나 더 선언하여 swap하는 것과 bit연산으로 swap하는것에 대하여 레지스터 관점에서 설명해주세요

2.부동소수점연산에서 바이어스의 역할은?

3.Control Unit의 명령어해독에 대해

4.완전연관사상이 구현되기 힘든 이유는?

5.세트연관사상에서 연관도가 낮으면 적중률이 낮은 이유는?

6.다중프로세서 병렬처리에서 캐시와 관련하여 메모리 공유 문제가 발생하는 경우는?

7.캐시의 교체알고리즘 / (분리캐시, 계층적캐시) 어떤걸까요?