memory(cache)

메모리 계층에 사용되는 대표 기술은 다음과 같다.

종류	사용 위치	특징	접근 시간	가격($/GB)
SRAM	Cache	빠름, 비쌈	0.5~2.5ns	500~1000
DRAM	Main Memory	보통, 중간가격	50~70ns	10~20
Flash Memory	SSD/USB	비휘발성, 느림	5,000~50,000ns	0.75~1
Magnetic Disk	HDD	매우 느림, 매우 큼	5M~20M ns	0.05~0.1

지역성의 원리 (Principal of Locality)

1. Temporal Locality

최근 접근한 데이터는 곧 다시 접근될 가능성이 높다는 의미로 루프 내 명령어 등에서 쓰인다.

Loop: LDUR X0, [X1, 0]
      ADD X0, X0, X10
      STUR X0, [X1, 0]
      SUBI X1, X1, 4
      CBZ X1, Loop

위의 예시에서 루프 명령어들이 계속 반복되어 같은 메모리 위치를 재사용한다.

2. Spatial Locality

인접한 주소에 있는 데이터가 함께 접근될 가능성이 높다는 의미로 배열이나 구조체 등에서 쓰인다.

for (i=0; i<MAX; i++)
    sum += a[i];

3. 지역성 활용

Disk → DRAM : 최근 접근한 프로그램/파일을 메인메모리로 복사
(ex. 프로그램 실행 시 로드)
DRAM → Cache : 자주 쓰는 데이터는 캐시로 이동
(CPU가 빠르게 접근 가능)

→ Temporal & Spatial Locality 활용

Cache

1. 캐시(Cache)의 개념

캐시는 CPU와 메인 메모리(DRAM) 사이에 존재하는 작고 빠른 SRAM 기반 메모리다.
CPU가 메모리에 자주 접근하는 데이터를 미리 저장해 두어, 전체 접근 속도를 높인다.

캐시의 기본 원리

프로그램은 지역성(Locality) 을 보인다.
즉, 최근에 사용한 데이터나 그 주변 데이터가 다시 사용될 가능성이 높다.
캐시는 이러한 지역성을 이용해 “자주 사용하는 데이터”를 가까운 곳에 저장한다.
CPU는 요청한 데이터를 먼저 캐시에서 탐색한다.
- 데이터가 있으면 Cache Hit
- 없으면 Cache Miss → DRAM에서 데이터를 읽어와 캐시에 복사

💡 캐시의 목적: 평균 접근 속도(Average Memory Access Time, AMAT) 향상

2. 캐시의 동작 과정

CPU가 특정 메모리 주소를 요청
캐시에서 해당 주소의 데이터 블록을 탐색
- Hit → 캐시에서 즉시 데이터 제공
- Miss → 하위 계층(DRAM)에서 블록 단위로 읽어와 캐시에 저장
이후 같은 데이터 요청 시 빠르게 캐시에서 처리

⚡ 첫 번째 접근은 느리지만, 이후 반복 접근 시 빠른 속도로 해결된다.
즉, 처음 접근만 손해, 나중은 이득.

3. 캐시의 구조 — 블록 단위 저장

Block (Line)
캐시는 데이터를 “블록(block)” 단위로 저장한다.
보통 한 블록은 여러 바이트(예: 4~64B)로 구성된다.
메모리 주소는 바이트 단위로 관리되며,
캐시에 저장될 때는 여러 바이트를 하나의 블록으로 묶어 저장한다.


Cache Hit	요청한 데이터가 캐시에 있음 → 빠르게 접근
Cache Miss	캐시에 없음 → 하위 계층(DRAM)에서 블록 단위로 복사 후 저장

⚙️ 한 번 Miss가 발생하면 해당 블록의 인접 데이터까지 같이 올라오므로,
Spatial Locality(공간적 지역성) 을 활용한다.

4. 캐시 성능 지표

용어	정의	설명
Hit rate	캐시에서 데이터를 찾을 확률	높을수록 좋음
Miss rate	캐시에 없는 비율	1 - hit rate
Hit time	캐시 접근에 걸리는 시간	매우 짧음 (SRAM 접근 시간)
Miss penalty	캐시에 없을 때 DRAM에서 데이터를 불러오는 데 걸리는 시간	매우 김 (수십~수백 배)

평균 메모리 접근 시간(AMAT): HitTime+(MissRate×MissPenalty)

일반적으로 Hit time << Miss penalty,
즉 캐시의 존재로 평균 접근 시간이 극적으로 감소한다.

5. 캐시의 역할과 필요성

