Method and system for cache eviction

Abstract

The proposed system and associated algorithm when implemented improves the processor cache miss rates and overall cache efficiency in multi-core environments in which multiple CPU's share a single cache structure (as an example). The cache efficiency will be improved by tracking CPU core loading patterns such as miss rate and minimum cache line load threshold levels. Using this information along with existing cache eviction method such as LRU, results in determining which cache line from which CPU is evicted from the shared cache when a capacity conflict arises. This methodology allows one to dynamically allocate shared cache entries to each core within the socket based on the particular core's frequency of shared cache usage.

1 . A system of cache eviction, said system comprising:
 a multiple core central processing unit; and   a first cache;   wherein said multiple core central processing unit shares a last-level cache;   said first cache line is loaded to a first cache;   a first core among said multiple core central processing unit requests a load in said first cache;   said first core has an identification number;   said first cache line is marked with said identification number of said first core;   a cache load tracker keeps track of counts of cache lines loaded into said first cache for each individual core among said multiple core central processing unit;   when a count of said first core's cache lines loaded into said first cache exceeds a first threshold, all said counts of cache lines loaded into said first cache are reduced for each individual core, proportionally, such that said cache load tracker is not overflowed;   said cache load tracker further measures load rate and miss rate for each individual core;   said cache load tracker records said load rate and said miss rate on separate memory locations;   said cache load tracker takes a running average over a first predetermined number of most recent misses;   said identification number of said first core is stored in a second predetermined number of first-in-first-out queues of first memory locations;   when said first cache is full and all said counts of cache lines loaded into said first cache for each individual core are equal, a least-recently-used cache line corresponding to any core not responsible for said load in said first cache is evicted;   when said count of said first core's cache lines loaded into said first cache exceeds a second threshold or said miss rate for said first core exceeds a third threshold, a least-recently-used cache line corresponding to a core with the largest said count of cache lines loaded into said first cache is evicted; and   when said count of said first core's cache lines loaded into said first cache does not exceed said second threshold and said miss rate for said first core does not exceed said third threshold, a least-recently-used cache line corresponding to a core with the lowest load rate is evicted.