Soowon You  Donghee Lee

10.5626/JOK.2024.51.10.849

cache replacement policy memory and computation overheads region mapping policy LRU CLOCK 2Q ARC

Cache has been widely used to improve performance in systems with fast and slow devices. Various cache replacement policies have been studied, but these policies often come with computation and memory overheads. Unfortunately, many studies do not consider these overheads seriously and instead evaluate cache replacement policies based solely on cache hit rate. However, in modern computer systems, cache sizes are constantly increasing, making these overheads more significant. In order to provide a more comprehensive evaluation of cache replacement policies, we aim to consider both overheads and hit rates. In this study, we analyze the memory and computational overheads of popular cache replacement policies such as LRU, CLOCK, 2Q, ARC, and RAND. Additionally, we propose the Region Mapping (RM) policy, which has low memory and computational overheads. Furthermore, we introduce the RM2 policy, which improves hit rates by separating hot and cold data. Our experimental results show that the hit rates of the RM and RM2 policies are competitive with state-of-the-art policies. Moreover, policies with low memory overheads can reduce overall data access time by caching more data within a given cache size.