HyVE: A Hybrid Voting-based Eviction Policy for Caches

In computer architecture, caches enable low-latency memory accesses, but are limited in capacity. This makes efficient cache data management strategies critical for good system performance. Standalone eviction policies (LRU, LFU, LIP, etc.) usually optimize for a single eviction criterion (recency, frequency, etc.), which suit applications with trivial memory access patterns. Modern day applications are growing in both number and complexity. Even within a single application, there are certain phases that exhibit contrasting memory access patterns. On many core systems, multiple such applications run on the same platform simultaneously, further diversifying the memory access patterns. Such erratic access patterns can easily disorient an eviction algorithm, resulting in cache pollution/thrashing, subsequently degrading application performance. The challenge is to provide a smart eviction policy, which efficiently manages cache data by optimizing for multiple eviction criteria.

This invention proposes HyVE, a Hybrid Voting-based Eviction Policy that combines multiple eviction policies together and uses concepts from voting theory to decide on an eviction victim. HyVE is a modular framework designed to accommodate an arbitrary number of standalone eviction policies. HyVE is also designed to be flexible, such that the number of eviction policies and the voting methodology can be (re)configured based on application requirements, even at runtime.

These features enable computer architects to configure HyVE with the desired number and/or combination of constituent eviction policies that best suit the computing platform and the applications to be executed. Results show that on average, HyVE reduces cache misses by 7% compared to the LRU policy. HyVE is also evaluated against state-of-the-art set-dueling and learning-based eviction policies.

In particular, HyVE can improve the system performance of multi-processor architectures with a shared last-level cache. Almost any new/existing standalone eviction policy can be incorporated within HyVE with relatively low development and verification effort.

Further, all eviction policies within HyVE operate in parallel, allowing for minimal timing overheads. From a hardware implementation perspective, HyVE’s ranking extensions and voting overheads consume very little resources compared to the standalone eviction policies.

We are looking for license partners who can profitably use the technology in the context of their own microprocessor developments and products.

The concept of HyVE has been extensively verified using simulations. HyVE has also been implemented and verified on a Xilinx Virtex-7 FPGA as part of a cache controller sub-module within a multi-processor platform.