Lec 14 part 2 & Lec 15 · non-blocking cache·write policy·multi-level cache 와 virtual memory 도입
정밀 정리 · 검증 2026-09-24 20:18
1개요
1.1non-blocking(lockup-free) cache 와 MSHR 로 miss 처리 중에도 실행을 계속하는 방법을 다룬다.
1.2write-hit(write-through/write-back, dirty bit)과 write-miss(write-allocate/no-allocate) policy, unified vs split I/D cache 를 비교한다.
1.3multi-level cache 설계, inclusive/exclusive(+NINE)와 back-invalidation, timing 으로 cache 구성을 알아내는 reverse engineering 을 설명한다.
1.4Lec 15 도입: virtual memory 의 illusion, address translation, base and bound 까지 (p6 이후는 다음 강의).
2섹션별 정리 상황·문제 → 원인 → 해결
2.10:50–2:26recap: cache write 문제와 store buffer
상황·문제지난 시간 write 문제 복습. write 완료는 늦춰도 성능 영향이 거의 없다.
원인write 가 여러 cycle(tag→data)을 쓰면 뒤따르는 read 와 cache port 를 다툰다.
해결write 는 store buffer 에 넣고 read 를 먼저 처리, cache 가 idle 일 때 buffer 의 write 를 반영.
- read 가 성능에 더 중요하므로 우선 처리
- store buffer 는 cache 가 한가할 때 비운다
2.22:26–5:33blocking vs non-blocking miss
상황·문제miss 동안 CPU 가 통째로 멈추면 miss 가 많을 때 성능이 크게 떨어진다.
원인miss 처리 중에도 독립 instruction 은 실행 가능한데, blocking cache 는 그 기회를 버린다.
해결cache 를 non-blocking 으로 만들고, dependence 가 있는 instruction 만 data 도착 후 실행.
- out-of-order core 에 특히 중요
- in-order 도 store miss 는 뒤 instruction 이 기다릴 필요 없음
- RAW 의존 load 는 stall 후 data 도착 시 forward
2.2.r.1Memory-level parallelism (Wikipedia) ↗ · miss 를 겹쳐 처리하는 memory-level parallelism 개념 (MSHR 자체 언급은 없음)
2.35:33–9:07MSHR 와 primary·secondary·structural miss
상황·문제non-blocking cache 는 처리 중인 miss 정보를 어딘가에 보관해야 다른 요청을 받을 수 있다.
원인miss 한 address, instruction, 목적 register 등을 잃으면 data 도착 시 전달할 곳을 모른다.
해결MSHR(Miss Status Holding Register)에 기록. 첫 miss=primary, 같은 block 재miss=secondary(entry 재사용), MSHR 가 가득=structural miss(stall).
- non-blocking = lockup-free cache
- secondary miss 는 기존 entry 에 정보만 추가
- 강의: 이 이름들보다 cold·capacity·conflict 가 더 중요
2.3.r.1Memory-level parallelism (Wikipedia) ↗ · miss 를 겹쳐 처리하는 memory-level parallelism 개념 (MSHR 자체 언급은 없음)
2.49:07–12:42MSHR entry 구조
상황·문제한 entry 는 V bit, block address 와 miss 한 load 마다 sub-entry 를 가진다.
원인같은 block 에 여러 load 가 miss 할 수 있고, 각 load 의 목적 register·크기·offset 이 다르다.
해결sub-entry 에 dest register, format(byte/half/word/double, sign/zero ext), block offset 기록. 새 miss 는 block address 와 비교해 merge, 완료 시 모두 통지.
- entry 수(예: 4개) = 동시에 처리 가능한 miss 수
- 모든 entry 사용 중이면 pipeline stall (structural miss)
2.512:42–17:37질의응답: MSHR sub-entry 예시 (한국어 설명)
상황·문제'구조가 잘 이해가 안 된다'는 질문에 판서로 다시 설명.
원인table entry 를 bit string 하나로 생각하면 sub-entry 구조가 헷갈린다.
해결같은 block 에 LB·LH·LW 가 miss 하면 sub-entry 3개에 dest register(x3 등), format 00/01/10, block offset 을 기록, block 도착 시 하나씩 core 에 전달.
- 판서: 4× entry, LB x3·LH x4·LW x6
- structural miss = 새 miss 에 쓸 entry 가 없을 때
2.617:37–21:48write-hit policy 1: write-through
상황·문제write hit 때 Lᵢ 만 고칠지, 하위 level 까지 전파할지 정해야 한다.
원인write-through 는 단순하고 I/O 장치가 하위 level 만 보면 최신 값을 얻지만, 모든 store 가 하위로 간다.
해결3.6GHz·IPC 2·store 10%·4 byte → 약 3GB/s write. 고성능 CPU 엔 부적합, L1→L2 는 가능하나 L2→L3 는 비싸다.
- I/O 장치는 core 보다 하위 level 에 가깝다
- read·instruction bandwidth 까지 더하면 부담이 크다
2.6.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
2.721:48–25:03write-hit policy 2: write-back 과 dirty bit
상황·문제write-through 의 bandwidth 부담을 줄여야 한다.
원인같은 block 에 여러 번 쓰면 매번 하위로 보낼 필요가 없다.
해결write hit 시 Lᵢ 만 고치고 dirty bit 설정. evict 때 dirty 면 하위에 write back, clean 이면 그냥 버린다.
- valid bit 외에 dirty bit 추가
- 대가: I/O 접근 시 상위 level 을 확인하거나 core 가 write 를 내려보내야 함 (I/O 접근은 드물다)
2.7.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
2.825:03–29:48write-miss policy: write-allocate vs write-no-allocate
상황·문제write miss 때 block 을 memory 에서 가져와 cache 에 둘지 정해야 한다.
원인write-through 는 어차피 하위로 쓰니 가져올 이유가 적고, write-back 은 같은 block 의 여러 write 를 cache 에서 합쳐야 한다.
해결write-allocate(가져와서 갱신)는 write-back 과, write-no-allocate(하위에만 씀)는 write-through 와 짝.
- locality 가 낮으면 write-no-allocate + write-through
- write-allocate + write-through 도 가능하나 이점이 적다
2.8.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
2.929:48–35:49unified vs split I/D cache
상황·문제instruction 과 data 를 한 cache 에 둘지 나눌지.
원인Harvard(분리)·Princeton(von Neumann, 통합) 은 원래 main memory 용어였고 지금은 cache 설계를 가리킨다.
해결L1 은 split: bandwidth 2배를 싸게 얻고 footprint 가 겹치지 않는다. L2·L3 는 unified: 1MB 통합이 0.5MB+0.5MB 보다 공간을 잘 쓴다.
- instruction 은 작은 footprint·높은 spatial locality·read-only 경향
- 그래도 실제 L1 I/D 는 보통 대칭 설계 (server 프로그램은 instruction footprint 가 큼)
2.1035:49–39:26multi-level cache 와 서버 CPU 예시
상황·문제L1-I/L1-D → unified L2 → unified L3, 가끔 L4.
원인off-chip L4 는 SRAM 대신 eDRAM·DRAM 을 쓴다. AMD EPYC 7742 와 Intel Xeon 8280 은 설계 선택이 달라 latency 가 다르다.
해결표의 latency 는 load-to-use: L3 34 cycle 은 L1·L2 miss 경로 포함, L2 까지 약 17 cycle, 나머지 약 17 cycle 이 L3 접근·전달.
- L1 둘 다 32KB, L2 512KB vs 1MB, L3 256MB total vs 약 40MB
- AMD 는 L3 latency 가 낮고 DRAM latency 가 길다
2.1139:26–41:28multi-level cache 설계 선택
상황·문제level 마다 C, B, a 를 어떻게 정하나.
원인상위는 짧은 latency 가 필수, 하위는 긴 latency 가 허용된다.
해결상위: 작은 C·작은 B·적은 way. 하위: 큰 C·큰 B·높은 associativity. 큰 off-chip cache 는 tag 를 SRAM, data 를 DRAM 에.
- 현대 CPU 에선 상위 block 이 꼭 작지는 않다
- on-chip 은 SRAM, 대용량은 DRAM 기반이 합리적
2.1241:28–45:51inclusive vs exclusive (퀴즈)
상황·문제inclusive: 하위가 상위 내용을 모두 포함. exclusive: block 은 한 level 에만.
원인inclusive 는 중복 때문에 effective capacity 가 작다 (퀴즈 정답: exclusive 가 용량에 유리).
해결inclusive 의 이점: 하위(LLC)에 없으면 상위 어디에도 없음이 보장돼 I/O 등이 하위만 확인하면 된다.
- 학생 답(write-through 가 빠르다, miss 가 적다)을 두고 한국어로 토론
- multi-core 면 L1·L2 가 여럿이라 이 보장이 더 중요
2.1345:51–49:51back-invalidation 문제 (inclusive)
상황·문제core 가 A 를 L1 에서 계속 hit 하면 L2 는 A 접근을 보지 못한다.
원인L2 LRU 에서 A 가 LRU 위치로 밀려 evict 되고, inclusion 유지를 위해 L1 의 A 도 무효화된다.
해결자주 쓰던 A 가 L1·L2 모두에서 사라져 다음 접근은 L3/DRAM. 드물지만 inclusive 의 단점.
- L1 에선 MRU, L2 에선 LRU 위치
- inclusion property: L2 에 못 두면 L1 에도 둘 수 없다
2.1449:51–56:12exclusive 의 lookup 비용, 선택 기준, NINE
상황·문제exclusive 에서 L1·LLC 모두 miss 하면 다른 L1 에 A 가 있을 수 있다.
원인exclusive 는 LLC miss 가 상위 부재를 보장하지 않아 모든 L1 을 확인하거나 모든 L1 tag 를 LLC 에 둬야 한다.
해결크기 비율로 선택: 32KB L1 과 1MB L2 는 inclusive(손실 작음), L2 1MB·L3 1.25MB 면 exclusive(inclusive 면 0.25MB 만 추가). NINE 은 back-invalidation 을 피하지만 양쪽 단점을 일부 가진다.
- coherence 는 이후 강의
- NINE(non-inclusive non-exclusive)은 advanced topic
2.1556:12–1:02:25cache 계층 reverse engineering: capacity 실험
상황·문제spec 에 cache 세부가 없거나, architect 가 chip 을 검증하려 할 때 C·a·B·level 수를 알아내고 싶다.
원인cache 는 functional 로는 투명하지만 timing(load 처리 cycle)으로 드러난다.
해결배열 크기 R 을 16KB→32KB→64KB… 로 늘리며 반복 순회 시간을 잰다. 32KB 까지 빠르다가 64KB 에서 뛰면 L1=32KB, 같은 방식으로 L2(예 256KB).
- for loop 로 반복 접근하고 전체 순회 시간 측정
- R 증가에 따라 계단형 시간 증가
2.161:02:25–1:06:38block size·associativity 실험, lmbench, prefetcher 주의
상황·문제block size·associativity 도 비슷한 microbenchmark 로 알아낼 수 있다 (강의는 slide 만 넘김).
원인prefetcher 가 순차 접근을 예측해 미리 가져오면 capacity 곡선이 평평하게 나올 수 있다.
해결BIOS 에서 prefetcher 를 끄거나, random access 로 prefetcher 를 무력화. lmbench(1996)는 접근 방식 옵션을 제공.
- microbenchmark 로 cache 특성 측정
- 읽기: P&H Ch. 5.8–5.9, 5.12–5.17
2.16.r.2McVoy & Staelin, lmbench: Portable Tools for Performance Analysis (USENIX 1996) ↗ · p26 에 인용된 원 논문
2.171:06:38–1:10:20virtual memory: large·private·uniform 의 illusion
상황·문제C 프로그램은 OS·다른 프로그램·다른 사용자를 신경 쓰지 않고 크고 사적이고 균일한 memory 를 본다.
원인실제 physical memory 는 작고 공유되며 위치마다 비용이 다르다.
해결Part 1 naming & protection: 구멍 없는 큰 연속 공간, 다른 process 로부터 보호. Part 2 demand paging: 4GB DRAM 으로 16GB 사용, 뒤에서 disk 와 swap.
- virtual address space ≫ physical storage
- swap space(disk) 용량에 DRAM 속도
2.181:10:20–1:12:35mechanism: address translation
상황·문제protection 과 demand paging 을 하나의 HW mechanism 으로 구현한다.
원인user process 는 effective address(EA, C pointer)로 동작하고, HW 가 매 memory reference 마다 PA 로 변환한다.
해결변환 결과가 disk 면 HW/OS 가 swap 처리. 변환 HW 와 policy 는 OS 만 privileged operation 으로 제어한다.
- 변환은 programmer 에게 투명
- privileged 구조는 악의적·오류 프로그램으로부터 보호
2.18.r.2Protection ring (Wikipedia) ↗ · supervisor(privileged) mode 와 user mode, privileged instruction
2.191:12:35–1:15:28memory protection 의 진화와 base and bound
상황·문제초기 기계는 single user·single process 라 protection·translation 이 필요 없었다.
원인time-shared 기계에서 여러 task 가 같은 physical memory 를 공유하게 됐다.
해결process 마다 겹치지 않는 연속 영역을 주고, per-process privileged register base(시작)·bound(끝)로 접근이 영역 안인지 검사.
- 나머지(p6 이후)는 다음 강의에서 계속
2.201:15:28–1:17:25마무리와 질의응답: inclusion 과 write policy 조합
상황·문제질문: inclusive/exclusive 와 write-back/write-through 는 어떤 관계인가 → 서로 독립이라 다양한 조합이 가능하다는 답.
3핵심 개념
3.1non-blocking cache(lockup-free cache)
miss 처리 중에도 다른 요청을 받아 독립 instruction 을 계속 실행하게 하는 cache.
3.1.r.1Memory-level parallelism (Wikipedia) ↗ · miss 를 겹쳐 처리하는 memory-level parallelism 개념 (MSHR 자체 언급은 없음)
3.2MSHR(Miss Status Holding Register)
처리 중인 miss 의 block address 와 load 별 dest register·format·block offset 을 보관.
3.3primary / secondary / structural miss
block 첫 miss / 처리 중인 block 에 또 miss / MSHR 가 가득 차 stall.
3.4write-through / write-back
write hit 을 하위까지 전파 / Lᵢ 만 고치고 dirty bit, evict 때 write back.
3.4.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
3.5dirty bit
block 이 들어온 뒤 수정됐는지 표시. clean 이면 evict 때 write back 불필요.
3.5.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
3.6write-allocate / write-no-allocate
write miss 때 block 을 가져와 갱신 / 하위에만 쓰고 cache 에 두지 않음.
3.6.r.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
3.7Harvard / Princeton architecture
split I/D / unified. 원래 main memory 용어, 지금은 cache 설계를 가리킨다.
3.8load-to-use latency
load 실행부터 core 에 data 가 오기까지. 상위 level miss 경로를 포함한다.
3.9inclusive / exclusive / NINE
하위가 상위 포함 / level 간 disjoint / 아무것도 보장 안 함.
3.10back-invalidation
LLC 에서 evict 한 block 을 상위 cache 에서도 무효화해 inclusion 유지.
3.11microbenchmark / lmbench
timing 으로 cache C·B·a 등을 알아내는 작은 프로그램. lmbench 는 1996 년 공개 도구.
3.12effective address(EA) / physical address(PA)
프로그램(pointer)이 쓰는 주소 / HW 가 변환해 실제로 접근하는 주소.
3.13demand paging
DRAM 보다 큰 공간을 쓰게 하려고 뒤에서 DRAM 과 disk 사이에 page 를 swap.
3.14base and bound
process 영역의 시작·끝을 privileged register 로 두고 모든 접근을 범위 검사.
4스스로 확인
4.1non-blocking cache 에서 structural miss 는 언제 생기나?
답
새 miss 에 할당할 MSHR entry 가 없을 때 (모두 사용 중). 이때 pipeline 이 stall 한다.
4.2같은 block 에 LB 와 LW 가 연달아 miss 하면 MSHR 에서 무슨 일이 일어나나?
답
첫 miss 가 entry 할당(primary), 둘째는 같은 entry 에 sub-entry(dest reg·format·offset)를 추가(secondary).
4.33.6GHz, IPC 2, store 10%, 4 byte/store 일 때 write-through 가 만드는 write bandwidth 는?
답
3.6G×2×0.1×4 ≈ 2.9 GB/s, 약 3GB/s.
4.4write-back cache 에 write-allocate 가 어울리는 이유는?
답
같은 block 의 여러 write 를 cache 안에서 합치려면 block 이 cache 에 있어야 한다.
4.5L2 1MB, L3 1.25MB 일 때 L3 를 inclusive 로 하면?
답
L2 내용이 중복돼 L3 로 얻는 추가 용량이 0.25MB 뿐. exclusive 가 적합.
4.6capacity 실험에서 곡선이 평평하게 나오면 의심할 것은?
답
prefetcher. BIOS 에서 끄거나 random access 로 무력화한다.
5참고 자료
5.1Cache (computing) (Wikipedia) ↗ · write-through/write-back, dirty bit, write-allocate/no-write-allocate
5.4McVoy & Staelin, lmbench: Portable Tools for Performance Analysis (USENIX 1996) ↗ · p26 에 인용된 원 논문
5.7Jacob & Mudge, Virtual Memory: Issues of Implementation (IEEE Computer 1998) — UMD DRUM ↗ · p36 읽기 과제 논문, PDF 제공