Cache Memory and Replacement Algorithm Implementation and Performance Comparison (캐시 메모리와 교체 정책 구현 및 성능의 비교)

Park Naeun (박나은); Jong Wan Kim (김종완); Jeong,Tae-Seog (정태석)

doi:10.9708/jksci.2020.25.03.011

Cache Memory and Replacement Algorithm Implementation and Performance Comparison

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2020, 25(3), pp.11-17
DOI : 10.9708/jksci.2020.25.03.011
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science
Received : March 5, 2020
Accepted : March 26, 2020
Published : March 31, 2020

Park Naeun ¹, Jong Wan Kim ², Jeong,Tae-Seog ²

¹성신여자대학교
²삼육대학교

Accredited

ABSTRACT

In this paper, we propose practical results for cache replacement policy by measuring cache hit and search time for each replacement algorithm through cache simulation. Thus, the structure of each cache memory and the four types of alternative policies of FIFO, LFU, LRU and Random were implemented in software to analyze the characteristics of each technique. The paper experiment showed that the LRU algorithm showed hit rate and search time of 36.044% and 577.936ns in uniform distribution, 45.636% and 504.692ns in deflection distribution, while the FIFO algorithm showed similar performance to the LRU algorithm at 36.078% and 554.772ns in even distribution and 45.662% and 489.574ns in bias distribution. Then LFU followed, Random algorithm was measured at 30.042% and 622.866ns at even distribution, 36.36% at deflection distribution and 553.878ns at lowest performance. The LRU replacement method commonly used in cache memory has the complexity of implementation, but it is the most efficient alternative to conventional alternative algorithms, indicating that it is a reasonable alternative method considering the reference information of data.

KEYWORDS

Cache Replacement, LRU, LFU, FIFO, Random Replacement

Citation status

* References for papers published after 2023 are currently being built.

[book] Jongjung Woo / 2014 / Computer Architecture / Hanbit Academy

[journal] 고정국 / 2012 / Design and Implementation of a Web-based Simulator for Educating Page Replacement Algorithms / 멀티미디어학회논문지 / 한국멀티미디어학회 15(4) : 552~559

[journal] 손창권 / 2017 / An Exploratory Study on the Effects of Reference Locality on Page Replacement Performance / 한국정보기술학회논문지 / 한국정보기술학회 15(9) : 37~47

[confproc] Mikyung Lee / 2014 / SWSC(Sequential Write Spatial Clock) Buffer Replacement Algorithm For Mobile Flash Storage / Proceedings of the Korea Information Processing Society Conference / Korea Information Processing Society 21(2) : 771~774

[journal] Donghee Lee / 1997 / LRFU : A Block Replacement Policy which exploits Infinite History of References / Journal of KISS(A) : Computer Systems and Theory / The Korean Institute of Information Scientists and Engineers 24(7) : 632~641

[journal] Seunghoon Lee / 2000 / Memory Reference Patterns and Page Replacement Policies / Journal of The Korean Institute of Information Scientists and Engineers / The Korean Institute of Information Scientists and Engineers 27(2) : 50~52

[journal] Jae-Seung Ko / 1996 / An Alternative Scheme to LRU for Efficient Page Replacement / Journal of KISS(A) : Computer Systems and Theory / The Korean Institute of Information Scientists and Engineers 23(5) : 478~486

[journal] JongIck Lee / 1996 / The Performance Comparison of the True-LRU and the Pseudo-LRU Algorithm in Cache Memory / Journal of KISS(A): Computer Systems and Theory / The Korean Institute of Information Scientists and Engineers 23(11) : 1148~1160

[confproc] Seon Kim / 2010 / Buffer Cache Block Replacement Algorithm Based on LRU and Prefetching / Journal of The Korean Institute of Information Scientists and Engineers / The Korean Institute of Informativon Scienti sts and Engineers 37(2) : 298~303

[confproc] Hyoil Lee / 1999 / Performance Analysis of Replacement Policies for Internet Proxy Cache / Journal of The 1999 Fall Conference of The Korea Society For Simulation / The Korea Society For Simulation : 138~143

[confproc] Jungmin Yoo / 2013 / Performance comparison of Cache replacement policy in Named Data Network / Proceedings of Symposium of the Korean Institute of communications and Information Sciences (Fall) / Korea Institute Of Communication Sciences : 7~8

[journal] 정도영 / 2013 / Cache Replacement Policy Based on Dynamic Counterfor High Performance Processor / 전자공학회논문지 / 대한전자공학회 50(4) : 52~58

[thesis] Duk Jun Bang / 2015 / An Adaptive Cache Replacement Policy to Evict Dirty Block for Last-Level-Cache / The Graduate School Sejong University

[book] Inkook Chun / 2019 / Easily written data structure in C language / Saengneung Publisher

[web] Microsoft docs / C/C++ Compiler and build tools errors and warnings / https://docs.microsoft.com

This paper was written with support from the National Research Foundation of Korea.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

Cache Memory and Replacement Algorithm Implementation and Performance Comparison

ABSTRACT

KEYWORDS

Citation status

* References for papers published after 2023 are currently being built.

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

Cache Memory and Replacement Algorithm Implementation and Performance Comparison

ABSTRACT

KEYWORDS

Statistics

Tools

Issue List

Citation status

KCI Citation Counts (1)

REFERENCES (15) * References for papers published after 2023 are currently being built.

Search PDF

Citation

* References for papers published after 2023 are currently being built.