A cache block reuse prediction scheme

We introduce a novel approach to predict whether a block should be allocated in the cache or not upon a miss based on past reuse behavior during its lifetime in the cache. It introduces a new reuse model that makes a single-entry bypass buffer suffice to exploit the spatial locality in non-allocated blocks. It also applies classical two-level branch prediction to the reuse history patterns to predict whether the block should be allocated or not. Our evaluation of the scheme, based on five benchmarks from SPEC'95 and a set of six multimedia and database applications, shows that the prediction accuracy is between 66 and 94% across the applications and can result in a miss rate reduction of between 1 and 32% with an average of 12% (using the ideal implementation). We also consider cost/performance aspects of several implementations of the scheme. We find that with a modest hardware cost—essentially a table of about 300 bytes—miss rate can be cut by up to 14% compared to a cache with an always-allocate strategy.