직접 매핑 캐시(direct-mapped cache)의 동작
직접 매핑 캐시의 실제 동작
캐시가 세트를 선택하고 라인을 식별하는 메커니즘은 매우 단순합니다.
그럴 수밖에 없습니다 — 하드웨어는 이 과정을 수 나노초 단위로 수행해야 하기 때문입니다.
하지만 이런 비트 조작은 인간에게 혼란스러울 수 있으므로, 구체적인 예를 통해 과정을 살펴보겠습니다.
다음과 같은 직접 매핑 캐시가 있다고 가정합시다:
(S, E, B, m) = (4, 1, 2, 4)즉,
- 캐시는 4개의 세트(S=4) 를 가지고 있고,
- 세트당 1개의 라인(E=1),
- 블록 크기(B)=2바이트,
- 주소 크기(m)=4비트입니다.
또한, 각 워드는 1바이트라고 가정합니다 (비현실적이지만 예시 단순화를 위한 가정입니다).
주소 공간 나누기
4비트 주소 공간 전체를 나누어보면, 아래 그림(Figure 6.30)처럼
각 주소는 [Tag | Index | Offset] 비트로 구성됩니다.
흥미로운 점:
-
Tag와 Index의 조합은 메모리의 각 블록을 유일하게 식별합니다.
예:- 블록 0은 주소 0과 1로 구성
- 블록 1은 주소 2와 3
- 블록 2는 주소 4와 5
- 블록 3은 주소 6과 7
- 블록 4는 주소 8과 9, … 이런 식으로 구성됩니다.
-
메모리 블록은 8개지만, 캐시 세트는 4개뿐이므로
여러 블록이 같은 세트에 매핑됩니다.
예:- 블록 0과 4 → 세트 0
- 블록 1과 5 → 세트 1
- 블록 2와 6 → 세트 2
- 블록 3과 7 → 세트 3
-
같은 세트에 매핑된 블록들은 Tag 비트로 구분됩니다.
예:- 블록 0의 태그 = 0, 블록 4의 태그 = 1
- 블록 1의 태그 = 0, 블록 5의 태그 = 1 등.
Figure 6.30 — 4비트 주소 공간 예시
| 주소(10진수) | Tag (t=1) | Index (s=2) | Offset (b=1) | 블록 번호(10진수) |
|---|---|---|---|---|
| 0 | 0 | 00 | 0 | 0 |
| 1 | 0 | 00 | 1 | 0 |
| 2 | 0 | 01 | 0 | 1 |
| 3 | 0 | 01 | 1 | 1 |
| 4 | 0 | 10 | 0 | 2 |
| 5 | 0 | 10 | 1 | 2 |
| 6 | 0 | 11 | 0 | 3 |
| 7 | 0 | 11 | 1 | 3 |
| 8 | 1 | 00 | 0 | 4 |
| 9 | 1 | 00 | 1 | 4 |
| 10 | 1 | 01 | 0 | 5 |
| 11 | 1 | 01 | 1 | 5 |
| 12 | 1 | 10 | 0 | 6 |
| 13 | 1 | 10 | 1 | 6 |
| 14 | 1 | 11 | 0 | 7 |
| 15 | 1 | 11 | 1 | 7 |
캐시 시뮬레이션
초기 상태: 캐시는 비어 있음 (모든 valid 비트 = 0)
| Set | Valid | Tag | block[0] | block[1] |
|---|---|---|---|---|
| 0 | 0 | |||
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | 0 |
1️⃣ Read word at address 0
- 세트 0의 valid bit = 0 → cache miss
- 메모리에서 block 0을 읽어와 세트 0에 저장.
m[0],m[1]이 캐시로 복사됨.
| Set | Valid | Tag | block[0] | block[1] |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | 0 |
2️⃣ Read word at address 1
- 같은 블록 내 데이터 (
m[1]) → cache hit - 세트 0의 상태는 변하지 않음.
3️⃣ Read word at address 13
- 주소 13 → 세트 2
valid bit = 0 → cache miss - 메모리에서 block 6을 가져와 세트 2에 저장.
| Set | Valid | Tag | block[0] | block[1] |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
4️⃣ Read word at address 8
- 주소 8 → 세트 0, valid=1 → 확인 필요
- 하지만 Tag(1) ≠ 기존 Tag(0) → cache miss
- 블록 4를 세트 0에 로드 (기존 block 0 교체)
| Set | Valid | Tag | block[0] | block[1] |
|---|---|---|---|---|
| 0 | 1 | 1 | m[8] | m[9] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
5️⃣ Read word at address 0
- 다시 주소 0을 읽음 → 세트 0,
하지만 이제 태그가 다름 (현재 Tag=1, 필요 Tag=0) - Cache miss 발생
- block 0이 다시 세트 0에 로드됨 → block 4가 교체됨
| Set | Valid | Tag | block[0] | block[1] |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
이와 같은 미스는 충돌 미스(conflict miss) 라고 부릅니다.
캐시 공간은 충분하지만, 서로 다른 블록들이 같은 세트에 매핑되어
계속 서로를 덮어쓰는 상황에서 발생합니다.
there ain't no shortcuts