KAIST CS311 전산기조직 (Spring 2023) 교재: Computer Organization and Design: The Hardware/Software Interface (Patterson & Hennessy, MIPS Edition)
캐시 메모리 (Cache)
캐시의 개념
캐시(Cache)는 하드웨어에서 관리하는 빠른 메모리(SRAM)이다. CPU와 메인 메모리(DRAM) 사이의 속도 차이를 줄이기 위해, 자주 접근하는 데이터를 CPU 가까이에 복사해 두는 것이 캐시의 핵심 아이디어다.
┌───────┐ ┌───────────┐ ┌──────────────┐
│ CPU │────▶│ Cache │────▶│ Main Memory │
│ │ │ (SRAM) │ │ (DRAM) │
└───────┘ └───────────┘ └──────────────┘
fast ~1-2 cycle ~100 cycle
캐시의 성능을 측정하는 핵심 지표가 **AMAT(Average Memory Access Time)**이다:
AMAT = Hit Time + Miss Rate × Miss Penalty
- Hit Time: 캐시에 데이터가 있을 때(Hit) 접근하는 데 걸리는 시간
- Miss Rate: 캐시에 데이터가 없을 확률
- Miss Penalty: 캐시 미스 시 메인 메모리에서 데이터를 가져오는 데 걸리는 시간
캐시의 기본 용어
캐시를 이해하려면 다음 용어들을 정확히 알아야 한다:
- Block (= Cache Block = Line = Cache Line): 캐시로 복사되는 데이터의 기본 단위. 보통 64바이트(= 16 word)이다.
- Set: 캐시의 Index로 접근 가능한 Block의 묶음. 한 Set에는 Way의 수만큼 Block이 존재한다.
- Way: 한 Set에 들어갈 수 있는 Block의 수. Way에 따라 캐시의 종류가 결정된다.
캐시의 구분: Way에 따른 분류
Way의 수에 따라 캐시를 세 가지로 구분할 수 있다:
┌─────────────────────────────────────────────────────────────┐
│ Direct Mapped (Way = 1) │
│ │
│ Set 0: [ Block ] │
│ Set 1: [ Block ] │
│ Set 2: [ Block ] │
│ Set 3: [ Block ] │
│ ... │
│ 각 Set에 Block이 1개뿐 → 충돌(conflict) 잦음 │
├─────────────────────────────────────────────────────────────┤
│ N-way Set Associative (Way = N) │
│ │
│ Set 0: [ Block | Block | ... | Block ] ← N개 │
│ Set 1: [ Block | Block | ... | Block ] │
│ ... │
│ 같은 Set 내에서 N개 Block 중 빈 곳에 저장 가능 │
├─────────────────────────────────────────────────────────────┤
│ Fully Associative (Way = 전체 Block 수) │
│ │
│ Set 0: [ Block | Block | Block | ... | Block ] │
│ Set이 1개뿐이고, 어디든 저장 가능 │
│ 충돌 없지만 비교 회로가 많이 필요 │
└─────────────────────────────────────────────────────────────┘
Cache Fields: 주소의 분해
캐시는 **Physical Address(PA)**를 사용한다. PA를 다음과 같이 세 필드로 분해한다:
Physical Address (PA):
┌──────────┬────────────┬──────────────────────────┐
│ Tag │ Set Index │ Block Offset / Byte Offset│
└──────────┴────────────┴──────────────────────────┘
├──────────┬───────┤
│Block Off.│Byte Off│
└──────────┴───────┘
각 필드의 역할:
- Byte Offset: word 내에서 byte를 구별한다. word = 4바이트이므로 항상 2 bit이다.
- Block Offset: Block 내에서 word를 구별한다. Block에 포함된 word 수에 따라 비트 수가 결정된다.
- Set Index: 캐시에 포함된 Set 수에 따라 결정된다.
log₂(#Sets)비트. - Tag: 같은 Set에 매핑되는 서로 다른 Block을 구별하기 위한 나머지 비트.
PA에서 Block Offset과 Byte Offset을 뺀 나머지가 Block Address이다. 같은 Set Index일 때, Tag가 같아야 Block Address가 같은 것이다.
Cache Size 관계식
캐시 크기와 주소 비트 사이의 관계를 정리하면:
Cache Size = Block Size × #Sets × Way
각 필드의 비트 수 결정 과정:
Physical Address Space → PA 비트 수 결정
│
▼
Block Size (바이트 수) → Block Offset + Byte Offset 비트 수
│
▼
#Sets in Cache → Set Index 비트 수
│
▼
나머지 비트 → Tag 비트 수
예시: PA = 32 bit, Block Size = 64B, Cache Size = 16KB, 4-way
Block Size = 64B → Byte Offset = 2 bit, Block Offset = 4 bit (16 words)
(총 6 bit)
#Sets = Cache Size / (Block Size × Way) = 16KB / (64B × 4) = 64
Set Index = log₂(64) = 6 bit
Tag = 32 - 6 - 6 = 20 bit
PA: [ 20-bit Tag | 6-bit Set Index | 4-bit Block Off | 2-bit Byte Off ]
캐시 접근 과정
캐시에 데이터를 읽는 과정을 단계별로 살펴보자:
1. PA에서 Set Index를 추출 → 해당 Set으로 이동
2. Set 내의 모든 Way에서 Tag를 비교
3. Tag가 일치하고 Valid bit = 1 → Cache Hit!
4. Tag가 일치하지 않음 → Cache Miss → Main Memory에서 Block을 가져옴
┌──────────────────────────────────────────────┐
│ Set 0: [V|Tag|Data] [V|Tag|Data] (2-way) │
│ Set 1: [V|Tag|Data] [V|Tag|Data] │
│ Set 2: [V|Tag|Data] [V|Tag|Data] ◄── Set Index로 선택
│ Set 3: [V|Tag|Data] [V|Tag|Data] │
│ ... │
└──────────────────────────────────────────────┘
│ │
▼ ▼
Tag 비교 Tag 비교
│ │
└──────┬───────┘
▼
Hit or Miss?
Cache Performance: 캐시 성능 분석
캐시를 사용했을 때 전체 CPU 성능이 얼마나 개선되는지 분석해보자.
CPU Time = IC × CPI × CC
- IC: Instruction Count
- CPI: Cycles Per Instruction
- CC: Clock Cycle time
CPI를 이상적인 경우와 메모리 지연(stall)으로 분리하면:
CPI = CPI_ideal + CPI_stall
CPI_stall = Miss Rate × Miss Penalty
문제점: Hit Time이 아무리 빨라도 Miss Rate이 크면 CPI 개선이 크지 않다.
예시: L1 Hit Time = 2 cycle, Miss Rate = 2%, Miss Penalty = 100 cycle
CPI_stall = 0.02 × 100 = 2 cycle
총 CPI = CPI_ideal + 2
→ Hit Rate 98%인데도 stall이 상당히 크다!
Miss Rate을 줄이는 방법
방법 1: N-way Set Associative Cache
Direct Mapped 대신 N-way Set Associative를 사용하면 같은 Set에 N개의 Block을 저장할 수 있으므로 충돌 미스(conflict miss)가 줄어든다. 다만 비교 회로가 늘어나므로 Hit Time이 약간 증가할 수 있다.
방법 2: Multi-Level Cache
단일 레벨 캐시 대신 여러 레벨의 캐시를 두어 Miss Penalty를 줄인다:
L1 Miss Rate L2 Miss Rate
│ │
▼ ▼
┌─────┐ 항상 ┌──────────┐ ┌──────────┐ ┌─────────────┐
│ CPU │───────▶│ L1 Cache │───────▶│ L2 Cache │───────▶│ Main Memory │
└─────┘ └──────────┘ └──────────┘ └─────────────┘
Hit Time Miss Penalty Miss Penalty
= 2 cycle (L1 기준) (L2 기준)
= L2 접근 = 100 cycle
- Miss Rate은 어디에서 Miss가 발생했느냐에 따라 결정된다.
- Miss Penalty는 어디로 Access하러 가느냐에 따라 결정된다.
L1 캐시는 속도를 우선으로 작게, L2 캐시는 Miss Rate을 줄이기 위해 크게 설계하는 것이 일반적이다.
Physical Cache vs Virtual Cache
지금까지 배운 캐시는 Physical Address를 입력으로 사용하는 Physical Cache이다.
Physical Cache의 접근 과정:
┌─────┐ VA ┌─────────────────┐ PA ┌───────────┐
│ CPU │────────▶│ Page Table / TLB │────────▶│ Cache │
└─────┘ └─────────────────┘ └───────────┘
VA → PA 변환 먼저! PA로 캐시 접근
Translation(VA → PA)이 먼저 일어나고, 그 다음에 Cache를 접근한다. 따라서 Main Memory의 data를 참조하기 전에 Cache로부터 data를 참조하기 전에 먼저 VA를 PA로 바꾸는 Translation 과정이 선행되어야 한다.
이 Translation이라는 Memory Access 조차도 Cache를 이용해 optimize하고 싶다면? 먼저 사전적인 PA를 Cache에 두고, 이후에 VA를 Cache의 input으로 넘기면 Cache에서의 결과를 받아오고 싶은 것이다.
Virtual Cache는 VA를 Cache의 input으로 사용한다:
┌─────┐ VA ┌───────────┐ ┌─────────────────┐
│ CPU │────────▶│ Cache │────────▶│ Page Table / TLB │
└─────┘ └───────────┘ └─────────────────┘
VA로 바로 캐시 접근 Miss 시에만 변환
TLB라는 CPU chip 내부의 MMU에 있는 set-associative hardware cache를 이용해 Virtual Cache를 구현한다. PA를 Cache의 input으로 넘기면 Physical Cache, VA를 Cache의 input으로 넘기면 Virtually Addressed Cache이다.
가상 메모리 (Virtual Memory)
개념
가상 메모리(Virtual Memory)는 Physical Memory가 실제보다 더 커 보이게 하는 메모리 관리 기법이다.
┌──────────────────────┐
│ Virtual Address │ ┌──────────────┐
│ Space (per process)│ │ │
│ │ │ Main Memory │
│ ┌────┐ ┌────┐ │ │ (DRAM) │
│ │Page│ │Page│ ... │ ◄────▶ │ │
│ └────┘ └────┘ │ └──────────────┘
│ ... │ ▲
│ [Disk에 존재] │ │
└──────────────────────┘ ┌──────────────┐
│ Disk (SSD/ │
│ HDD) │
└──────────────┘
핵심 원리: Main Memory를 Secondary Memory(Disk)의 Cache로 사용한다 (DRAM Cache).
주요 사실들:
- Program(machine code)에 적힌 메모리의 주소는 모두 Virtual Address이다.
- Program은 본인만의 virtual address space를 compile된다.
- Program에는 Physical Address가 적혀있지 않다 (compile 단계에서는 PA가 결정되지 않음).
- Physical Address는 Run-Time에 결정된다.
- VA에서 PA로의 변환을 Address Translation이라 한다.
- Memory Request의 가장 첫 단계는 Address Translation이다. 이후에 Memory Access가 진행된다.
페이지 (Page)
메모리를 block 단위로 나누어 관리하는데, 이 블록을 Page라 한다 (word의 cache block과 유사한 개념).
48-bit Virtual Address Space 예시:
주소 1개 = 1 Byte → VM의 size = 2^48 Byte
page size = 4KB = 2^12 Byte (주소 2^12개 묶음을 page라 함)
VM은 총 2^(48-12) = 2^36개의 Virtual Page로 구성
┌──────────────────────┬─────────────┐
│ Virtual Page Number │ Page Offset │
│ (VPN) │ (PO) │
│ 36 bit │ 12 bit │
└──────────────────────┴─────────────┘
- VM 내에서 원하는 Page를 찾을 때 → 2^36개의 Page Number로 구분
- Page 내에서 원하는 Address를 찾을 때 → 2^12개의 Page Offset으로 구분
예를 들어, 48-bit VA = [0010..00100 | 0110..0] 으로 해석 가능:
├── VPN (36 bit) ──┤── PO (12 bit) ──┤
페이지 테이블 (Page Table)
Page Table은 Virtual Page와 Physical Frame을 Mapping하는 Table이다. 개념적으로 Fully Associative Cache와 같다.
Page Table의 역할: VPN → PPN 변환
┌─────────────────────────────────────────────────────┐
│ Page Table │
│ │
│ Index(VPN) │ Status Bits │ PPN or Disk Addr │
│ ────────── │ ─────────── │ ────────────────── │
│ 0 │ Valid=1 │ PPN = 0x3A │
│ 1 │ Valid=0 │ Disk Addr = ... │
│ 2 │ Valid=1 │ PPN = 0x7F │
│ 3 │ Valid=0 │ Null │
│ ... │ ... │ ... │
└─────────────────────────────────────────────────────┘
Page Table의 특성:
- Page Table은 DRAM에 존재한다.
- 각 Program마다 자신의 Page Table을 갖고 있다.
- VPN으로부터 PPN을 알아내는 Table이다.
- VPN이 Page Table의 index로 사용된다 → VPN 1개가 PTE 1개씩 대응한다.
PTE (Page Table Entry)
Page Table을 구성하는 각각의 항목을 **PTE(Page Table Entry)**라 한다:
PTE = [ Status Bits ] + [ PPN or Disk Address or Null ]
- size of PTE = 32-bit or 64-bit (32-bit OS or 64-bit OS)
(가끔 64-bit에서도 32Byte)
PTBR (Page Table Base Register)
**PTBR(Page Table Base Register)**는 Page Table의 시작 주소(Physical Address)를 담고 있는 CPU 내의 Register이다.
Page Table 크기 = [ # VPN ] × [ size of PTE ]
PTE의 Physical Address (PTEA) 계산:
PTEA = PTBR + (VPN × size of PTE)
┌──────┐ ┌─────────────────────┐
│ PTBR │─── base addr ──▶│ Page Table (in DRAM) │
└──────┘ │ PTE[0] │
│ PTE[1] │
│ PTE[VPN] ◄── 여기! │
│ ... │
└─────────────────────┘
주소 변환 과정 (Address Translation)
VA에서 PA로의 전체 변환 과정을 정리하면:
Virtual Address:
┌────────────────────┬──────────────┐
│ VPN (36 bit) │ PO (12 bit) │
└────────┬───────────┴──────┬───────┘
│ │
▼ │
┌──────────────┐ │
│ Page Table │ │
│ (DRAM) │ │
│ │ │
│ VPN → PPN │ │
└──────┬───────┘ │
│ │
▼ ▼
Physical Address:
┌────────────────────┬──────────────┐
│ PPN │ PO (12 bit) │
└────────────────────┴──────────────┘
* Page Offset은 변환 없이 그대로 사용된다!
Page Fault
Page Table에서 VPN에 대응하는 PTE의 값에 따라 다양한 결과를 얻을 수 있다:
1. PTE에 PPN이 존재하면 → Page Hit
- Virtual Page가 Physical Memory에 이미 Cache 되어 있다!
- 이 VPN의 translation 결과는 PPN이다.
2. PTE에 Disk Address가 존재하면 → Page Fault
- Access하고자 하는 Virtual Page가 아직 Disk에만 있고, Main Memory에 Cache 되지 않은 상태이다.
- Disk에 존재하는 Virtual Page의 정보가 Physical Memory에 아직 Cache 되어 있지 않다.
- 이 Disk Address가 Disk에 존재하는 Virtual Page의 시작 주소를 가리키므로, 이 곳으로 가야 한다.
- → Page Fault Handler가 Page Fault를 해결한다.
Page Hit vs Page Fault:
VA ──▶ Page Table 조회
│
┌────┴────┐
│ │
PPN 존재 Disk Addr 존재
(Valid=1) (Valid=0)
│ │
▼ ▼
Page Hit Page Fault!
(빠름) (Disk I/O 발생 → 매우 느림)
Page Fault가 발생하면:
- OS의 Page Fault Handler가 호출된다.
- Disk에서 해당 Page를 읽어 Main Memory에 적재한다.
- Page Table을 업데이트한다 (Disk Addr → PPN).
- 원래 명령어를 재실행한다.
Page Table은 Fully Associative
Page Table의 구조적 특징을 Cache와 비교해보면:
- 모든 VPN이 어떤 Physical Frame에도 매핑될 수 있다 → Fully Associative
- Replacement 시 LRU 등의 교체 알고리즘 사용
- Miss Penalty가 매우 크다 (Disk 접근) → Miss Rate을 최소화하는 것이 핵심
Multi-level Page Table
단일 Page Table의 문제: Page Table 하나의 크기가 너무 크다.
예시: 48-bit VA, 4KB page, 8-byte PTE
VPN = 36 bit → 2^36개의 PTE
Page Table 크기 = 2^36 × 8B = 512 GB!
→ 하나의 프로세스당 512GB는 비현실적
해결: Multi-level Page Table
Page Table 자체를 Page 단위로 나누어 계층적으로 관리한다. 사용하지 않는 영역의 Page Table은 할당하지 않으므로 메모리를 절약할 수 있다.
2-level Page Table 구조:
VA: [ L1 Index | L2 Index | Page Offset ]
L1 Index ──▶ Level-1 Page Table
│
▼
L2 Index ──▶ Level-2 Page Table
│
▼
PPN ──┐
│
Page Offset ────┤
▼
Physical Address
실제 시스템(x86-64)에서는 4-level 또는 5-level Page Table을 사용한다.
TLB (Translation Lookaside Buffer)
Page Table이 DRAM에 있으므로, 매번 주소 변환마다 메모리 접근이 필요하다. 이 오버헤드를 줄이기 위해 **TLB(Translation Lookaside Buffer)**를 사용한다.
TLB는 최근 사용한 Page Table Entry를 저장하는 작은 하드웨어 캐시이다.
주소 변환 과정 (TLB 포함):
┌─────┐ VA ┌───────┐ Hit ┌───────────┐
│ CPU │────────────▶│ TLB │────────▶│ PA 바로 사용│
└─────┘ └───┬───┘ └───────────┘
│ Miss
▼
┌──────────────┐
│ Page Table │
│ (DRAM) │
└──────┬───────┘
│
▼
TLB 업데이트 후 재접근
TLB의 특성:
- CPU chip 내부의 MMU에 위치한 set-associative hardware cache
- VPN → PPN 매핑을 캐싱
- TLB Hit 시: 추가 메모리 접근 없이 바로 PA를 얻음 (매우 빠름)
- TLB Miss 시: Page Table을 DRAM에서 조회해야 함 (느림)
전체 메모리 접근 흐름
CPU가 메모리에 접근하는 전체 흐름을 정리하면:
CPU가 VA 생성
│
▼
┌──────────┐
│ TLB 조회 │
└────┬─────┘
│
┌──┴──┐
│ │
Hit Miss
│ │
│ ▼
│ Page Table 조회 (DRAM)
│ │
│ ┌──┴──┐
│ │ │
│ Hit Page Fault
│ │ │
│ │ ▼
│ │ Disk에서 Page 적재
│ │ Page Table 업데이트
│ │ │
│ ▼ ▼
│ TLB 업데이트
│ │
▼ ▼
PA 획득
│
▼
┌──────────┐
│ Cache 조회│ (Physical Cache)
└────┬─────┘
│
┌──┴──┐
│ │
Hit Miss
│ │
│ ▼
│ Main Memory 접근
│ │
▼ ▼
데이터 획득!
이 전체 과정에서 TLB Hit + Cache Hit이 가장 빠른 경로이며, 실제로 대부분의 접근이 이 경로를 따른다.
정리
메모리 계층구조의 핵심을 다시 정리하면:
메모리 계층구조 (Memory Hierarchy):
속도 ▲ 용량 ▲
│ Registers (~0.25 ns) │
│ L1 Cache (~1 ns) │
│ L2 Cache (~5 ns) │
│ L3 Cache (~20 ns) │
│ Main Memory (~100 ns) │
│ SSD (~100 μs) │
│ HDD (~10 ms) │
▼ ▼
| 개념 | 관리 주체 | 주소 유형 | 기본 단위 |
|---|---|---|---|
| Cache | 하드웨어 | Physical Address | Block (64B) |
| Virtual Memory | OS + 하드웨어 | Virtual Address | Page (4KB) |
| TLB | 하드웨어 | VPN → PPN | PTE |
캐시와 가상 메모리는 모두 **지역성(Locality)**을 활용하여 메모리 접근 성능을 극대화하는 메커니즘이다. 캐시는 하드웨어가 투명하게(transparent) 관리하고, 가상 메모리는 OS와 하드웨어(MMU/TLB)가 협력하여 관리한다는 점이 핵심적인 차이이다.