Hierarchy-aware Replacement for Inclusive Last-level Caches

Patent Status: 

Patent Filed

Indian Patent Applicaton No: 

13/722,607

Overview: 

Proposes online algorithms to decide which cache blocks should be prioritized in the last level of an inclusive cache hierarchy for replacement so that with high probability these blocks are dead in the near-future.

Key Features: 

  • The online algorithm dynamically partitions the cache blocks into a few categories based on the reuse pattern exhibited by a cache block in the private caches of a chip-multiprocessor with a shared last-level inclusive cache.
  • For each cache block category, the algorithm estimates the overall reuse probability of the blocks belonging to that category. This is done by sampling a few cache sets and observing the reuse behaviour of the blocks that map to these sets. The observation is done only when a block is evicted from the inner level of the hierarchy so that the complete behaviour of the block can be incorporated to compute the reuse probability. The sample sets serve as the reference for learning the reuse behaviour in an online fashion.
  • The non-sampled sets use the reuse probability estimates of each cache block category to decide the replacement priority of a block in the last level of the cache hierarchy.

Applications: 

  • Efficient management of a multi-level cache hierarchy in chip-multiprocessors.

Contact us

Search form

Connect with us

Follow us