캐시는 CPU가 가장 자주 접근하는 데이터를 보관하는
가장 빠른 메모리 계층(level 1) 이다.
캐시가 없다면, CPU는 DRAM의 느린 속도에 맞춰 동작해야 하므로 전체 성능이 크게 저하된다.
따라서 캐시는 “최근에 접근된 메모리 블록”을 유지함으로써
프로그램 실행 속도를 실질적으로 향상시킨다.

6. 캐시 미스 시 동작 원리

캐시에 데이터가 없을 때(Cache Miss) 수행되는 과정

CPU가 데이터를 요청했는데 캐시에 없음
Placement Policy (배치 정책) 에 따라 새 블록을 어디에 저장할지 결정
만약 캐시가 가득 찼다면, Replacement Policy (교체 정책) 에 따라
기존 블록 중 하나를 내보내고 새 데이터를 저장
DRAM에서 “block 단위”로 데이터를 읽어와 캐시에 복사


Placement Policy	새 데이터 블록을 캐시 어디에 둘지 결정	Direct mapped, Set associative
Replacement Policy	캐시가 가득 찼을 때 어떤 블록을 내보낼지 결정	LRU, FIFO, Random 등

Direct-Mapped Cache & Cache Addressing

1. 캐시 주소 지정 기본 개념 (Memory vs. Cache)

캐시 주소 계산의 핵심:
메모리의 한 주소(=byte address)가
캐시의 어떤 블록(block) 에 저장될지를 결정해야 한다.

메모리 주소는 바이트 단위(byte address) 로 표현된다.
블록 크기가 4 bytes라면, 하나의 블록 안에는 4개의 byte address가 포함된다.
따라서 block address = byte address ÷ block size
→ 즉, byte address를 오른쪽으로 log₂(block size) 비트만큼 시프트하면 block address가 된다.

예시

메모리 주소가 5비트(0~31, 총 32 bytes)
블록 크기 = 4 bytes (= 2² bytes)
따라서 8개의 블록(= 32/4) 이 존재한다.

주소	계산	결과
byte address 00011 (3)	00011 ÷ 4	block address 000
byte address 11001 (25)	11001 ÷ 4	block address 110

즉,

Block address = Byte address >> 2 (shift right 2 bits)

2. 간단한 캐시 예제 구조 (Simple Cache Example)

위의 그림을 중심으로 설명을 해보자

메인 메모리의 크기가 32bytes 이므로 전체 주소 공간은 5비트로 표현할 수 있다.

Memory address = 5 bits  (0 ~ 31)

block의 size는 4bytes로 가정 했다.

따라서 블록 내부의 위치를 구분하기 위해서는 2bit가 필요하다

Block offset = 2 bits

또한 cache가 16bytes라고 가정하면 cache의 총 block 개수는 16bytes / 4bytes = 4개가 된다.

따라서 캐시 내부의 위치를 구분하기 위해서는 2bit가 필요하다.

index 비트 수 = log2(4) = 2 bits

