SF-LRU cache replacement algorithm

Jaafar Alghazo, Adil Akaaboune, Nazeih Botros

Research output: Contribution to journalConference articlepeer-review

47 Scopus citations

Abstract

In this paper we propose a novel replacement algorithm, SF-LRU (Second Chance-Frequency - Least Recently Used) that combines the LRU (Least Recently Used) and the LFU (Least Frequently Used) using the second chance concept. A comprehensive comparison is made between our algorithm and both LRU and LFU algorithms. Experimental results show that the SF-LRU significantly reduces the number of cache misses compared the other two algorithms. Simulation results show that our algorithm can provide a maximum value of approximately 6.3% improvement in the miss ratio over the LRU algorithm in data cache and approximately 9.3% improvement in miss ratio in instruction cache. This performance improvement is attributed to the fact that our algorithm provides a second chance to the block that may be deleted according to LRU's rules. This is done by comparing the frequency of the block with the block next to it in the set.

Original languageEnglish (US)
Pages (from-to)19-24
Number of pages6
JournalRecords of the IEEE International Workshop on Memory Technology, Design and Testing
DOIs
StatePublished - 2004
Externally publishedYes
EventRecords of the 2004 International Workshop on Memory Technology, Design and Testing, MTDT 2004 - San Jose, CA, United States
Duration: Aug 9 2004Aug 10 2004

Keywords

  • LFU
  • Low Power Cache
  • LRU
  • Replacement

Fingerprint

Dive into the research topics of 'SF-LRU cache replacement algorithm'. Together they form a unique fingerprint.

Cite this