Lec 17 · Cache 최적화 후반(non-blocking cache·MSHR·victim·way prediction·compiler) 과 Prefetching 입문

1.1ca_L11 p27~48: early restart·critical word first, non-blocking cache 와 MSHR, 실제 chip cache 구성, victim cache, way prediction, compiler optimization(loop interchange·fusion·blocking)

1.2ca_L12 p1~17: prefetching 의 목적·correctness, what/when/where/how 네 질문, software prefetching(binding/non-binding)과 한계

1.3강의는 ca_L12 p17 에서 끝나 p19 이후(hardware prefetcher·FDP·runahead)는 다음 강의로

상황·문제64B·128B 같은 긴 block 에서 CPU 가 실제로 원한 word 는 1~8B 인데 block 전체가 올 때까지 기다리면 miss penalty 가 불필요하게 크다.

원인miss 처리 완료 조건이 "block 전체 도착" 이라 요청 word 와 무관하게 대기한다.

해결early restart: 요청 word(예 word 2)가 도착하는 즉시 CPU 에 전달. critical word first: 요청 word 를 먼저 보내게 하고 나머지는 wrap-around 로 채움 (memory 가 이를 지원해야 함).

상황·문제miss 한 번에 CPU 가 멈추면 이후 hit 가능한 접근도 기다리고, 여러 miss 의 긴 latency 가 직렬로 쌓인다.

원인blocking cache 는 miss 처리 중 다른 접근을 받지 않는다. 같은 cache line 에 두 번째 miss(secondary miss)가 오면 추적 구조가 필요하다.

해결miss 중에도 hit 제공(hit under miss), 여러 miss 를 겹침(miss under miss) → MSHR 필요, full/empty bit 나 out-of-order 실행, pipelined·banked memory 필요. SPEC92 에서 hit under 1 miss 만으로도 AMAT 이 크게 줄고 64 까지 늘리면 더 준다.

상황·문제여러 outstanding miss 와 그 block 을 기다리는 load/store 들을 추적해야 한다.

원인같은 block 에 대한 miss 가 여러 개일 수 있고, 각 load 는 다른 destination register·block offset 을 가진다.

해결MSHR entry = valid·block address·issued bit + load/store entry 여러 개(valid·type·block offset·destination). miss 시 같은 block entry 검색 → 있으면 load/store entry 추가, 없으면 새 MSHR, 여유 없으면 stall. data 도착 시 대기 load/store 에 전달·해제, block 완성 후 cache 에 write 하고 MSHR 해제.

상황·문제cache 크기·계층이 시대에 따라 어떻게 커졌는지 실제 chip 으로 확인.

원인(구성 소개 구간)

해결X704 PowerPC(1997) 2KB L1 I$/D$·32KB L2 → Itanium-2(2002) 16KB/256KB/3MB → Power7(2009) 32KB/256KB/32MB eDRAM L3 → z15(2019) 128KB I$·D$, 4MB L2, 256MB L3.

상황·문제direct-mapped L1 에서는 중요한 data 가 conflict 로 우연히 evict 되기 쉽다.

원인set associativity 가 없어 같은 index 를 쓰는 block 끼리 서로 밀어낸다.

해결L1 에서 evict 된 line 을 4-block fully associative victim cache 에 보관(L2 에도 감), L1 miss 시 VC 검색 → hit 면 L1 으로 올리며 CPU 에 제공. direct-mapped 의 빠른 hit time 유지 + conflict miss 감소.

상황·문제R10000 시절 L2 는 off-chip 이라 cache 에서 나오는 bandwidth(pin 수)가 제한적이었다.

원인모든 way 를 한 번에 읽으려면 외부 SRAM 에 pin 이 너무 많이 필요하다.

해결8,192-bit MRU table 로 index 별 최근 way 를 예측해 먼저 읽음 → 맞으면 짧은 latency, 다른 way 에서 hit 면 추가 latency(slow hit, table 갱신), 둘 다 miss 면 memory 에서 refill. I-cache 는 line 마다 sequential way·branch target way 를 저장해 branch predictor 와 함께 다음 way 예측 (Alpha 21264 유사).

상황·문제hardware 만으론 program 의 나쁜 access pattern 을 바꿀 수 없다.

원인code 순서가 data access sequence 를 결정한다 (예: row-major 배열을 column 방향으로 순회).

해결code 재배치로 spatial·temporal locality 개선, cache bypass(no-allocate hint), 다시 안 쓸 data 는 LRU 위치로. loop interchange(j 를 inner loop 로) → spatial locality, loop fusion(두 loop 합침, a[i]·c[i] 재사용) → temporal locality.

상황·문제naive x=y×z 에서 y 는 row 방향이라 spatial locality 가 있지만 z 는 column 방향이라 locality 가 거의 없다.

원인N 이 크면 z 의 line 이 다시 쓰이기 전에 evict 된다.

