왜 캐시가 필요한가

15편에서 기억장치 계층(memory hierarchy)을 다뤘다. CPU는 매우 빠른데 주기억장치(main memory, 흔히 DRAM)는 상대적으로 느려서, CPU가 명령어나 데이터를 요청할 때마다 주기억장치를 직접 오가면 CPU가 대부분의 시간을 기다리는 데 쓰게 된다. 이 속도 차이를 메우기 위해 CPU와 주기억장치 사이에 캐시(cache memory)라는 작고 빠른 기억장치를 둔다.

캐시가 효과를 내는 이유는 15편에서 다룬 지역성(locality) 때문이다. 프로그램은 방금 사용한 데이터를 곧 다시 사용하는 경향(시간적 지역성, temporal locality)이 있고, 방금 사용한 주소 근처의 데이터를 곧 사용하는 경향(공간적 지역성, spatial locality)이 있다. 그래서 주기억장치에서 데이터를 가져올 때 딱 그 값 하나만 가져오지 않고 블록(block) 단위로 묶어서 캐시에 저장해 두면, 다음 요청이 캐시 안에서 해결될 확률이 높아진다.

쉽게 말하면: 캐시는 CPU 옆에 놓인 작은 즉석 보관함이다. 방금 꺼낸 물건과 그 주변 물건을 통째로 옮겨 두면, 다음에 찾을 때 창고(주기억장치)까지 가지 않고 바로 옆에서 꺼낼 수 있다.

문제는 “주기억장치의 어떤 블록을 캐시의 어떤 자리에 넣을 것인가”다. 이 규칙을 사상(mapping)이라 하고, 크게 직접사상·완전연관사상·세트연관사상 세 가지가 있다. 이 편에서는 같은 조건(같은 주기억 크기·캐시 크기·블록 크기) 하나를 세 가지 방식에 모두 적용해서, 비트 계산이 방식마다 어떻게 달라지는지 정면으로 비교한다.

주소를 세 조각으로 나누는 이유

쉽게 말하면: CPU가 내놓은 하나의 메모리 주소는 캐시 입장에서 “블록 안 몇 번째 바이트인지” · “캐시의 몇 번째 자리인지” · “그 자리가 정말 내가 찾는 블록이 맞는지 확인하는 이름표”로 쪼개서 읽힌다.

CPU가 메모리에 접근할 때 내놓는 하나의 이진수 주소(address)를, 캐시 하드웨어는 항상 다음 세 부분으로 잘라서 해석한다.

1. 오프셋(offset): 블록 하나 안에서 몇 번째 바이트인지를 가리키는 부분. 블록 크기(block size)가 $2^b$바이트면 오프셋은 $b$비트다.
2. 인덱스(index): 캐시의 여러 자리(line, 라인) 중 어느 자리에 저장될지를 가리키는 부분. 캐시의 라인 수가 $2^s$개면 인덱스는 $s$비트다. 완전연관사상에는 인덱스가 없다 — 어느 자리에나 넣을 수 있기 때문이다.
3. 태그(tag): 그 자리에 실제로 들어 있는 블록이 지금 찾는 블록이 맞는지 확인하는 “이름표” 부분. 전체 주소 비트 수에서 인덱스와 오프셋을 뺀 나머지가 태그다.

• 전체 주소 비트: 주기억장치의 전체 바이트 수가 $2^n$이면 $n$비트
• 인덱스 비트: 캐시 라인 수가 $2^s$개면 $s$비트(완전연관사상은 0)
• 오프셋 비트: 블록 크기가 $2^b$바이트면 $b$비트

공통 조건: 이번 편 전체에서 쓰는 하나의 예제

세 가지 사상 방식을 공정하게 비교하기 위해, 다음 조건을 처음부터 끝까지 고정한다.

• 주기억장치(main memory) 전체 크기: $1\text{MB} = 2^{20}$바이트
• 캐시(cache) 전체 크기: $4\text{KB} = 2^{12}$바이트
• 블록(block) 크기: $16\text{바이트} = 2^4$바이트

1단계: 전체 주소 비트 수를 구한다. 주기억장치가 $2^{20}$바이트이므로, 이를 모두 가리키려면 주소가 20비트 필요하다.

2단계: 오프셋 비트 수를 구한다. 블록 크기가 $2^4 = 16$바이트이므로, 오프셋은 4비트다. 이 값은 세 가지 사상 방식 모두에서 동일하다(블록 크기가 같기 때문).

3단계: 캐시에 들어갈 수 있는 블록(라인) 개수를 구한다. 캐시 전체 크기를 블록 크기로 나누면 캐시가 몇 개의 블록을 동시에 담을 수 있는지 나온다.

이 256개의 라인을 세 가지 사상 방식이 각각 다른 규칙으로 채운다. 이제부터 방식별로 인덱스·태그 비트를 계산한다.

직접사상: “주소로 자리가 정해진다”

쉽게 말하면: 직접사상(direct mapping)은 각 주기억 블록이 갈 수 있는 캐시 자리가 딱 하나로 정해져 있는 방식이다. 자리를 두고 경쟁할 필요는 없지만, 같은 자리를 두고 다투는 블록끼리는 서로를 밀어낸다.

