Bypass and Insertion Algorithms for Exclusive Last-Level Caches

Patent Status: 

Patent Filed

US Patent No: 

13/078,415

Overview: 

Proposes online algorithms to decide which cache blocks should not be allocated [bypassed] in the cache and the relative importance of the allocated blocks at the time of insertion in the cache in the exclusive last level of a multi-level cache hierarchy.

Key Features: 

  • The online algorithm dynamically partitions the cache blocks into a few categories based on the use count and the number of trips a cache block makes between the last two levels of the cache hierarchy in a chip-multiprocessor with a shared last-level exclusive cache.
  • For each cache block category, the algorithm estimates the volume of the dead and the live blocks within the category. This is done by mining the eviction stream coming from the inner-level of the cache hierarchy.
  • The relative volumes of the dead and live blocks in each cache block category are used to decide the set of the blocks to be bypassed and the insertion order of the non-bypassed blocks.

Applications: 

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

Contact us

Search form

Connect with us

Follow us