이와 연관해서 실제 cache address를 구하는 공식은 다음과 같다.
Cache address = (Block address) mod (# of blocks in cache)

전체 주소가 5 bit 였고 offset 2 bit , Index 2 bit를 제외한 나머지 1비트는 Tag가 된다.

Memory address = [ Tag(1) | Index(2) | Offset(2) ]

또한 cache에 데이터가 들어가 있으면 Valid bit를 1로 초기화한다.

3. Direct - Mapped Cache

Cache의 방식에도 여러가지가 있는데 지금까지의 방식은 Direct Mapped 라는 방식이다.

메모리의 각 블록이 캐시의 오직 한 곳( index) 에만 저장될 수 있는 구조이다.

위의 그림을 보면 Block address 기준이므로 offset은 없고 Cache의 Block 개수가 8개 이므로 Index는 3bit이다.

매핑 규칙을 보면 같은 Index를 가진 블럭들은 모두 Cache의 같은 Index에만 매핑됨을 알 수 있다.

하지만 이렇게 매핑되면 충돌이 생길 수 있는데 이를 해결하기 위해 Cache는 Tag와 Valid bit를 함께 저장한다.

4. Address Subdivision

앞에서 말했듯이 메모리 주소는 block 내부를 구분할 수 있는 offset 그리고 cache 내부를 구분할 수 있는 index 그리고 tag로 이루어져있다.

프로그램이 어떤 특정 메모리 주소에 접근할 때, 그 주소 근처의 다른 주소들에도 접근할 확률이 높다는 특성을 공간 지역성(Spatial Locality)라고 했는데

만약 블록 크기가 증가한다면 메인메모리에서 데이터를 가져올 때, 주변의 많은 워드들을 함께 캐시로 가져온다. 후에 주변워드에 접근할 때 이미 캐시에 있을 확률이 높아지므로 전체 miss rate가 감소하게 된다.

하지만, 블록이 커질 수록 cache miss시 메인 메모리에서 캐시로 전송해야 할 데이터 양이 늘어나므로 Miss penalty 즉, 미스 발생 시 cpu가 기다려야 하는 시간이 증가한다.

또한, 캐시 용량이 고정된 상태에서 블록 크기가 너무 커지면 총 블록 개수가 줄어들어 같은 index를 놓고 경쟁할 확률이 높아져 conflict miss가 증가할 수 있다.

Handling Cache Hit / Misses

cache miss가 발생하면 메모리 접근을 위해 cpu pipeline이 stall 된다.

종류	발생 위치	이유	정지 위치	일어나는 일	결과
Instruction Cache Miss	IF 단계 (Instruction Fetch)	명령어를 가져오려 했는데 캐시에 없음	Fetch 멈춤 → IF 단계에서 stall 발생	메모리(또는 L2 캐시)에서 해당 명령어 블록 가져옴	명령어 캐시에 블록 복사 후 fetch 재시작
Data Cache Miss	MEM 단계 (Memory Access)	load/store 수행 중 캐시에 데이터 없음	실행 중지 → MEM 단계에서 stall 발생	메모리에서 데이터 블록 가져올 때까지 기다림	데이터 캐시에 복사 후 실행 재개
공통 (Pipeline Stall)	전체 파이프라인	위 두 경우 중 하나가 발생	파이프라인 전체가 잠시 멈춤	데이터 또는 명령어가 준비될 때까지 대기	캐시 적중 시점에 파이프라인 다시 진행

이러한 stlall을 줄이기 위한 방법으로 write policy가 사용된다.

write policy

cache에서 write policy란 cpu가 데이터를 캐시에 쓸 때 내용이 언제 메모리까지 반영되는지를 결정하는 방식이다.

1. write through

write through 방식은 데이터를 캐시에 저장함과 동시에 메인 메모리에도 저장하는 방식으로 항상 캐시와 메인 메모리 내용이 동일하게 유지된다.

일관성 유지가 용이하다는 장점이 있지만 매번 메모리에 접근해야 하므로 속도가 느려진다.

2. write buffer

write through의 단점을 완화하기 위해 등장한 방식으로 write buffer를 따로 둬서 cpu는 캐시에만 데이터를 저장하고 메모리에 저장하는 작업은 buffer가 대신 처리하도록 한다.

cpu와 메모리의 동작 분리로 성능이 향상 되지만 write buffer가 가득차면 cpu는 다시 stall 되고 write buffer에 있는 데이터가 아직 메모리에 반영되지 않았다면 일관성 문제가 발생한다.

3. write back

cpu는 cache 만 갱신하고 메인 메모리는 cache block이 교체될 때만 저장하는 방식이다.

dirty bit를 사용하여 데이터가 존재하면 1로 초기화하고 나중에 block 교체시 dirty bit가 1이면 메인메모리에 저장

매번 메모리에 접근하지 않으므로 속도가 빠르지만 여전히 데이터 일관성 유지가 어렵다.

Improving Cache Performance

1. 캐시 성능 측정의 핵심

CPU 시간을 구성하는 요소는 다음 두 가지다.

CPU execution cycles (cache hit 포함)
Memory stall cycles (대부분 cache miss 때문에 발생)

메모리 stall은 이렇게 계산된다:

Memory stall cycles = Memory accesses × Miss rate × Miss penalty

캐시 미스가 1회 날 때마다 miss penalty(수십~수백 cycles)가 추가되므로
CPU가 아무리 빨라져도 캐시 미스가 많으면 결국 전체 성능은 매우 느려진다.

2. Cache 성능 예시 (왜 캐시가 중요한지 보여주는 사례)

조건:

I-cache miss rate = 2%
D-cache miss rate = 4%
D-load/store 비율 = 36%
Miss penalty = 100 cycles
Base CPI = 2

계산하면:

I-cache stall = 2 cycles
D-cache stall = 1.44 cycles
총 Stall = 3.44 cycles

최종 CPI:

Actual CPI = 2 + 3.44 = 5.44

즉, 캐시 미스가 없다면 CPI=2인데, 캐시 미스 때문에 성능이 2.72배나 느려진다.
→ 캐시 구조가 엄청나게 중요하다는 의미.

3. AMAT(평균 메모리 접근 시간) — 가장 중요한 공식

AMAT = Hit time + (Miss rate × Miss penalty)

예:

hit time = 1 cycle
miss penalty = 20 cycles
miss rate = 5%

→ AMAT = 1 + 0.05×20 = 2 cycles

평균 2클럭이 들어간다는 뜻이다.

CPU 속도를 올리면 hit time은 그대로인데 miss penalty가 상대적으로 훨씬 커지므로
CPU가 빨라질수록 캐시의 가치가 폭발적으로 커진다.

4. Base CPI가 낮아질수록 Memory stall의 비중은 더 심각해짐

예를 들어 Base CPI가 2 → 1로 줄면:

Stall은 그대로 3.44
전체 CPI는 5.44 → 4.44로 줄지만
stall 비중은 63% → 77%로 더 커짐

즉,
CPU만 빨라져서는 안 되고, 캐시가 더 중요해진다.

5. Direct-Mapped Cache의 한계

Direct-mapped는 블록이 딱 1개의 index로만 들어간다.

예:

block 12 → 12 mod 8 = index 4

하지만 문제는:

캐시가 아직 비어 있음에도
두 블록이 같은 index로 매핑되면 무조건 충돌(conflict miss) 발생

이게 direct-mapped의 최대 단점이다.
그래서 더 flexible한 구조가 필요하게 됨 → Associativity

6. Fully Associative Cache

특징:

블록이 캐시 아무 곳이나 저장 가능
conflict miss 거의 없음 → miss rate 최소화

단점:

모든 entry에 대해 tag를 비교해야 함
comparator가 너무 많아짐 → hit time 증가
하드웨어 비용 증가

장점과 단점이 극단적이라 현실에서는 거의 사용되지 않음(아주 작은 TLB 등에서만 사용).

7. Set Associative Cache (현실에서 가장 많이 쓰는 구조)

n-way set associative 구성:

캐시가 여러 세트로 나뉨
각 set은 n개의 block(way)을 가짐
block number mod (#sets) 로 set 결정
set 내부에서는 n개의 block 중 아무 곳에나 저장 가능

장점:

Direct-mapped보다 conflict miss 현저히 감소
Fully associative보다 hardware 비용 낮음

hit time은 다음 순서:

Direct < Set Associative < Fully Associative

8. Associativity 예제 (Direct vs 2-way vs Fully)

블록 접근 순서:

0, 8, 0, 6, 8

결과:

❗ Direct-mapped

Miss: 5
Replacement: 매우 많음 (거의 매번)

❗ 2-way

Miss: 4
Replacement: 2회

❗ Fully associative

Miss: 3
Replacement: 0

결론:

Associativity 증가 → Miss rate 감소
하지만 hit time이 증가하므로 무조건 많이 넣을 수 없음

9. Associativity의 실제 효과(데이터 기반)

64KB D-cache, 16-word block 기준

1-way: 10.3%
2-way: 8.6%
4-way: 8.3%
8-way: 8.1%

즉,

1-way → 2-way 변화: 큰 감소 2-way → 4-way 변화: 조금 감소 4-way 이후: 거의 감소 없음

현대 CPU 대부분 2-way ~ 8-way 정도 사용함.

10. Replacement Policy (교체 정책)

Set-associative에서 set이 꽉 찼을 때:

빈 엔트리가 있으면 → 그곳 사용
없으면 교체 대상 선택해야 함

대표 정책:

✔ LRU (Least Recently Used)

가장 오래 사용하지 않은 block을 교체
2-way는 매우 쉽고 정확함
4-way는 관리 가능
8-way 이상에서는 회로가 매우 복잡해짐

✔ Random

성능은 LRU와 거의 동일
하드웨어 구현은 훨씬 쉽다

11. Multilevel Cache (L1/L2/L3)

캐시 miss penalty를 줄이는 기술

✔ L1 Cache

CPU와 가장 가까움
매우 빠르지만, 용량 작음
hit time이 가장 중요 (빠르게 해야 함)

✔ L2 Cache

L1 miss를 처리
용량 크고, hit time은 조금 느려도 됨
miss rate 줄이는 것이 중요

✔ L3 Cache

고급 시스템에서 추가됨
일반적으로 여러 코어가 공유

전체 구조:

CPU → L1 → L2 → Memory

12. Multilevel Cache 성능 예제

조건:

Base CPI = 1
Clock = 4GHz → 1 cycle = 0.25ns
Miss rate = 2%
Memory access 100ns → 400 cycles

✔ L1만 존재할 때

CPI = 1 + (0.02×400) = 9

✔ L2 cache 추가

L2 access = 5ns = 20 cycles
Global miss rate to memory = 0.5%

CPI = 1 + (0.02×20) + (0.005×400) = 1 + 0.4 + 2 = 3.4

L2 덕분에 성능이 9 → 3.4, 즉 2.6배 향상됨.