SF-LRU cache replacement algorithm

Jaafar Alghazo; Adil Akaaboune; Nazeih Botros

doi:10.1109/MTDT.2004.1327979

SF-LRU cache replacement algorithm

Jaafar Alghazo, Adil Akaaboune, Nazeih Botros

Research output: Contribution to journal › Conference article › peer-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 language	English (US)
Pages (from-to)	19-24
Number of pages	6
Journal	Records of the IEEE International Workshop on Memory Technology, Design and Testing
DOIs	https://doi.org/10.1109/MTDT.2004.1327979
State	Published - 2004
Externally published	Yes
Event	Records of the 2004 International Workshop on Memory Technology, Design and Testing, MTDT 2004 - San Jose, CA, United States Duration: Aug 9 2004 → Aug 10 2004

Keywords

LFU
Low Power Cache
LRU
Replacement

Publisher link

10.1109/MTDT.2004.1327979

Find It

Find It at U of M Libraries

Cite this

@article{3f5b55c1523b4d6dbcb0a7d0ffb0ac0a,

title = "SF-LRU cache replacement algorithm",

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.",

keywords = "LFU, Low Power Cache, LRU, Replacement",

author = "Jaafar Alghazo and Adil Akaaboune and Nazeih Botros",

year = "2004",

doi = "10.1109/MTDT.2004.1327979",

language = "English (US)",

pages = "19--24",

journal = "Records of the IEEE International Workshop on Memory Technology, Design and Testing",

issn = "1087-4852",

publisher = "IEEE Computer Society",

note = "Records of the 2004 International Workshop on Memory Technology, Design and Testing, MTDT 2004 ; Conference date: 09-08-2004 Through 10-08-2004",

}

TY - JOUR

T1 - SF-LRU cache replacement algorithm

AU - Alghazo, Jaafar

AU - Akaaboune, Adil

AU - Botros, Nazeih

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - LFU

KW - Low Power Cache

KW - LRU

KW - Replacement

UR - http://www.scopus.com/inward/record.url?scp=10044286074&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10044286074&partnerID=8YFLogxK

U2 - 10.1109/MTDT.2004.1327979

DO - 10.1109/MTDT.2004.1327979

M3 - Conference article

AN - SCOPUS:10044286074

SN - 1087-4852

SP - 19

EP - 24

JO - Records of the IEEE International Workshop on Memory Technology, Design and Testing

JF - Records of the IEEE International Workshop on Memory Technology, Design and Testing

T2 - Records of the 2004 International Workshop on Memory Technology, Design and Testing, MTDT 2004

Y2 - 9 August 2004 through 10 August 2004

ER -

SF-LRU cache replacement algorithm

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this