Cache is a basic computer architecture for better performance in modern computer. Though small
size of cache which cannot have all blocks in memory, blocks in cache should be replaced with new blocks from memory. In this kind of view, many cache replacement policies come into the world. The most well-known policy is Least Recently Used (LRU) policy. LRU gives positions to all blocks, moves new or re-referenced block to first position and evicts the last position's block. Tree-based PseudoLRU (PLRU) is similar policy with LRU which uses binary tree to express position. PLRU has better space efficiency than LRU. However, this tree-based system makes unnecessary disturbances to non-referenced blocks in a set. Therefore, we make a Counter-based Pseudo-LRU (CpLRU) which diminishes disturbance of non-referenced blocks. Finally, we propose the Dynamic Pseudo-LRU (DpLRU) which monitors CpLRU and PLRU and chooses better policy.
To make Counter-based Pseudo-LRU, we analyze three methods that could be used on PLRU. The first one is replacement position of new incoming block. Second one is whether to change a bit when there was hit in second quarter of a set. Last is whether to maintain the counter when there was change in counting part. This CpLRU improves MPKI in single thread by 0.07MPKI than LRU and PLRU. Dynamic Pseudo-LRU is made by applying Set Dueling between PLRU and CpLRU. DpLRU shows 0.4MPKI less than PLRU.
캐시는 현대 컴퓨터의 성능을 향상시키는 기본적인 컴퓨터 아키텍처입니다. 메모리의 모든 블록을 가질 수 없는 캐시의 작은 크기 때문에 캐시의 블록을 메모리의 새로운 블록으로 교체해주어야 합니다. 이러한 관점에서 많은 캐시 교체 정책이 나오게 됩니다. 가장 잘 알려진 정책은 LRU (Least Recently Used)입니다. LRU는 모든 블록에 위치를 제공하고 새 블록 또는 다시 참조 된 블록을 첫 번째 위치로 이동시키고 마지막 위치의 블록을 제거합니다. 트리 기반 Pseudo-LRU (PLRU)는 이진 트리를 사용하여 위치를 표현하는 LRU와 유사한 정책입니다. PLRU는 LRU보다 공간 효율성이 좋습니다. 그러나 이 트리 기반 시스템은 셋에서 참조되지 않은 블록에 디스터번스를 만듭니다. 따라서 우리는 참조되지 않은 블록의 디스터번스를 줄이는 Counter-based Pseudo-LRU (CpLRU)를 만들었습니다. 마지막으로 CpLRU와 PLRU를 모니터링하고 더 나은 정책을 선택하는 Dynamic Pseudo-LRU (DpLRU)를 제안합니다.
Counter-based Pseudo-LRU를 만들기 위해 PLRU에서 사용할 수 있는 세 가지 방법을 분석합니다. 첫 번째는 들어오는 새 블록의 교체 위치입니다. 두 번째 것은 세트의 2/4에 맞았을 때 한 비트를 바꿀 지의 여부입니다. 마지막으로 카운터 부분이 변경되었을 때 카운터를 유지할지 여부입니다. 이 CpLRU는 LRU 및 PLRU보다 0.07MPKI만큼 단일 코어에서 MPKI를 향상시킵니다. Dynamic Pseudo-LRU는 PLRU와 CpLRU간에 Set Dueling을 적용하여 만듭니다. DpLRU는 PLRU보다 0.4MPKI정도 더 낮은 miss를 보입니다.
