[PACT 2008] Adaptive Insertion Policies for Managing Shared Caches

Adaptive Insertion Policies for High Performance Caching[ISCA 2007] 의 확장판.

[ISCA 2007] 에서는 private cache 환경에서 DIP(Dynamic Insertion Policy) 를 제안.
DIP는 LRU(Least Recently Used) 와 BIP(Bimodal Insertion Policy) 둘중에 하나를 어플리케이션 실행중에 dynamic 하게 선택하는 알고리즘이다.
LRU가 새로운 line을 MRU에 Insertion 하는것인 반면 BIP는 기본적으로 LRU 위치에 Insertion 하고 일정확률로 MRU 위치에 insertion 하는 방법이다.
여기서도 Set Dueling 을 통해서 32개의 set을 각각 LRU, BIP 에게 주어, 잘 동작하는 알고리즘을 나머지 set에 적용시키는 방법을 사용했다.
자세한 내용은 따로 정리 하도록 해야겠다. 읽은지는 좀 됐는데 정리를 안하니 기억이 잘 안난다..ㅠㅠ

Adaptive Insertion Policies for Managing Shared Caches 는 이전의 페이퍼에서 CMP환경의 shared cache 환경을 고려한 확장 버전인듯하다.

페이퍼에서도 기본적으로 DIP을 기반으로 하고 있다고 말하고 있고, thread(core)별로 LRU, BIP 중에 어떤 알고리즘을 사용할지 결정하는 방식으로 역시 Set Dueling 을 사용함.

이름하여 Thread-Aware Dynamic Insertion Policy(TADIP)
core가 많아 질수록 모든 경의 수를 Set Dueling 방법으로 sampling 하는것은 실용적이지 못하다(코어 16개의 경우 2^16=65536가지).
이를 줄이기 위해 TADIP-isolated, TADIP-feedback 두가지 방법을 제안하는데,
isolated 방식은 각 thread(core) 별로 사용할 알고리즘을 결정하기 위해 나머지 코어는 LRU를 사용한다고 가정하는 것이고, feedback은 나머지 core도 이전의 Set Dueling 방법을 통해 선택된 알고리즘을 적용하는 방법이다.
즉, 4개의 core가 있고, 0(LRU), 1(BIP) 라고 할때
core 0번의 Set Dueling Monitor(SDM)은
isolated : (0, 0, 0, 0), (1, 0, 0, 0) 이렇게 되고
feecback : (0, P2, P3, P4), (1, P2, P3, P4) 이렇게 된다.

실험을 통해 throughtput, weighted speedup, fairness 모두 평균적으로 baseline LRU < DIP < TADIP-I < TADIP-F 순으로 성능을 보임.