EFRC is Adapted to Access-rate Imbalance: A Class of Efficient and Fair Replacement Algorithms for Cache Sharing

Co-located workloads demand fine-grained management of caching control for enhanced deterministic performance. Traditionally, minimizing cache interference has relied on hardware mechanisms that offer coarse cache resource allocation across cores or the last-level cache. More often than not, existing cache replacement algorithms aim to optimize cache hit efficiency depending on single workload access characteristics. In this paper, we propose a series of replacement algorithms for multi-workload shared caches, radically enhancing the deterministic performance of co-located workloads. We devise a class of replacement algorithms for cache sharing, referred to as Efficient and Fair Replacement Cache or EFRC. To strick a balance between performance and complexity, we divide the class of algorithms into Type I and Type II according to the data access characteristics. The common idea of our EFRC-I and EFRC-II algorithms is to judiciously adjust resources for a diversity of workloads or data characteristics online by triggering various resource allocation policies through a corresponding ghost cache preceptor. Our extensive experiments unveil that the EFRC-I and EFRC-II algorithms exhibit a handful of advantages. Firstly, the algorithms support multiple workloads sharing cache – and are compatible with single workload scenarios. Secondly, the cache-hit performance of our proposed EFRC-I and EFRC-II algorithms is superior to that of the existing ARC, LIRS, CACHEUS, and SIEVE algorithms in multi-workload shared caches. Importantly, our technique enhances the fairness of co-located workloads. In particular, when access rates of co-located workloads are imbalanced, our method demonstrates clear superiority over the baseline and the aforementioned state-of-the-art algorithms.