Dueling CLOCK: Adaptive cache replacement policy based on the CLOCK algorithm. Janapsatya, A., Ignjatovic, A., Peddersen, J., & Parameswaran, S. In Design, Automation Test in Europe Conference Exhibition (DATE), 2010, pages 920-925, March, 2010.
doi  abstract   bibtex   
We consider the problem of on-chip L2 cache management and replacement policies. We propose a new adaptive cache replacement policy, called Dueling CLOCK (DC), that has several advantages over the Least Recently Used (LRU) cache replacement policy. LRU's strength is that it keeps track of the 'recency' information of memory accesses. However, a) LRU has a high overhead cost of moving cache blocks into the most recently used position each time a cache block is accessed; b) LRU does not exploit 'frequency' information of memory accesses; and, c) LRU is prone to cache pollution when a sequence of single-use memory accesses that are larger than the cache size is fetched from memory (i.e., it is non scan resistant). The DC policy was developed to have low overhead cost, to capture 'recency' information in memory accesses, to exploit the 'frequency' pattern of memory accesses and to be scan resistant. In this paper, we propose a hardware implementation of the CLOCK algorithm for use within an on-chip cache controller to ensure low overhead cost. We then present the DC policy, which is an adaptive replacement policy that alternates between the CLOCK algorithm and the scan resistant version of the CLOCK algorithm. We present experimental results showing the MPKI (Misses per thousand instructions) comparison of DC against existing replacement policies, such as LRU. The results for an 8-way 1MB L2 cache show that DC can lower the MPKI of SPEC CPU2000 benchmark by an average of 10.6% when compared to the tree based Pseudo-LRU cache replacement policy.
@inproceedings{ 5456920,
  author = {Janapsatya, A. and Ignjatovic, A. and Peddersen, J. and Parameswaran, S.},
  booktitle = {Design, Automation Test in Europe Conference Exhibition (DATE), 2010},
  title = {Dueling CLOCK: Adaptive cache replacement policy based on the CLOCK algorithm},
  year = {2010},
  month = {March},
  pages = {920-925},
  abstract = {We consider the problem of on-chip L2 cache management and replacement policies. We propose a new adaptive cache replacement policy, called Dueling CLOCK (DC), that has several advantages over the Least Recently Used (LRU) cache replacement policy. LRU's strength is that it keeps track of the 'recency' information of memory accesses. However, a) LRU has a high overhead cost of moving cache blocks into the most recently used position each time a cache block is accessed; b) LRU does not exploit 'frequency' information of memory accesses; and, c) LRU is prone to cache pollution when a sequence of single-use memory accesses that are larger than the cache size is fetched from memory (i.e., it is non scan resistant). The DC policy was developed to have low overhead cost, to capture 'recency' information in memory accesses, to exploit the 'frequency' pattern of memory accesses and to be scan resistant. In this paper, we propose a hardware implementation of the CLOCK algorithm for use within an on-chip cache controller to ensure low overhead cost. We then present the DC policy, which is an adaptive replacement policy that alternates between the CLOCK algorithm and the scan resistant version of the CLOCK algorithm. We present experimental results showing the MPKI (Misses per thousand instructions) comparison of DC against existing replacement policies, such as LRU. The results for an 8-way 1MB L2 cache show that DC can lower the MPKI of SPEC CPU2000 benchmark by an average of 10.6% when compared to the tree based Pseudo-LRU cache replacement policy.},
  keywords = {cache storage;storage management chips;CLOCK algorithm;SPEC CPU2000 benchmark;adaptive cache replacement policy;dueling CLOCK;least recently used cache replacement policy;misses per thousand instructions;on-chip L2 cache management;single use memory accesses;Australia;Clocks;Computer science;Costs;DC generators;Delay;Engineering management;Frequency;Hardware;Pollution},
  doi = {10.1109/DATE.2010.5456920},
  issn = {1530-1591}
}
Downloads: 0