[ISCA 2007] Adaptive Insertion Policy for High Performance Caching

cache replacement algorithm은 보통 LRU 를 사용한다. 하지만 LRU는 cache size 보다 큰 working set 을 가지는 memory intensive workload 들에 의한 thrashing 에 안좋은 성능을 보이는 단점이 있다.

이 논문의 아이디어는 이러한 thrashing 이 발생하는 경우, working set의 일부분이라도 cache에 유지시켜 그 부분에 대해서는 hit 이 날 수 있도록 하고, 나머지 부분에서는 thrashing 발생하도록 하면 어떨까 하는 것이다.

3가지 방법을 제안했다.
LIP(LRU Insertion Policy) 를 통해 새로운 line을 MRU position 대신 LRU position 에 넣어 만약 다시 reference 되지 않으면 cache에서 바로 eviction 될수 있도록 하였다.
하지만 이와 같은 방법으로는 application phase 변화, 즉 프로그램 실행중에 working set 이 변화하는것에 대해 대응하지 못한다.

BIP(Bimodal Insertion Policy)를 통해 모든 새로운 line을 LRU position에 넣는 대신, 일정확률로 MRU position에 넣음으로 써 working set의 변화에 대응 하도록 한다.
하지만 BIP 역시 LRU friendly(LRU에서 잘 동작하는) workload 에 대해 안좋은 성능을 보일 수 가 있다.

그래서 마지막으로 DIP(Dynamic Insertion Policy)를 제안한다. 이는 LRU와 BIP 둘중 하나를 dynamic 하게 골라서 좋은 성능을 보이는 replacement 알고리즘을 사용한다.
둘중 하나를 고르기 위해서는 set dueling 방식을 사용한다.
cache set을 sample로 몇개씩 뽑아서 하나는 LRU, 다른하나는 BIP 방식을 사용하게 하고, counter를 둬서 LRU가 hit 나면 counter++, BIP가 hit나면 counter-- 하는 방식으로 해서, 나머지 set들은 현재의 counter 값에 따라 replacement algorithm을 dynamic 하게 적용한다.

이 페이퍼는 아이디어가 참 간단하면서도 명료했던 것 같다.
뒤늦게 안 사실이지만
(One of the 10 computer architecture papers of 2007 selected as Top Picks by IEEE Micro)
라고 한다.