Bypass Extended Stack Processing for Anti-Thrashing Replacement in Shared Last Level Cache of Chip Multiprocessors

Young-Sik EOM  Jong Wook KWAK  Seong-Tae JHANG  Chu-Shik JHON  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.2   pp.370-374
Publication Date: 2013/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.370
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Computer System
Keyword: 
last level cache,  stack processing,  replacement policy,  anti-thrashing,  cache partitioning,  chip multi-processors,  

Full Text: PDF>>
Buy this Article




Summary: 
Chip Multiprocessors (CMPs) allow different applications to share LLC (Last Level Cache). Since each application has different cache capacity demand, LLC capacity should be partitioned in accordance with the demands. Existing partitioning algorithms estimate the capacity demand of each core by stack processing considering the LRU (Least Recently Used) replacement policy only. However, anti-thrashing replacement algorithms like BIP (Binary Insertion Policy) and BIP-Bypass emerged to overcome the thrashing problem of LRU replacement policy in a working set greater than the available cache size. Since existing stack processing cannot estimate the capacity demand with anti-thrashing replacement policy, partitioning algorithms also cannot partition cache space with anti-thrashing replacement policy. In this letter, we prove that BIP replacement policy is not feasible to stack processing but BIP-bypass is. We modify stack processing to accommodate BIP-Bypass. In addition, we propose the pipelined hardware of modified stack processing. With this hardware, we can get the success function of the various capacities with anti-thrashing replacement policy and assess the cache capacity of shared cache adequate to each core in real time.