[HPCA 2012] Decoupled Dynamic Cache Segmentation

LLC(Last Level Cache)는 temporal locality가 낮다는 특징에서 출발하여, LLC에서는 temporal locality에 좋은 성능을 보이는 LRU보다 다른 접근 방법이 필요하다는 관점에서 출발한다.

cache set에 있는 block 들을 referenced list, non-referenced list 2개로 나눠서 predictor 를 통해 way 를 2개의 list로 나누고 replacement 가 일어날때 마다 predictor와 현재 list에 있는 way의 수를 비교해서 predictor보다 많은 way를 가지는 list에서 victim 을 선정한다.

thrashing, scan resistant한 특성을 가지며 predictor를 통해 bypass 또한 가능하다고 한다.

set dueling 방식을 사용하였고 DIP, RRIP, Pacman 등과 달리 3개의 leader sets 을 통해 총 5가지의 segmentation size 중에 하나를 고르게 했다.

논문 제목이 decoupled 인 이유는 replacement 알고리즘과 관계없이 cache를 2가지 list로 잘 segmentation 하면, 어떤 replacement 알고리즘을 사용하더라도 좋은 성능을 보일 수 있다고 하는 것이다.

실제로 실험에서는 SPEC CPU2006 벤치마크를 통해 DCS(Dynamic Cache Segmentation) 기반 NRU 또는 DCS 기반 random replacement 가 LRU보다 좋은 성능을 가짐을 보였다.

hardware overhead 측면에서는 DCS를 위해 cache의 각 line 마다 referenced list 인지 non-referenced list인지 구분하기 위한 1 bit가 필요하고, set dueling을 위해 counter 1개 만 있으면 되므로 overhead도 작았다.
특히, random replacement 를 사용할 경우 hardware overhead도 적으면서 LRU보다 좋은 성능을 보여줄 수 있는 장점이 있다.