Advanced Lease Caching

Since the dawn of computing, CPU performance has continually grown, buoyed by Moore\u27s Law. Execution speed for parallelizable programs in particular has massively increased with the now widespread employment of GPUs, TPUs, and FPGAs, capable of preforming hundreds of computations simultaneously, for data processing. A major bottleneck for further performance increases, which has impeded speedup of sequential programming in particular, is the processor memory performance gap. One of the approaches to address this block is improving cache management algorithms. Caching is transparent to software, but traditional caching algorithms forgo hardware-software collaboration. Previous work introduced the idea of assigning leases to cache blocks as a form of collaborative cache eviction policy and introduced two lease-caching algorithms, Compiler Lease of cAche Memory (CLAM) and Phased Reference Leasing (PRL), evaluating them over 7 benchmarks from the Polybench benchmark suite. This work evaluates CLAM and PRL over all thirty benchmarks of the Polybench suite for multiple dataset sizes. Additionally, to address the flaws CLAM and PRL, two new lease-caching algorithms have been developed: Scoped Hooked Eviction Lease (SHEL) and Cross-Scope Eviction Lease (C-SHEL). These algorithms are evaluated not just for a single-level cache, typically found in embedded systems, but also for a multi-level cache as exists in more high-performance systems including multi-core CPUs. The test system uses a RISCV architecture to run benchmarks. All four lease caching algorithms outperform the baseline Pseudo Least Recently Used (PLRU) policy at both levels of the cache hierarchy. Further, SHEL and C-SHEL display significant performance increases over PRL for certain benchmarks, demonstrating the value of scoped leasing in addressing complex reuse interval (RI) behavior