2 Motivation
Miss analysis on workload
캐시 시스템이 locality를 잘 활용하고, prefetcher가 효과적으로 load를 줄인다면, 어플리케이션을 실행했을 때 cache level이 높아질수록 load miss의 수가 많이 줄어들어야 한다.
Figure 3의 (a)는 기존 캐시 시스템이 잘 동작하는 예시인데, L1 -> L2 -> L3로 갈수록 miss의 수가 x3, x2배 줄어든다. 반면 나머지 5개의 workload들은 기존의 level-wise sequential한 캐시 접근이 비효율적인 여러 가지 상황을 보여준다. (b)의 경우는 L2 cache가 miss를 낮추지 못하므로 비효율적이며, L3도 L2에 비해 miss를 많이 낮추지는 못한다. (c)의 경우는 L3가 L2와 miss 수가 비슷하므로 비효율적으로 동작하고 있다. (d)와 같이 random access pattern을 가지는 경우는 이 문제가 더 심해진다. (e)는 simple access pattern을 가지는데, 그럼에도 miss의 수가 모든 level에서 높다고 되어 있다. (그런데 miss의 수가 높다는 것은 상대적이기에 뭔가 비교 대상이 있어야 할 것 같다) (f)는 특정 phase에 L2가 비효율적이었다가 또 다른 phase에는 효과적으로 동작한다.
Prefetcher
Prefetcher는 memory request가 오기 전에 미리 higher level에서 fetch 함으로써 miss rate을 줄이는 방식이다. Figure 4를 보면 기존 prefetcher들은 최대 약 50%의 coverage를 가지고, 이는 나머지 절반 이상은 off-chip으로 간다는 것이다. 또한 accuracy는 50~60%인데, 이는 나머지는 불필요한 prefetch로 potentially negative impact를 가져올 수 있다.
3 Level Prediction uArchitecture
여기서는 메모리 요청 명령어가 어느 level에 존재할지를 예측함으로써 dynamic 하게 unnecessary cache-level lookup을 생략하는 방법을 제안한다.
3.1 Design Consideration
4개의 계층 L1, L2, L3, main memory 중 L1은 예측 대상에서 제외한다. 왜냐하면 L1 캐시는 virtually indexed이기 때문에 L1 skip을 위해 physical address를 활용할 수 없다. 또한 core pipeline와 밀접하게 연관이 되어 있으므로 timing, design을 건들지 않기 위함이다.
기존의 hit/miss predictor를 stack하여 사용할 수 없는 하나의 이유는 prefetcher의 영향을 제대로 반영하지 못하기 때문인데, PC-indexed, address-indexed에서 prefetcher가 noise로서 작용하여 정확도를 떨어뜨린다. Level predictor의 경우 prefetcher의 동작 역시 포함시킬 수 있는데, prefetcher가 동작할 때 level predictor를 업데이트하도록 할 수 있다.
3.2 LP (Level Predictor) uArchitecture
각 block마다 location map (LocMap)을 가지고 있고, 2-bit으로 표현된다. (L2, L3, MEM 중 하나를 나타내므로) LocMap은 in-memory table로 구현하며, L2 level에서 접근될 수 있는 small metadata cache에 caching 된다. Metadata cache의 용량이 작고 LocMap을 접근하는 것은 latency가 길기 때문에, metadata cache miss 시에 예측에 활용할 history-based Popular Level Detector를 두며 이는 3개의 counter로 이루어져 있다.
LP는 4개의 정보를 활용하며, 이는 L2의 fill, eviction, L3의 fill, eviction이다. 이 정보가 결국 off-chip LocMap까지 도달하게 된다.
3.3 LocMap and Location Tracking
LocMap은 system-reserved physical memory에 존재하는 table이고, 캐시 block(=64B의 크기)마다 2-bit의 metadata로 location 정보를 표현한다. (L2, L3, main mem 중 하나)
Access
LocMap은 매 L1 cache miss와 LocMap 업데이트 시에 접근된다. 접근 주소를 얻는 detail은 다음과 같다. Table의 base address는 OS에 의해 정해지고, 메모리 접근 granularity는 64B 이다. Data 64B 당 2-bit metadata를 가지므로, 64B의 metadata에 해당되는 data는 64B * 2^8 = 2^16 B 이다. 따라서, memory request에 해당하는 physical address를 2^14로 나누어주면 block offset을 얻을 수 있고, 이를 base address에 더해서 접근할 주소를 얻는다.
Update
LP predictor의 정확성과 power efficiency를 동시에 고려해야 하기 때문에, 특정 event가 일어났을 때만 update 한다. Demand cache fill, dirty eviction, prefetch fill (metadata cache hit인 경우에 한해)에 대해서만 update 한다.
Metadata cache miss 시의 prefetch fill은 추가적인 traffic을 발생시키기 때문에 업데이트하지 않기로 한다. Clean eviction 역시 그러하다. Cache coherence protocol을 변경하지 않기 위해 coherence에 의한 level 변경 시에도 업데이트하지 않는다.
Metadata Cache
Metadata cache의 크기가 너무 작으면 miss ratio가 높아져 off-chip request가 증가하고, LocMap에 비해 덜 정확한 Popular Level Detector에 의존하게 되므로 정확도도 낮아진다. 동시에 latency와 energy 제한 요소도 있기 때문에 너무 커져서도 안 된다. 이것은 experiment를 통해 accuracy, energy의 tradeoff를 고려하여 2KB, 2-way set associative cache로 설정하였다.
3.4 Popular Levels Detector
요청한 데이터에 대한 location 2-bit이 metadata cache에 caching 되어 있지 않다면, LocMap entry가 도달할 때까지 기다리면 latency가 너무 길어지기 때문에 Popular Levels Detector를 통해 예측한다. 이것은 L2, L3, main memory 3개의 memory hierarchy 각각에 대한 recent access counter로서, 접근될 때마다 1씩 증가하고 접근되지 않은 것들은 1씩 감소한다. 예측 시에는 threshold와 적절히 비교해 1개 또는 여러 개의 level을 예측하고, 여러 개의 level을 예측한 경우에는 parallel 하게 접근한다.
3.5 Misprediction Detection and Recovery
L3에 접근해야 할 것을 L2로 예측하는 것과 같이 더 낮은 level로 잘못 예측하는 것은 correctness(=functionality)와 관련해 추가적으로 고려할 것이 없다. 다른 일반적인 miss와 마찬가지로 나머지 hierarchy들을 순차적으로 접근해 데이터를 얻어올 것이기 때문이다.
그러나 더 높은 level로 잘못 예측하면 이미 더 낮은 level을 bypass한 상태이므로 이 경우는 functionality를 추가적으로 고려해야 한다. Directory controller를 사용하는데, directory는 원래 LLC level에 존재하여 data block의 cache coherency를 보장하는 역할을 한다. 대부분의 프로세서에서 directory는 LLC tag와 함께 저장되어 있으므로, 여기서는 LLC hit 여부를 판단하면서 동시에 directory를 확인함으로써 L2 misprediction 여부를 확인하게 된다. L2 bypass를 할 때, main memory를 예측했을 때는 모두 directory를 확인하여 misprediction을 검사하는 것이다.
4 Evaluation Methodology
Simulated Systems
시뮬레이터는 gem5를 사용하였다. L1, L2 캐시는 tag, data를 parallel 하게 접근 가능, L3 캐시는 tag -> data 순으로 순차적으로 접근 가능한 구조이다.
비교 대상은 prefetcher만을 사용하는 Baseline, hit/miss predictor의 stack으로 level prediction을 하도록 만든 것, TLB entry에 location을 저장하는 D2D, miss penalty가 없는 ideal이다.
Benchmarks
SPEC, GAPBS, NAS를 사용하였다.
5 Evaluation Results
Single-Core Performance
LP는 D2D, ideal에 준하는 speedup(=IPC)을 달성하고, hit/miss predictor의 stack보다 우수한 성능을 보인다. 또한, Figure7, 8은 서로 다른 정도의 prefetcher를 사용한 차이가 있는데, LP는 prefetcher의 변화에 대해서도 speedup이 robust 하다.
Prediction Accuracy
Figure 12를 보면 sequential, skip으로 올바르게 예측한 것이 거의 90% 이상으로, prediction이 잘 동작하는 것을 알 수 있다.
Figure 13에서 보면 낮은 accuracy가 metadata cache miss rate과는 큰 상관이 없다. 대신 이것은 LocMap 정보의 stale 때문인데, 잦은 prefetch는 LocMap을 업데이트 하지 않도록 했기 때문이다.
또한 이 Figure 13은 PLD (Popular Level Detector)도 어느 정도 정확도를 보장함을 보여주는데, LP cache miss rate이 높은 경우도 level prediction 정확도가 높게 유지될 수 있었기 때문이다.