직접사상에서는 캐시 라인 수만큼 인덱스 비트가 그대로 필요하다. 캐시 라인이 256개($2^8$개)이므로 인덱스는 8비트다.

이제 태그 비트를 계산한다.

직접사상의 규칙은 간단하다. 주기억장치의 블록 번호를 캐시 라인 수(256)로 나눈 나머지가 그 블록이 들어갈 캐시 자리(인덱스)다.

완전연관사상: “아무 자리에나 넣을 수 있다”

쉽게 말하면: 완전연관사상(fully associative mapping)은 어떤 블록이든 캐시의 256개 자리 중 아무 곳에나 들어갈 수 있는 방식이다. 자리를 지정할 필요가 없으니 인덱스 자체가 없다.

완전연관사상은 “몇 번째 자리에 넣을지”를 주소로 미리 정하지 않는다. 대신 256개 라인 전부에 태그를 동시에 비교(병렬 비교, parallel comparison)해서 원하는 블록이 어딘가에 있는지 찾는다. 그래서 인덱스 비트가 0비트다.

직접사상과 비교하면 태그가 8비트에서 16비트로 늘어난 것을 볼 수 있다. 인덱스가 하던 “자리를 좁혀 주는” 역할이 사라지니, 태그 하나가 그 블록의 정체를 훨씬 더 많은 정보로 증명해야 하기 때문이다.

세트연관사상: 두 방식의 절충

쉽게 말하면: 세트연관사상(set-associative mapping)은 캐시 라인을 몇 개씩 묶어 “세트(set)“를 만들고, 주소로 세트는 정해 주되 그 세트 안 여러 자리 중 어디에 넣을지는 자유롭게 두는 절충안이다.

이번 예제에서는 4-way 세트연관사상(한 세트에 4개 라인)을 계산한다. “$k$-way”의 $k$는 한 세트에 몇 개의 라인이 있는지를 뜻한다.

1단계: 세트 개수를 구한다. 전체 라인 256개를 4개씩 묶으므로 세트는 64개다.

2단계: 인덱스(세트 인덱스) 비트를 구한다. 세트가 64개($2^6$개)이므로 인덱스는 6비트다.

3단계: 태그 비트를 구한다.

세트연관사상에서는 주소로 세트 번호까지만 정해지고, 그 세트 안의 4개 자리 중 어디에 넣을지는(그리고 어느 것을 내보낼지는) 뒤에서 다룰 교체 정책이 결정한다. 즉 세트연관사상은 “세트를 찾을 때는 직접사상처럼 주소로 바로 찾고, 세트 안에서는 완전연관사상처럼 자유롭게 넣는다.”

세 방식 비교 정리

같은 조건(주기억 1MB, 캐시 4KB, 블록 16바이트)에서 계산한 결과를 한 번에 모으면 다음과 같다.

이 표에서 알 수 있는 규칙: 인덱스 비트가 줄어들수록(자리 선택의 자유도가 커질수록) 태그 비트는 늘어난다. 오프셋은 블록 크기가 고정이므로 항상 동일하다. 직접사상(인덱스 최대, 태그 최소)과 완전연관사상(인덱스 0, 태그 최대)이 양 끝에 있고, 세트연관사상은 $k$-way의 $k$ 값에 따라 그 사이 어딘가에 위치한다.

적중률과 평균 접근시간 계산

쉽게 말하면: 캐시가 있어도 항상 캐시에서 찾아지는 것은 아니다. 캐시에서 찾아질 확률(적중률)과 못 찾았을 때 치러야 하는 추가 비용(실패 손실)을 합쳐서 평균적으로 한 번 접근하는 데 드는 시간을 구할 수 있다.

적중(hit)은 CPU가 요청한 데이터가 캐시 안에 있는 경우이고, 실패(miss)는 캐시에 없어서 주기억장치까지 가야 하는 경우다. 적중률(hit rate, $H$)은 전체 접근 중 적중이 차지하는 비율이고, 실패율(miss rate)은 $1 - H$다.

평균 기억장치 접근시간(Average Memory Access Time, AMAT) 공식은 다음과 같다.

• $T_{\text{cache}}$: 캐시 접근시간(적중이든 실패든 캐시를 먼저 확인하는 데 드는 시간)
• $H$: 적중률(0과 1 사이의 값, 예: 0.95는 95%)
• $T_{\text{penalty}}$: 실패 손실(miss penalty). 캐시에 없어서 주기억장치까지 다녀오는 데 걸리는 추가 시간

예제: $T_{\text{cache}} = 10\text{ns}$, $T_{\text{penalty}} = 100\text{ns}$, $H = 0.95$

1단계: 공식에 값을 대입한다.

2단계: 실패율을 계산한다.

3단계: 실패 손실 항을 계산한다.

4단계: 두 항을 더해 최종 답을 낸다.

