[MICRO 2006] Utility-Based Cache Partitioning : A Low-Overhead, High-Performance, Runtime Mechanism to Partition Shared Caches

LRU 를 사용하는 shared cache에서는 cache를 많이 요구하는 application 에게 더 많은 cache 를 사용하게 되는 demand based 방식이라 할 수 있다. 하지만 cache를 demand 에 따라 많이 할당하는것이 그에 따라 얻을 수 있는 이익과 correlation이 있다고 볼 수 는 없다. (e.g. streaming application).

이 논문은 demand based 가 아니라 cache를 더 줬을때 많이 이익을 보는 application 에게 cache를 더 할당하자는(utility-based) 방식을 제안한다.

ATD(Auxiliary Tag Directory)를 사용하여 LRU 알고리즘의 stack property를 사용하여 MRC를 구하고 utility 가 가장 높은(miss가 가장 작도록) partition을 dynamic 하게 찾아서 partitioning 한다.

partitioning 하는것은 500M cycles 마다 한다는데 이건 실험적으로 해서 구했다고 함.

페이퍼에서는 utility의 정의를 a-way 에서 b-way로 더 많이 줬을 때 줄어드는 miss의 수로 하고 있다. 

DSS(Dynamic Set Sampling)을 사용하여 ATD의 크기를 줄임으로써 monitoring 을 위한 hardware overhead를 줄이고 speedup, fairness 모두 LRU 보다 좋은 성능을 보였다.

실험에서는 core 2개에 4-way associativity 라서 optimal 한 partition을 찾는 cost가 적은데, core가 많아지고 associativity 가 높아지면 optimal partition 을 찾기가 거의 NP hard 이다.

이러한 scalability 문제를 해결하기 위해 greedy, lookahead algorithm을 통해 approximation을 하였으며, lookahead algorithm의 경우에는 거의 optimal에 가까운 partition을 찾아내서 성능을 보여주었다. 

ps. Yale N.Patt 라는 분이 저자의 advisor인 것 같은데 이 분 페이퍼에는 DSS(Dynamic Set Sampling) 방법이 hardware cost를 줄이기 위해 항상 나오는 것 같다.