14. Cache (2)
Cache miss의 종류
Compulsory miss (cold miss)
초반에는 아직 캐시가 비어있기 때문에, 아무것도 없어서 무조건 Miss가 남. B가 클수록 덜 생김. prefetch하면 덜 생김.
Capacity miss
cache 자체가 너무 작아서, working set보다 C가 작아서 생기는 miss. locality를 충분히 활용하지 못함.
Conflict miss
a가 너무 작아서, C/B가 작은 경우 여러개의 주소가 하나의 캐시라인을 쓰기 때문에 발생. a를 늘려야한다.
Cache Write Issue
write는 성능에 영향을 많이 주진 않지만, hit miss 파악 위해 tag부터 봐야함.
보통은 tag와 data는 분리되어있음.
- tag와 data는 read에서는 빨리 봐야하나 (load는 blocking)
- write에서는 tag만 보고 데이터는 나중에 봐도됨. power 줄이기 위함.
또, 데이터 저장 시에는 line read가 한번 필요하다. (보통 워드 단위로 쓰는데, 실제 저장해야하는건 캐시 라인 전체라서, 한번 데이터를 로드한 후 modify해서 다시 저장해야함)
Store Buffer
store 자체가 오래 걸린다면. structural hazard stall occurs!
cache의 data update는 좀 미룰 수 있다.
다음 data bank cycle까지 조금 기다렸다가…
→ load는 store buffer를 먼저 확인해야한다. (RAW dependency)
Blocking vs Non-blocking miss
Blocking miss
Cache miss를 해결하는 중간에는 cache에 오는 명령어 모두 막아버림.
non-blocking miss
Cache miss를 해결하는 중간에도 만약 다른 주소에 해당하는 메모리 명령어가 들어오면 실행을 허용.
그러나 OoO로 경쟁하는 경우에는 의존성을 꼭 확인해야함.
→ In-order에도 유용한데, 이는 SWD끼리는 더 이상 stall하지 않아도 되기 때문임.
MSHR (Miss status handling register)
이걸로 non-blocking을 만들 수 있지.
→ Each entry keeps track of status of outstanding memory requests to a cache miss being serviced.
- Primary miss: miss to cache line
- Secondary miss: Miss to cache line, while primary
- Structural miss: All MSHR being used
(1) Miss 발생 시, 한 엔트리를 할당 시켜
(2) 다른 명령어에 의해 또 파이프라인이 stall되는 것을 막는다.
(3) 새로운 cache miss가 발생하면 일단 MSHR 확인
- 매치되면, 어차피 서비스 될것을 안다.
- miss난 모든 것들이 완료되면 자기가 해결되었다는 것을 안다.
→ 어디에 miss 대기열을 만들어 놨다가 한번에 miss 해결하기.
Write hit policy
Write-through
정의: L_i에서 write hit이 나면 L_i+1에도 같이 쓴다.
⇒ 하위 계층의 캐시에 값을 업데이트 해준다.
장점
- Simple policy
- Search can be done only by looking at the lower-level hierarchy.
- Eviction을 할 때에도 굳이 아래 계층에 적어줄 필요 없이 그냥 사라지면 된다.
단점
- 고성능 프로세서에 불리.
- 3.6GHz, IPC = 2, 10% store → 사이클 당 0.2개의 write. 초당 0.72G*4Byte ⇒ 2.88GB/sec 을 write해야함
- L1, L2는 어떻게 하더라도, n개의 멀티코어인 경우에는 n배의 L2-L3 캐시간의 bandwidth가 필요해짐
Write-back
Write-hit, Li만 업데이트하고 Dirty mark 남기기
Later replacement 전까지는 캐시에만 쓰다가, Li+1에 갔다 쓰기.
좀더 하위 캐시들에게 적은 bandwidth를 요구한다.
Dirty bits (= 밑의 캐시에 없을 수도 있다!)
- dirty하지 않으면, 그냥 위에만 날리면 됨.
단점
- IO나 다른 코어는 L3만 보면 안되고, L1,L2까지 봐야하는 단점이 있다. (search 비용 증가)
Write-Miss Policy
Write-allocate
- Li+1에서 찾았으면 올린다. (load는 금방 쓸테니까 ok, store는 굳이 싶음). 즉 메모리 write에서도 로드한다.
- Write-back에서 더 적절함.
- 자주 쓰는 데이터라고 해도 메모리에 매번 안 내려놨기 때문에, 나중에 한꺼번에 메모리에 write하면 되니까 상관없음.
- write-thorugh였다면 올려봤자 어차피 매번 아래 계층으로 다시 쓸건데.. (bandwidth 낭비)
- Allocate하면 히트 시 아래에 쓰고, 미스 시 위로 다 올려 쓴다는 얘기인데 캐시를 쓰는 의미가 없어지며 write-through의 단점인 bandwidth 문제를 심화시킨다.
- locality가 있는 경우 유리하다.
Write-no-allocate
- Li에서 찾았다고 해도 굳이 위로 올려 쓰지 않는다.
- Write-through와 더 잘 맞음
- 밑에서 write를 해줘야하니까, 이건 write-through가 되어야함.
보통 Unified는 L2~L3부터, I/D split은 L1 수준에서 진행함
Multi-level Caches
caches are multi-leveled!
Inclusive Cache
상위 캐시에 있는 값은 무조건 하위 캐시에 그대로 있음.
외부 장치는 하위 캐시만 찾아보면 최신값 보장 받음. L1까지 올라갈 필요 없음.
How to test my cache?
C, B, a 를 대략적으로 알아내는 방법!
Capacity (C) 알아내기
- C를 2-power 수라고 가정.
- 2^n 승의 buffer를 선언하고, 해당 버퍼에 있는 메모리를 모두 읽는다. R 크기를 증가시키면서 이를 반복.
- Cache capacity를 R이 초과하는 시점, 레벨이 하위로 넘어가는 시점부터 시간이 jump하는 구간이 발생 → 각 캐시의 capacity로 추정하는 방식
Block size (B) 알아내기
여기서 S는 stride임.
- C의 배수인 buffer를 선언.
- S를 증가시켜서, S번째 메모리 위치를 모두 읽고 이를 반복.
- R>C이기 때문에 각 block의 첫 접근은 모두 miss가 남.
- S≥B 이면, 우리는 각 cache block마다 하나의 word만 씀. (매번 새로운 block임)
- S<B이면, 우리는 평균 메모리 값이 증가힌 것을 확인할 수 있음. 캐시 block miss마다 더 많은 word를 읽기 떄문. (같은 block안에 있다면 hit 발생)
associativity (a) 알아내기
- R을 C의 배수에 따라 늘린다. C번쨰 메모리 위치를 읽는다.
- 모든 R/C referenced 주소는 같은 집합에 묶인다.
- a ≥ R/C 라면, 같은 set에 묶일 것이기 때문에 hit이 많이 난다.
- a<R/C라면 다른 set에 매핑되기 떄문에 miss난다.