Segmented least recently used cache replacement simulator
Article Sidebar
Published:
May 30, 2025
Keywords:
Block Replacement, Cache Memory, Hit Ratio; SLRU
Section
Computer Science
Statistics Article
Article View : 2 Times
Main Article Content
Abstract
The block replacement process in the memory cache is an essential technique in computing systems to improve the efficiency of data retrieval from high-speed memory. Various caching algorithms have been developed to speed up data retrieval access in the memory cache, including Least Recently Used (LRU), Least Frequently Used (LFU), and First In First Out (FIFO). This study aims to develop a simulator by combining the LRU and LFU methods called Segmented Least Recently Used (SLRU), which is able to process data retrieval from the memory cache more efficiently. Experiments on the simulation program created were carried out on 10 random data groups to determine the effectiveness of each block replacement algorithm. Based on the test results, SLRU had the best performance, with an average hit ratio of 71.4%, followed by LRU (67%), LFU (62%), and FIFO, which showed the lowest hit ratio performance with a hit ratio of 55.8%. The advantage of SLRU lies in dividing cache segmentation into two segments: the probationary segment (LRU) and the protected segment (LFU). Based on the experiment results, it was concluded that SLRU has more efficient results in handling dynamic data access patterns than other algorithms.
Downloads
Download data is not yet available.
Article Details
How to Cite
Wijaya, M. C., Kartawidjaja, M. A. . and Edmund, K. . (2025) “Segmented least recently used cache replacement simulator”, Jurnal Mantik, 9(1), pp. 169-178. doi: 10.35335/mantik.v8i5.6201.
References
Alzakari, N., Dris, A. Bin, & Alahmadi, S. (2020). Randomized Least Frequently Used Cache Replacement Strategy for Named Data Networking. 2020 3rd International Conference on Computer Applications & Information Security (ICCAIS), 1–6. https://doi.org/10.1109/ICCAIS48893.2020.9096733
Asiatici, M., & Ienne, P. (2019). Stop Crying Over Your Cache Miss Rate: Handling Efficiently Thousands of Outstanding Misses in FPGAs. Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 310–319. https://doi.org/10.1145/3289602.3293901
Bachri, K. O., Alexander, J., Osmond, E., Widawati, E., & Kartawidjaja, M. A. (2024). SPArc-subset general-purpose microprocessor design and implementation in field programmable gate array. Mantik, 8(3), 1447–1455. https://doi.org/10.35335/mantik.v8i3.5681
Hasslinger, G., Ntougias, K., Hasslinger, F., & Hohlfeld, O. (2023). Scope and Accuracy of Analytic and Approximate Results for FIFO, Clock-Based and LRU Caching Performance. Future Internet, 15(3). https://doi.org/10.3390/fi15030091
Khan, T. A., Zhang, D., Sriraman, A., Devietti, J., Pokam, G., Litz, H., & Kasikci, B. (2021). Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications. 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), 734–747. https://doi.org/10.1109/ISCA52012.2021.00063
Krishna, K. (2025). Advancements in cache management: a review of machine learning innovations for enhanced performance and security. Frontiers in Artificial Intelligence, 8, 1441250. https://doi.org/10.3389/frai.2025.1441250
Kumar, S., & Singh, P. K. (2016). An overview of modern cache memory and performance analysis of replacement policies. 2016 IEEE International Conference on Engineering and Technology (ICETECH), 210–214. https://doi.org/10.1109/ICETECH.2016.7569243
Ma, T., Hao, Y., Shen, W., Tian, Y., & Al-Rodhaan, M. (2018). An Improved Web Cache Replacement Algorithm Based on Weighting and Cost. IEEE Access, 6, 27010–27017. https://doi.org/10.1109/ACCESS.2018.2829142
Panda, P., Patil, G., & Raveendran, B. (2016). A survey on replacement strategies in cache memory for embedded systems. 2016 IEEE Distributed Computing, VLSI, Electrical Circuits and Robotics (DISCOVER), 12–17. https://doi.org/10.1109/DISCOVER.2016.7806218
Pedro-Zapater, A., Rodríguez, C., Segarra, J., Gran Tejero, R., & Viñals-Yúfera, V. (2020). Ideal and Predictable Hit Ratio for Matrix Transposition in Data Caches. Mathematics, 8(2). https://doi.org/10.3390/math8020184
Podlipnig, S., & Böszörmenyi, L. (2003). A survey of Web cache replacement strategies. ACM Comput. Surv., 35(4), 374–398. https://doi.org/10.1145/954339.954341
Priya, B. K., Kumar, S., Begum, B. S., & Ramasubramanian, N. (2019). Cache lifetime enhancement technique using hybrid cache-replacement-policy. Microelectronics Reliability, 97, 1–15. https://doi.org/https://doi.org/10.1016/j.microrel.2019.03.011
Satria, B. D., Barakbah, A. R., & Sudarsono, A. (2021). Implementation Parallel Computation for Automatic Clustering. Mantik, 5(2), 994–1005. https://doi.org/10.35335/jurnalmantik.Vol5.2021.1439.pp994-1005
Sethumurugan, S., Yin, J., & Sartori, J. (2021). Designing a Cost-Effective Cache Replacement Policy using Machine Learning. 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), 291–303. https://doi.org/10.1109/HPCA51647.2021.00033
Sonia, Alsharef, A., Jain, P., Arora, M., Zahra, S. R., & Gupta, G. (2021). Cache Memory: An Analysis on Performance Issues. 2021 8th International Conference on Computing for Sustainable Global Development (INDIACom), 184–188.
Souza, M. A., & Freitas, H. C. (2024). Reinforcement Learning-Based Cache Replacement Policies for Multicore Processors. IEEE Access, 12, 79177–79188. https://doi.org/10.1109/ACCESS.2024.3409228
Unterluggauer, T., Harris, A., Constable, S., Liu, F., & Rozas, C. (2022). Chameleon Cache: Approximating Fully Associative Caches with Random Replacement to Prevent Contention-Based Cache Attacks. 2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED), 13–24. https://doi.org/10.1109/SEED55351.2022.00009
Wijaya, M. C. (2020). Algoritme penggantian cache proxy terdistribusi untuk meningkatkan kinerja server web. Jurnal Teknologi Dan Sistem Komputer, 8(1), 1–5. https://doi.org/10.14710/jtsiskom.8.1.2020.1-5
Xiong, W., & Szefer, J. (2020). Leaking Information Through Cache LRU States. 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), 139–152. https://doi.org/10.1109/HPCA47549.2020.00021
Yamaki, H. (2019). Flow Characteristic-Aware Cache Replacement Policy for Packet Processing Cache BT - Advances in Information and Communication Networks. Advances in Intelligent Systems and Computing, 886, 258–273. https://doi.org/10.1007/978-3-030-03402-3_18
Yang, J., Zhang, Y., Qiu, Z., Yue, Y., & Vinayak, R. (2023). FIFO queues are all you need for cache eviction. Proceedings of the 29th Symposium on Operating Systems Principles, 130–149. https://doi.org/10.1145/3600006.3613147
Yang, Q., Jin, R., Fan, N., Inupakutika, D., Davis, B., & Zhao, M. (2023). AdaCache: A Disaggregated Cache System with Adaptive Block Size for Cloud Block Storage. Retrieved from https://arxiv.org/abs/2306.17254
Yennimar, Y., Faturrahman, M. R., Nesen, S., Guci, M. A., & Pasaribu, S. R. (2023). Implementation of artificial neural network and support vector machine algorithm on student graduation prediction model on time. Mantik, 7(2), 925–934. https://doi.org/10.35335/mantik.v7i2.3992
Young, V., Chishti, Z. A., & Qureshi, M. K. (2019). TicToc: Enabling Bandwidth-Efficient DRAM Caching for Both Hits and Misses in Hybrid Memory Systems. 2019 IEEE 37th International Conference on Computer Design (ICCD), 341–349. https://doi.org/10.1109/ICCD46524.2019.00055
Zheng, Q., Yang, T., Kan, Y., Tan, X., Yang, J., & Jiang, X. (2022). On the Analysis of Cache Invalidation With LRU Replacement. IEEE Transactions on Parallel and Distributed Systems, 33(3), 654–666. https://doi.org/10.1109/TPDS.2021.3098459
Asiatici, M., & Ienne, P. (2019). Stop Crying Over Your Cache Miss Rate: Handling Efficiently Thousands of Outstanding Misses in FPGAs. Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 310–319. https://doi.org/10.1145/3289602.3293901
Bachri, K. O., Alexander, J., Osmond, E., Widawati, E., & Kartawidjaja, M. A. (2024). SPArc-subset general-purpose microprocessor design and implementation in field programmable gate array. Mantik, 8(3), 1447–1455. https://doi.org/10.35335/mantik.v8i3.5681
Hasslinger, G., Ntougias, K., Hasslinger, F., & Hohlfeld, O. (2023). Scope and Accuracy of Analytic and Approximate Results for FIFO, Clock-Based and LRU Caching Performance. Future Internet, 15(3). https://doi.org/10.3390/fi15030091
Khan, T. A., Zhang, D., Sriraman, A., Devietti, J., Pokam, G., Litz, H., & Kasikci, B. (2021). Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications. 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), 734–747. https://doi.org/10.1109/ISCA52012.2021.00063
Krishna, K. (2025). Advancements in cache management: a review of machine learning innovations for enhanced performance and security. Frontiers in Artificial Intelligence, 8, 1441250. https://doi.org/10.3389/frai.2025.1441250
Kumar, S., & Singh, P. K. (2016). An overview of modern cache memory and performance analysis of replacement policies. 2016 IEEE International Conference on Engineering and Technology (ICETECH), 210–214. https://doi.org/10.1109/ICETECH.2016.7569243
Ma, T., Hao, Y., Shen, W., Tian, Y., & Al-Rodhaan, M. (2018). An Improved Web Cache Replacement Algorithm Based on Weighting and Cost. IEEE Access, 6, 27010–27017. https://doi.org/10.1109/ACCESS.2018.2829142
Panda, P., Patil, G., & Raveendran, B. (2016). A survey on replacement strategies in cache memory for embedded systems. 2016 IEEE Distributed Computing, VLSI, Electrical Circuits and Robotics (DISCOVER), 12–17. https://doi.org/10.1109/DISCOVER.2016.7806218
Pedro-Zapater, A., Rodríguez, C., Segarra, J., Gran Tejero, R., & Viñals-Yúfera, V. (2020). Ideal and Predictable Hit Ratio for Matrix Transposition in Data Caches. Mathematics, 8(2). https://doi.org/10.3390/math8020184
Podlipnig, S., & Böszörmenyi, L. (2003). A survey of Web cache replacement strategies. ACM Comput. Surv., 35(4), 374–398. https://doi.org/10.1145/954339.954341
Priya, B. K., Kumar, S., Begum, B. S., & Ramasubramanian, N. (2019). Cache lifetime enhancement technique using hybrid cache-replacement-policy. Microelectronics Reliability, 97, 1–15. https://doi.org/https://doi.org/10.1016/j.microrel.2019.03.011
Satria, B. D., Barakbah, A. R., & Sudarsono, A. (2021). Implementation Parallel Computation for Automatic Clustering. Mantik, 5(2), 994–1005. https://doi.org/10.35335/jurnalmantik.Vol5.2021.1439.pp994-1005
Sethumurugan, S., Yin, J., & Sartori, J. (2021). Designing a Cost-Effective Cache Replacement Policy using Machine Learning. 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), 291–303. https://doi.org/10.1109/HPCA51647.2021.00033
Sonia, Alsharef, A., Jain, P., Arora, M., Zahra, S. R., & Gupta, G. (2021). Cache Memory: An Analysis on Performance Issues. 2021 8th International Conference on Computing for Sustainable Global Development (INDIACom), 184–188.
Souza, M. A., & Freitas, H. C. (2024). Reinforcement Learning-Based Cache Replacement Policies for Multicore Processors. IEEE Access, 12, 79177–79188. https://doi.org/10.1109/ACCESS.2024.3409228
Unterluggauer, T., Harris, A., Constable, S., Liu, F., & Rozas, C. (2022). Chameleon Cache: Approximating Fully Associative Caches with Random Replacement to Prevent Contention-Based Cache Attacks. 2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED), 13–24. https://doi.org/10.1109/SEED55351.2022.00009
Wijaya, M. C. (2020). Algoritme penggantian cache proxy terdistribusi untuk meningkatkan kinerja server web. Jurnal Teknologi Dan Sistem Komputer, 8(1), 1–5. https://doi.org/10.14710/jtsiskom.8.1.2020.1-5
Xiong, W., & Szefer, J. (2020). Leaking Information Through Cache LRU States. 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), 139–152. https://doi.org/10.1109/HPCA47549.2020.00021
Yamaki, H. (2019). Flow Characteristic-Aware Cache Replacement Policy for Packet Processing Cache BT - Advances in Information and Communication Networks. Advances in Intelligent Systems and Computing, 886, 258–273. https://doi.org/10.1007/978-3-030-03402-3_18
Yang, J., Zhang, Y., Qiu, Z., Yue, Y., & Vinayak, R. (2023). FIFO queues are all you need for cache eviction. Proceedings of the 29th Symposium on Operating Systems Principles, 130–149. https://doi.org/10.1145/3600006.3613147
Yang, Q., Jin, R., Fan, N., Inupakutika, D., Davis, B., & Zhao, M. (2023). AdaCache: A Disaggregated Cache System with Adaptive Block Size for Cloud Block Storage. Retrieved from https://arxiv.org/abs/2306.17254
Yennimar, Y., Faturrahman, M. R., Nesen, S., Guci, M. A., & Pasaribu, S. R. (2023). Implementation of artificial neural network and support vector machine algorithm on student graduation prediction model on time. Mantik, 7(2), 925–934. https://doi.org/10.35335/mantik.v7i2.3992
Young, V., Chishti, Z. A., & Qureshi, M. K. (2019). TicToc: Enabling Bandwidth-Efficient DRAM Caching for Both Hits and Misses in Hybrid Memory Systems. 2019 IEEE 37th International Conference on Computer Design (ICCD), 341–349. https://doi.org/10.1109/ICCD46524.2019.00055
Zheng, Q., Yang, T., Kan, Y., Tan, X., Yang, J., & Jiang, X. (2022). On the Analysis of Cache Invalidation With LRU Replacement. IEEE Transactions on Parallel and Distributed Systems, 33(3), 654–666. https://doi.org/10.1109/TPDS.2021.3098459
Copyright and Licensing
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.