TY  - JOUR
T1  - Overhead Analyses of Cache Replacement Policies and Region Mapping Replacement Policy
AU  - You, Soowon 
AU  - Lee, Donghee 
JO  - Journal of KIISE, JOK
PY  - 2024
DA  - 2024/1/14
DO  - 10.5626/JOK.2024.51.10.849
KW  - cache replacement policy
KW  - memory and computation overheads
KW  - region mapping policy
KW  - LRU
KW  - CLOCK
KW  - 2Q
KW  - ARC
AB  - 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.