해결행렬을 tile(예 4x4) 로 나눠 tile 단위로 부분합 누적 → tile 들이 cache 에 머무는 동안 반복 hit → temporal locality 개선. Q&A: z 를 transpose 하면 naive 에는 도움되지만 blocking 구현에선 tile 이 어차피 cache 에 있어 이득이 작다.

상황·문제memory latency 가 높아 miss 마다 오래 기다린다. compulsory miss 는 cache 를 키워도 남는다.

원인data 를 처음 쓰는 시점에야 fetch 하기 때문. 미래 주소 예측이 어렵고(graph 같은 irregular pattern) timeliness 도 맞춰야 한다.

해결prefetch: 필요하기 전에 cache block 단위로 가져와 miss rate·miss latency 감소 (hardware·compiler·programmer). 잘못 prefetch 해도 architectural state 는 안 바뀌어 correctness 에 영향 없음 (branch·value misprediction 과 대비). L1–L2 사이 prefetcher 가 demand·miss stream 을 보고 요청 생성.

상황·문제prefetcher 설계는 what·when·where·how 를 정해야 한다.

원인쓸모없는 prefetch 는 memory bandwidth·cache/buffer 공간·energy 를 낭비하고, 너무 이르면 evict, 너무 늦으면 latency 를 다 숨기지 못한다.

해결accuracy = used / sent prefetches. 주소는 과거 access pattern 이나 compiler 의 data structure 지식으로 예측. timeliness 는 hardware 를 더 aggressive 하게, software 는 prefetch instruction 을 앞으로 옮겨 개선.

상황·문제prefetch 한 data 를 어디에 두고 prefetcher 를 어디에 둘지 정해야 한다.

원인cache 에 넣으면 단순하지만 유용한 demand data 를 밀어냄(cache pollution). 별도 buffer 는 위치·접근 시점·이동·크기·coherence 문제가 생긴다.

해결현대 시스템은 대부분 cache 에 둔다. L2 에만 넣으면 L1 오염은 없지만 L2 접근 latency. LRU 에서 prefetch block 을 MRU/LRU/중간 중 어디 넣을지는 confidence 에 따라 (강의: 낮으면 LRU, 높으면 MRU). 더 완전한 access pattern(L1 hit 포함)은 accuracy·coverage ↑ 대신 bandwidth·port 부담.

상황·문제prefetch 를 누가 만들지 정해야 한다.

원인software 는 regular pattern 에서만 쉽고, hardware 는 pattern 감지 구조가 필요하다.

해결software: ISA prefetch instruction 을 programmer·compiler 가 삽입. hardware: access 를 monitor 해 pattern/stride 를 찾고 자동 생성. execution-based: main program 보다 앞서 실행되는 thread 가 data 를 touch (software 또는 별도 hardware context).

상황·문제compiler·programmer 가 code 에 prefetch 를 넣는 방법과 문제.

원인binding(regular load 로 register 에) 은 register 를 차지하고 exception(page fault)·다른 processor 의 수정 문제. non-binding(cache 로, 특수 instruction) 은 coherence 걱정은 없지만 hardware 가 무시할 수 있다.

해결array 는 a[i+8] 처럼 쉽게, linked list 는 p->next 로 prefetch. 단 fetch·decode·execute bandwidth 소모, prefetch distance 가 microarchitecture·다른 thread 에 좌우돼 portability 문제, 너무 앞서면 branch 로 accuracy ↓. Alpha 는 R31 load 를 prefetch 로, PowerPC 는 dcbt. graph 같은 pointer 구조는 어렵다. 다음 강의에서 계속.

miss 된 word 를 먼저 받아 CPU 재개, 나머지는 wrap-around 로 채움

miss 처리 중에도 hit 제공(hit under miss), 여러 miss 를 겹침(miss under miss)

outstanding miss 의 block address 와 대기 load/store(type·offset·destination) 추적

L1 에서 evict 된 line 을 담는 작은 fully associative cache, conflict miss 감소

최근 way 를 먼저 읽어 set associative cache 의 bandwidth·latency 절약

loop 순서 교환으로 spatial, loop 합치기로 temporal locality 개선

tile 단위 계산으로 cache 에 올린 data 를 반복 사용

used prefetches / sent prefetches

너무 이르면 evict, 너무 늦으면 latency 를 다 못 숨김

prefetch data 가 유용한 demand data 를 밀어내는 현상

register 로 regular load vs cache 로 특수 instruction

4.1early restart 와 critical word first 의 차이는?

4.2MSHR 에 같은 block 의 miss 가 또 오면?

4.3victim cache 가 set associative L1 에서 덜 유용한 이유는?

4.4loop fusion 이 개선하는 locality 는?

4.5잘못된 prefetch 가 correctness 에 영향이 없는 이유는?

4.6binding prefetch 의 단점 두 가지는?