Full beginner lecture
Memory Cache I/O
목표
Memory Cache I/O는 RISC-V lw와 sw가 실제 memory system을 만날 때 벌어지는 일을 다룹니다. 시험에서는 tag/index/offset bit 수 계산, hit/miss trace, AMAT 계산, 그리고 memory-mapped I/O(MMIO)를 일반 memory 접근과 구별하는 설명이 자주 나옵니다. German term은 Speicherhierarchie, Hauptspeicher, Cache, Block, Set, Way, Speicherzugriff, I/O-Geraet처럼 그대로 보존합니다.
직관
CPU register는 아주 빠르지만 작고, Hauptspeicher는 크지만 느립니다. Cache는 그 사이에 있는 작고 빠른 임시 저장소입니다. 책상 위에 최근에 보는 페이지를 올려두는 것처럼, cache는 최근에 썼거나 곧 다시 쓸 가능성이 높은 block을 CPU 가까이에 둡니다.
RISC-V instruction은 여전히 평범한 lw와 sw입니다. 하지만 effective address가 만들어진 뒤에는 memory system이 그 address를 해석합니다. 주소가 RAM range라면 cache lookup을 하고, 주소가 MMIO range라면 device register로 갑니다. 즉 MMIO는 특별한 "I/O instruction"이 아니라 주소 해석의 문제입니다.
Tag, Index, Offset
Cache lookup은 address를 세 조각으로 나누는 것으로 시작합니다.
32-bit byte address, 16 KiB cache, 64 B block, 2-way set associative
sets = cache size / (block size x ways)
= 16 KiB / (64 B x 2)
= 16384 / 128
= 128 sets
offset bits = log2(64 B) = 6
index bits = log2(128 sets) = 7
tag bits = 32 - 7 - 6 = 19
bit: 31 13 12 6 5 0
+----------------------------+-------------+------------+
field: | tag | set index | offset |
bits: | 19 bits | 7 bits | 6 bits |
+----------------------------+-------------+------------+
Index는 "어느 set을 볼 것인가"를 고릅니다. Tag는 "그 set 안의 block이 내가 찾는 memory block이 맞는가"를 확인합니다. Offset은 "block 안의 어느 byte/word를 꺼낼 것인가"를 고릅니다. Hit 조건은 보통 valid = 1이고 stored tag가 requested tag와 같은 것입니다.
AMAT Formula Panel
AMAT(Average Memory Access Time)는 평균 memory access 시간을 계산하는 공식입니다.
AMAT = hit time + miss rate x miss penalty
hit time = 1 cycle
miss rate = 5% = 0.05
miss penalty = 40 cycles
AMAT = 1 + 0.05 x 40
= 1 + 2
= 3 cycles
가장 흔한 실수는 5%를 5로 넣는 것입니다. 그러면 1 + 5 x 40 = 201 cycles라는 말도 안 되는 값이 나옵니다. percent는 반드시 decimal로 바꿉니다.
MMIO Load/Store Flow
RISC-V instruction
sw t0, 0(t1)
|
v
effective address = t1 + 0
|
v
+------------------+
| address decoder |
+------------------+
| normal RAM range | MMIO range
v v
cache lookup I/O-Geraet register
tag/index/offset GPIO, timer, UART, display
CPU 입장에서는 둘 다 sw입니다. 차이는 address decoder가 요청을 Hauptspeicher 쪽으로 보내는지, I/O-Geraet register 쪽으로 보내는지입니다. C 코드에서 hardware register pointer에 volatile이 붙는 이유는 device register read/write가 side effect를 가지며, compiler가 마음대로 생략하거나 재정렬하면 안 되기 때문입니다.
Worked Example 1: Bit Split and AMAT
문제: 32-bit address, cache size 16 KiB, block size 64 B, 2-way set associative cache가 있습니다. Hit time은 1 cycle, miss rate는 5%, miss penalty는 40 cycles입니다. tag/index/offset bit 수와 AMAT를 구하세요.
풀이:
64 B = 2^6이므로 offset은 6 bit입니다.- set 수는
16 KiB / (64 B x 2) = 16384 / 128 = 128입니다. 128 = 2^7이므로 index는 7 bit입니다.- tag는
32 - 7 - 6 = 19 bit입니다. - AMAT는
1 + 0.05 x 40 = 3 cycles입니다.
검산: 19 + 7 + 6 = 32이므로 address bit가 남거나 모자라지 않습니다.
Worked Example 2: Direct-Mapped Conflict Miss
문제: block size가 4 B이고 set이 8개인 direct-mapped cache가 비어 있습니다. s1 = 0일 때 다음 접근이 반복됩니다.
lw s2, 0x04(s1)
lw s3, 0x24(s1)
풀이:
- block size가 4 B이므로 offset은 2 bit입니다.
- block number는 address / 4입니다.
0x04 / 4 = 1, 0x24 / 4 = 9입니다. - direct-mapped에서 set은
block number mod set count로 생각할 수 있습니다. 1 mod 8 = 1, 9 mod 8 = 1이므로 둘 다 set 1로 갑니다.- 첫
0x04는 compulsory miss입니다. 그 뒤 0x24가 같은 set을 차지하며 0x04를 밀어냅니다. 반복하면 둘이 서로를 계속 교체합니다.
정답·검산 확인
capacity가 부족해서가 아니라 같은 set에 충돌하기 때문에 conflict miss가 반복됩니다.
Worked Example 3: MMIO Store
문제: GPIO base address가 0x10012000이고 output_val register offset이 0x0C입니다.
li t1, 0x1001200C
li t0, 0x00000200
sw t0, 0(t1)
풀이:
- effective address는
0x1001200C입니다. 0x10012000 + 0x0C = 0x1001200C이므로 GPIO output_val register 주소입니다.- instruction은 여전히 RISC-V
sw입니다. - address decoder가 이 주소를 MMIO range로 분류하여 GPIO register write로 보냅니다.
0x00000200 = 1 << 9이므로 bit 9가 1로 설정됩니다.
정답·검산 확인
일반 store encoding이지만 효과는 I/O register write입니다.
LRU와 Pseudo-LRU: 어느 Way를 교체할까
입문 설명
Set-associative cache에서 miss가 났고 선택된 set의 모든 Way가 valid라면, 새 block을 넣기 위해 하나를 골라야 합니다. 이 결정을 Ersetzungsstrategie(replacement policy)가 합니다.
- LRU(Least Recently Used): 그 set에서 가장 오랫동안 사용하지 않은 block을 교체합니다.
- echte LRU: 최근 사용 순서를 정확히 저장합니다. Way 수가 많아질수록 상태와 갱신 logic이 복잡해집니다.
- Pseudo-LRU(PLRU): 더 적은 bit로 “덜 최근에 사용한 쪽”을 근사합니다. 항상 진짜 LRU victim을 고르는 것은 아니지만 hardware가 단순합니다.
현행 강의는 2-way cache에서 한 개의 U-bit로 다음 victim Way를 가리키는 방식을 다루고, 2개보다 많은 Way에서는 Bit-PLRU나 Tree-PLRU 같은 근사를 소개합니다. Tree-PLRU의 세부 update 식은 강의에서 더 진행하지 않으므로 여기서 임의의 algorithm을 추가하지 않습니다.
Worked Trace: 2-way LRU와 Valid bit
Übung 12의 조건을 사용합니다: 16-bit address, 2 sets, 16-byte block, 2-way, 처음에는 전부 invalid입니다. offset=4 bits, index=1 bit, tag=11 bits입니다. U-bit는 다음 miss에서 교체할 Way를 뜻하며 U=0 → Way 0, U=1 → Way 1입니다.
| 접근 | block / set / tag | 결과 | 접근 후 Way 0 (V,Tag) | 접근 후 Way 1 (V,Tag) | 접근 후 U |
|---|
0x00 | block 0 / set 0 / tag 0 | compulsory miss, invalid Way 0 채움 | (1,0) | (0,-) | 1 |
0x20 | block 2 / set 0 / tag 1 | compulsory miss, invalid Way 1 채움 | (1,0) | (1,1) | 0 |
0x0C | block 0 / set 0 / tag 0 | hit in Way 0 | (1,0) | (1,1) | 1 |
0x40 | block 4 / set 0 / tag 2 | compulsory miss, LRU Way 1 교체 | (1,0) | (1,2) | 0 |
핵심 trace는 0x0C입니다. 0x00..0x0F와 같은 block이므로 Way 0 hit이고, Way 0이 most recently used가 됩니다. 따라서 다음 miss 0x40에서는 Way 1의 tag 1이 victim입니다.
검산:
block number = floor(address / 16)
set = block number mod 2
tag = floor(block number / 2)
offset = address mod 16
변형 문제
같은 빈 cache에 0x00, 0x20, 0x00, 0x60 순서로 접근합니다. 마지막 victim과 최종 set 0 상태는 무엇인가요?
정답·검산 확인
첫 두 접근 뒤 Way 0=tag 0, Way 1=tag 1입니다. 세 번째 0x00 hit로 Way 0이 최근 사용됩니다. 0x60은 block 6, set 0, tag 3의 첫 접근이므로 compulsory miss이고 LRU인 Way 1의 tag 1을 교체합니다. 최종 상태는 Way 0 (V=1,Tag=0), Way 1 (V=1,Tag=3)입니다.
Active Recall
Q1. 왜 direct-mapped cache에는 replacement 선택이 없나요?
정답 확인
각 memory block이 갈 수 있는 Way가 하나뿐이어서 miss 시 victim이 이미 정해져 있기 때문입니다.
Q2. echte LRU와 Pseudo-LRU의 trade-off는 무엇인가요?
정답 확인
echte LRU는 정확하지만 Way가 많으면 상태·갱신 hardware가 복잡하고, Pseudo-LRU는 더 단순한 상태로 근사하는 대신 항상 정확한 LRU victim을 고르지는 않습니다.
Q3. tag가 같아도 V=0이면 왜 hit가 아닌가요?
정답 확인
그 line의 tag/data가 유효한 cache entry임을 보장하지 않기 때문입니다. Hit 조건은 valid와 tag match가 모두 필요합니다.
근거: current:Uebung\Übung 12.pdf와 current:Uebung\Lösung 12.pdf, pages 1-6; current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 58-63.
Write-Through, Write-Back, Valid/Dirty bit trace
입문 설명
Store가 cache의 word를 바꾸면 Hauptspeicher와 cache 중 어느 시점에 같은 값을 만들지 정해야 합니다.
- Write-Through: cache에 쓸 때마다 Hauptspeicher에도 즉시 씁니다. memory write가 자주 생기지만 cache와 memory의 값 차이를 오래 유지하지 않습니다.
- Write-Back: 우선 cache만 바꾸고 **Dirty bit
D=1**로 표시합니다. 그 line이 나중에 교체될 때 dirty이면 먼저 Hauptspeicher에 되씁니다. - **Valid bit
V**: line의 tag/data가 사용할 수 있는 entry인지 나타냅니다. V=0이면 tag bit pattern이 우연히 같아도 miss입니다. - **Dirty bit
D**: valid한 cache block이 Hauptspeicher에서 가져온 뒤 cache 안에서 수정되었는지 나타냅니다. V=0인 line의 D는 교체 판단에 의미가 없습니다.
Write miss에서 block을 먼저 가져오는지(write-allocate), cache를 우회하는지(no-write-allocate)는 별도 policy입니다. 문제에 주어지지 않았다면 추측하지 않습니다. 아래 trace는 이 선택을 피하기 위해 이미 cache에 있는 block에 store hit가 난다고 명시합니다.
Worked Trace: store hit 뒤 conflict replacement
한 selected line이 처음에 (V=1, Tag=A, D=0, Data=oldA)이고 Hauptspeicher의 A도 oldA라고 가정합니다. 먼저 A에 newA를 store hit하고, 그 다음 같은 line에 mapping되는 B를 load하여 A를 교체합니다.
| 단계 | Write-Through | Write-Back |
|---|
| 시작 | cache A=oldA, memory A=oldA | cache A=oldA, memory A=oldA, D=0 |
store A,newA hit | cache A=newA, memory A=newA 즉시 | cache A=newA, memory A=oldA, D=1 |
load B miss, A victim | A에 대한 추가 write-back 없이 B를 채움 | V=1,D=1인 A를 memory에 먼저 write-back |
| B를 채운 뒤 | line=(V=1,Tag=B,Data=memory[B]) | line=(V=1,Tag=B,D=0,Data=memory[B]) |
| 최종 memory A | newA | eviction 때 newA가 됨 |
Write-Back victim 검사 순서는 다음처럼 손으로 씁니다.
miss
-> victim V=0 ? 그대로 덮기
-> victim V=1 and D=0 ? 그대로 교체
-> victim V=1 and D=1 ? old block write-back 후 교체
-> 새로 읽은 clean block은 V=1, D=0
정답·검산 확인
이 trace에서 A에 대한 Hauptspeicher write는 두 policy 모두 한 번이지만 시점이 다릅니다. Write-Through는 store 순간, Write-Back은 dirty A가 교체되는 순간입니다.
변형 문제
같은 valid clean A에 두 번 연속 store hit한 뒤 B가 A를 교체합니다. A에 대한 Hauptspeicher write 횟수를 Write-Through와 Write-Back 각각 구하세요. 중간 eviction은 없다고 가정합니다.
정답·검산 확인
Write-Through는 store마다 쓰므로 2회입니다. Write-Back은 두 store 동안 cache만 갱신하고 D=1을 유지하다가 eviction 때 최신 A block을 한 번 되쓰므로 1회입니다. 검산은 “store 횟수”가 아니라 “memory가 실제로 갱신되는 사건”을 세는 것입니다.
Active Recall
Q1. Write-Back에서 D=1은 무엇을 뜻하나요?
정답 확인
그 valid block이 cache 안에서 수정되어 Hauptspeicher의 복사본보다 최신이라는 뜻입니다.
Q2. (V=0,D=1)처럼 보이는 line을 교체할 때 write-back해야 하나요?
정답 확인
아닙니다. V=0이면 유효한 cached block이 아니므로 D는 의미가 없고 그대로 채울 수 있습니다.
Q3. Write-Through와 Write-Back의 가장 빠른 구분 문장은 무엇인가요?
정답 확인
Write-Through는 매 store 때 memory도 갱신하고, Write-Back은 dirty block을 eviction할 때 memory를 갱신합니다.
Q4. Dirty bit와 Valid bit의 역할을 서로 바꾸어 말하면 왜 틀리나요?
정답 확인
V는 entry 존재/유효성을, D는 valid entry가 memory와 달라졌는지를 나타내므로 서로 다른 질문에 답합니다.
근거: current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 64-77; current:Uebung\Übung 12.pdf와 current:Uebung\Lösung 12.pdf, pages 1-3.
자주 틀리는 점
- cache size와 block size를 같은 것으로 봅니다.
cache size = block size x sets x ways입니다. - offset을 word offset으로 계산합니다. RISC-V address는 byte address이므로
64 B block은 6 offset bits입니다. - tag만 맞으면 hit라고 생각합니다. valid bit도 1이어야 합니다.
- associativity가 커지면 항상 빨라진다고 말합니다. conflict miss는 줄 수 있지만 comparator와 mux 비용 때문에 hit time이 늘 수 있습니다.
- MMIO를 별도 instruction으로 설명합니다. 실제로는 일반
lw/sw와 address decoding입니다. - LRU를 “가장 먼저 cache에 들어온 block”으로 고정합니다. Hit가 날 때마다 recency가 갱신되므로 insertion time이 아니라 마지막 사용 시점을 추적해야 합니다.
- Write-Back store마다 Hauptspeicher도 즉시 바꿉니다. 그것은 Write-Through이고, Write-Back은 dirty eviction까지 memory 갱신을 미룹니다.
Active Recall
Q1. 32-bit address, 64 B block, 128 sets이면 offset/index/tag는?
정답 확인
offset 6 bit, index 7 bit, tag 19 bit입니다.
Q2. hit 조건을 한 문장으로 말해 보세요.
정답 확인
selected set의 어떤 way에서 valid bit가 1이고 stored tag가 requested tag와 같으면 hit입니다.
Q3. AMAT = 1 + 0.10 x 100의 결과는?
정답 확인
11 cycles입니다.
Q4. compulsory miss와 conflict miss의 차이는?
정답 확인
compulsory miss는 block을 처음 요청해서 생기는 miss이고, conflict miss는 mapping 때문에 필요한 block들이 같은 set에서 서로 밀어내 생기는 miss입니다.
Q5. MMIO에서 sw는 특별한 I/O instruction인가요?
정답 확인
아닙니다. 일반 store instruction이고, effective address가 I/O register range라서 device register로 routing됩니다.
Source Grounding
current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 35-60: cache organization, hit/miss, tag/index/offset, associativity와 LRU trace.current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 61-63: Pseudo-LRU와 multi-level cache 도입.current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 64-77: miss-rate trade-offs, Write-Through, Write-Back와 dirty-bit trace.current:Vorlesung\Rechnerorganisation - Teil 3.pdf, pages 85-99: MMIO address decoder, GPIO register addresses, volatile hardware register pointers.current:Uebung\Übung 11.pdf와 current:Uebung\Lösung 11.pdf, pages 1-6: cache address split, hit/miss와 AMAT.current:Uebung\Übung 12.pdf와 current:Uebung\Lösung 12.pdf, pages 1-6: LRU/Pseudo-LRU, Valid/Dirty bit, Write-Through/Write-Back 및 2-way LRU 표.