결과 해석: 캐시 자체는 10ns면 확인이 끝나지만, 100번 중 5번은 캐시에 없어서 100ns를 추가로 더 써야 한다. 이 5번의 비용을 전체 평균에 나눠 담으면 평균 접근시간은 15ns가 된다. 만약 적중률이 0.99로 올라가면 $10 + 0.01 \times 100 = 11\text{ns}$로 크게 줄어드는데, 이것이 바로 캐시 설계에서 적중률을 조금만 높여도 체감 성능이 크게 개선되는 이유다.

교체 정책: 자리가 다 찼을 때 누구를 내보낼까

쉽게 말하면: 세트연관사상이나 완전연관사상처럼 한 블록이 여러 자리 중 아무 데나 들어갈 수 있는 방식에서는, 그 자리가 이미 다 차 있을 때 “누구를 내보내고 새 블록을 넣을지” 정하는 규칙이 필요하다.

직접사상은 자리가 하나로 고정되어 있어 교체 정책이 필요 없다(그 자리를 무조건 새 블록으로 덮어쓴다). 반면 완전연관사상과 세트연관사상은 후보 자리가 여러 개이므로 교체 정책(replacement policy)이 필요하다. 대표적으로 세 가지가 있다.

1. LRU(Least Recently Used, 최소 최근 사용): 가장 오랫동안 사용되지 않은 블록을 내보낸다. 시간적 지역성을 가장 잘 반영하지만, “누가 가장 오래됐는지” 계속 추적해야 해서 하드웨어 비용이 크다.
2. FIFO(First-In First-Out, 선입선출): 가장 먼저 들어온 블록을 내보낸다. 사용 빈도와 무관하게 “입장 순서”만 기억하면 되어 구현이 간단하다.
3. 랜덤(Random): 후보 중 하나를 무작위로 내보낸다. 추적 비용이 전혀 없지만 특정 상황에서는 성능이 들쭉날쭉하다.

예제: 3개 자리(라인)에 블록 참조열 1, 2, 3, 4, 1, 2, 5, 1, 2, 3을 순서대로 요청

같은 참조열을 LRU와 FIFO 두 정책으로 각각 채워 보면서 실패(miss) 횟수를 비교한다. 자리는 3개뿐이라고 가정한다.

LRU로 채우기

LRU 결과: 실패 7회, 적중 3회. 6번 요청에서 2가 적중하는 이유는 방금(5번) 1을 썼지만 2도 그 이전에 쓴 적이 있어 아직 자리를 지키고 있었기 때문이다.

FIFO로 채우기

FIFO 결과: 실패 8회, 적중 2회. FIFO는 “최근에 다시 쓰였는지”를 전혀 보지 않고 순서만 보므로, 6번 요청에서 방금(5번 바로 전에) 자주 쓰인 2를 내보내는 비효율이 생긴다.

결과 해석: 같은 참조열에서 LRU(실패 7회)가 FIFO(실패 8회)보다 실패가 적다. 이는 이 예제가 시간적 지역성을 보이는 패턴(1, 2가 반복해서 다시 요청됨)이기 때문이며, LRU가 “최근에 다시 쓰인 블록”을 우선 보호하는 정책이라 이런 패턴에 유리하다. 랜덤 정책은 후보 중 아무거나 뽑으므로 같은 참조열에 대해서도 실행할 때마다 실패 횟수가 달라질 수 있어, 이 문서와 같은 고정된 단계별 표로 미리 계산할 수 없다는 점이 시험에서 자주 다뤄지는 특징이다.

자주 틀리는 점

• 직접사상에는 교체 정책이 필요 없다는 것을 잊고 LRU·FIFO를 적용하려는 실수가 잦다. 직접사상은 자리가 하나뿐이라 “교체”가 아니라 “무조건 덮어쓰기”다.
• AMAT 공식에서 실패율($1-H$)이 아니라 적중률($H$)을 그대로 실패 손실에 곱하는 부호 실수가 흔하다.
• 세트연관사상의 $k$-way에서 $k$는 “세트 개수”가 아니라 “한 세트 안의 라인 개수”라는 점을 혼동하기 쉽다.

핵심 정리

• 캐시 주소는 태그·인덱스·오프셋 세 부분으로 나뉘며, 오프셋은 블록 크기, 인덱스는 캐시(또는 세트) 라인 수, 태그는 나머지로 결정된다.
• 같은 조건(1MB 주기억, 4KB 캐시, 16바이트 블록)에서 직접사상은 (태그 8, 인덱스 8), 완전연관사상은 (태그 16, 인덱스 0), 4-way 세트연관사상은 (태그 10, 인덱스 6)이다.
• 인덱스 비트가 줄면(자리 선택 자유도가 커지면) 태그 비트가 늘어나는 관계가 성립한다.
• 평균 접근시간(AMAT) $= T_{\text{cache}} + (1-H) \times T_{\text{penalty}}$이며, 적중률이 조금만 올라가도 평균 접근시간이 크게 줄어든다.
• 직접사상은 교체 정책이 필요 없고, 완전연관사상·세트연관사상은 LRU·FIFO·랜덤 같은 교체 정책으로 내보낼 블록을 정한다.

마무리 복습

참고 자료

• 유럽/미국 대학 공개 강의자료 - Computer Architecture: Cache, Virtual Memory, DMA 
• 국가평생교육진흥원 독학학위제 - 출제방향/수준