파이프라이닝과 캐시 메모리
파이프라인 해저드와 캐시 지역성·매핑·쓰기 정책·평균 접근시간을 학습한다.
1. 파이프라이닝
하나의 명령어 처리를 여러 단계로 나누고 서로 다른 명령어의 단계를 겹쳐 수행해 처리량을 높인다. 전형적인 5단계는 다음과 같다.
IF(인출) → ID(해독) → EX(실행) → MEM(메모리) → WB(결과 기록)
파이프라인은 한 명령어의 지연시간을 반드시 줄이는 기술이라기보다 일정 시간이 지난 뒤 완료되는 명령어 수, 즉 처리량을 높이는 기술이다.
단계 수가 k이고 각 단계 시간이 같으며 명령어가 n개라면 이상적인 총 시간은 대략 (k+n-1)×단계시간이다. 실제로는 해저드와 단계 불균형 때문에 이상적 속도향상보다 낮다.
2. 파이프라인 해저드
- 구조적 해저드: 같은 하드웨어 자원을 동시에 요구
- 데이터 해저드: 이전 명령어 결과가 아직 준비되지 않음
- 제어 해저드: 분기 결과를 몰라 다음 명령어가 확정되지 않음
대응 방법은 자원 분리, stall, forwarding, 명령어 재배치, 분기예측, speculative execution 등이 있다.
대표 데이터 의존성은 RAW(Read After Write)이다. 단순 순차 파이프라인에서 가장 자주 문제되는 실제 의존성이다.
3. 메모리 계층과 지역성
레지스터 → 캐시 → 주기억장치 → 보조기억장치 순으로 아래로 갈수록 일반적으로 용량은 커지고 가격은 낮아지며 접근은 느려진다.
- 시간 지역성: 최근 사용한 데이터를 다시 사용할 가능성
- 공간 지역성: 사용한 주소 주변을 곧 사용할 가능성
캐시는 메모리를 블록 또는 캐시 라인 단위로 가져온다.
4. 캐시 매핑
직접 매핑
각 메모리 블록이 하나의 캐시 라인에만 배치된다. 단순하고 빠르지만 같은 라인으로 매핑되는 블록 사이 충돌 미스가 많을 수 있다.
완전 연관 매핑
어떤 블록도 어느 라인에나 배치할 수 있다. 충돌은 줄지만 모든 태그를 비교해야 해 하드웨어 비용이 크다.
집합 연관 매핑
캐시를 여러 집합으로 나누고 블록은 하나의 집합 안 여러 way 중 하나에 배치된다. 직접과 완전 연관 방식의 절충이다.
주소는 일반적으로 tag | index(set) | block offset으로 나눈다.
5. 적중과 평균 접근시간
- hit: 원하는 데이터가 캐시에 있음
- miss: 주기억장치 등 하위 계층에서 가져와야 함
AMAT = hit time + miss rate × miss penalty
hit time이 2ns, miss rate가 5%, miss penalty가 80ns라면 AMAT는 2 + 0.05×80 = 6ns이다.
6. 교체·쓰기 정책
- 교체: LRU, FIFO, Random 등
- write-through: 캐시와 메모리에 즉시 기록, 단순하지만 쓰기 트래픽 증가
- write-back: 캐시에 먼저 기록하고 교체 시 메모리에 반영, 빠르지만 dirty bit와 일관성 관리 필요
- write-allocate: 쓰기 미스 시 블록을 캐시에 가져옴
- no-write-allocate: 쓰기 미스 시 캐시 적재 없이 하위 계층에 기록
7. 파이프라인 시간표와 속도향상
5단계 파이프라인, 단계 시간 1ns, 명령 4개라면 이상적인 시간표는 다음과 같다.
cycle 1 2 3 4 5 6 7 8
I1 IF ID EX ME WB
I2 IF ID EX ME WB
I3 IF ID EX ME WB
I4 IF ID EX ME WB
비파이프라인에서 명령당 5ns라면 총 20ns, 파이프라인은 (5+4-1)×1=8ns, 이 경우 속도향상은 2.5배다. 명령 수가 매우 커질 때 이상적 처리량은 사이클당 약 1명령이고 속도향상은 단계 수에 가까워진다.
8. 데이터 해저드와 forwarding
I1: ADD R1, R2, R3
I2: SUB R4, R1, R5 # RAW on R1
I1의 ALU 결과를 레지스터 기록까지 기다리지 않고 I2의 EX 입력으로 전달하면 forwarding으로 stall을 줄일 수 있다. 그러나 다음과 같은 load-use는 데이터가 MEM 단계 뒤에 준비되어 전형적인 5단계 설계에서 한 사이클 stall이 필요할 수 있다.
I1: LOAD R1, 0(R2)
I2: ADD R3, R1, R4
WAR·WAW는 순차 in-order 단일 발행 파이프라인에서는 보통 나타나지 않지만 비순차 실행에서는 레지스터 이름 의존성으로 발생할 수 있으며 register renaming으로 제거한다.
9. 분기 패널티와 CPI
기본 CPI가 1, 명령의 20%가 분기, 예측 실패율 10%, 실패 패널티 3사이클이면 다음과 같다.
추가 CPI = 0.20 × 0.10 × 3 = 0.06
평균 CPI = 1.06
예측 정확도뿐 아니라 분기 비율, 해결 시점, 실패 패널티가 전체 성능을 결정한다.
10. 캐시 주소 비트 분해 예제
32비트 주소, 32KiB 캐시, 블록 64B, 4-way 집합연관 캐시라 하자.
전체 라인 수 = 32KiB / 64B = 512
집합 수 = 512 / 4 = 128 = 2^7
offset = log2 64 = 6비트
index = log2 128 = 7비트
tag = 32 - 7 - 6 = 19비트
주소 0x00001234의 block offset은 하위 6비트, set index는 그 위 7비트로 구한다. byte-addressable인지, 캐시 용량에 데이터만 포함하는지 조건을 확인한다.
11. 캐시 미스의 3C 분류
- compulsory: 처음 접근해 발생
- capacity: 작업집합이 캐시 전체 용량보다 커 발생
- conflict: 매핑 제약 때문에 빈 다른 라인이 있어도 같은 집합에서 충돌
완전 연관 캐시는 같은 용량·블록 크기라면 conflict miss를 제거하지만 compulsory·capacity miss는 남는다. 연관도를 높이면 태그 비교와 hit time·전력 비용이 늘 수 있다.
12. 다단계 캐시 AMAT
L1 hit time 1ns, L1 miss rate 5%, L2 hit time 5ns, L2 local miss rate 20%, 메모리 penalty 80ns라면 다음처럼 계산할 수 있다.
L2 miss service = 5 + 0.20×80 = 21ns
AMAT = 1 + 0.05×21 = 2.05ns
문제에 따라 L2 접근시간과 메모리 penalty가 포함·제외 관계인지 표현이 다르므로 계층별 조건부 확률(local miss rate)을 구분한다.
13. 쓰기 정책 조합
write-through는 보통 write buffer로 CPU 대기를 줄인다. write-back은 dirty line 교체 시 하위 계층 쓰기가 필요하다. 흔한 조합은 write-back + write-allocate, write-through + no-write-allocate이지만 설계에 따라 다를 수 있다.
멀티코어에서는 각 코어 캐시가 같은 메모리 블록의 사본을 가질 수 있어 캐시 일관성 문제가 생긴다. snooping·directory 기반 프로토콜은 쓰기 시 다른 사본을 무효화하거나 갱신한다.
14. CPI와 CPU 시간 통합 문제
명령 수 10억, 기본 CPI 1, load 비율 30%, load 중 캐시 미스율 4%, 미스 패널티 50사이클, 클록 2GHz라면:
memory stall CPI = 0.30×0.04×50 = 0.6
total CPI = 1.6
CPU time = 10^9×1.6/(2×10^9) = 0.8초
미스율이 작은 숫자라도 패널티와 메모리 명령 비율을 곱하면 전체 성능 영향이 커질 수 있다.
최종 확인 문제
- 6단계 파이프라인에서 단계 시간 2ns, 명령 10개, stall이 총 3사이클일 때 총 시간을 구하시오.
- 기본 CPI 1, 분기 비율 25%, 예측 실패율 8%, 실패 패널티 4사이클일 때 평균 CPI를 구하시오.
- 64비트 주소, 256KiB 캐시, 64B 블록, 8-way 집합연관일 때 offset·index·tag 비트 수를 구하시오.
- L1 hit 1ns, L1 miss rate 10%, L2 hit 8ns, L2 local miss rate 25%, 메모리 penalty 100ns일 때 AMAT를 구하시오.
- 완전 연관 캐시로 바꿔도 사라지지 않는 3C 미스 두 종류를 쓰시오.