Articles
Reinforcement Learning-Driven Cache Management: Advanced Belady-Inspired Strategies with Bypass Optimization and Access Pattern Evaluation
Downloads
Keywords
ACache management
reinforcement learning
Belady’s algorithm
bypass optimization
Article Usage Statistics
Live Metrics
Abstract Views
181
File Views
100
PDF
0
HTML
0
Other
100
Total
281
Article Usage Chart
Abstract
File Views
PDF
HTML
Other
Total
Abstract
Cache memory management remains a critical determinant of computing system performance, particularly under workloads with high spatial and temporal locality. Traditional replacement strategies, exemplified by Belady’s optimal algorithm, provide theoretical baselines but are infeasible for practical implementation due to their requirement for future knowledge (Belady, 1966). Recent advancements in reinforcement learning (RL) have enabled adaptive, data-driven cache management strategies that dynamically adjust replacement and bypass decisions based on runtime access patterns. This paper proposes an RL-driven framework that integrates Belady-inspired heuristics with bypass optimization to enhance cache utilization, reduce miss rates, and improve system throughput. We evaluate the approach using synthetic and benchmark workloads, including SPEC CPU2017 (Bucek et al., 2018), demonstrating up to 15% reduction in last-level cache misses compared to state-of-the-art re-reference interval prediction (RRIP) and adaptive insertion policies. Analytical results illustrate the efficacy of RL in capturing complex access behaviors, while a detailed discussion addresses implementation trade-offs, scalability, and potential integration into heterogeneous architectures.
Downloads
Download data is not yet available.
References
1. L. A. Belady, “A study of replacement algorithms for a virtual-storage computer,” IBM Syst. J., vol. 5, no. 2, pp. 78–101, 1966.
2. J. Bucek, K.-D. Lange, and J. V. Kistowski, “SPEC CPU2017: Next-generation compute benchmark,” in Proc. Companion ACM/SPEC Int. Conf. Perform. Eng., Apr. 2018, pp. 41–42.
3. Jain and C. Lin, “Back to the future: Leveraging Belady’s algorithm for improved cache replacement,” ACM SIGARCH Comput. Archit. News, vol. 44, no. 3, pp. 78–89, 2016.
4. A. Jaleel, K. B. Theobald, S. C. Steely, and J. Emer, “High performance cache replacement using re-reference interval prediction (RRIP),” ACM SIGARCH Comput. Archit. News, vol. 38, no. 3, pp. 60–71, Jun. 2010.
5. Jaleel, W. Hasenplaugh, M. Qureshi, J. Sebot, S. Steely, and J. Emer, “Adaptive insertion policies for managing shared caches,” in Proc. Int. Conf. Parallel Architectures Compilation Techn. (PACT), Oct. 2008, pp. 208–219.
6. D. A. Jimenez and C. Lin, “Dynamic branch prediction with perceptrons,” in Proc. HPCA 7th Int. Symp. High-Perform. Comput. Archit., 2001, pp. 197–206.
7. D. A. Jiménez and E. Teran, “Multiperspective reuse prediction,” in Proc. 50th Annu. IEEE/ACM Int. Symp. Microarchitecture, Oct. 2017, pp. 436–448.
8. F. Hameed, L. Bauer, and J. Henkel, “Reducing inter-core cache contention with an adaptive bank mapping policy in DRAM cache,” in Proc. Int. Conf. Hardw./Softw. Codesign Syst. Synth. (CODES+ISSS), Sep. 2013, pp. 1–8.
9. M. Ferdman, A. Adileh, O. Kocberber, S. Volos, M. Alisafaee, D. Jevdjic, C. Kaynak, A. D. Popescu, A. Ailamaki, and B. Falsafi, “Clearing the clouds: A study of emerging scale-out workloads on modern hardware,” ACM SIGPLAN Notices, vol. 47, no. 4, pp. 37–48, Jun. 2012.
10. D. A. Jimenez and E. Teran, “Multiperspective reuse prediction,” in Proc. 50th Annu. IEEE/ACM Int. Symp. Microarchitecture, Oct. 2017, pp. 436–448.
11. J. Kim, E. Teran, P. V. Gratz, D. A. Jiménez, S. H. Pugsley, and C. Wilkerson, “Kill the program counter: Reconstructing program behavior in the processor cache hierarchy,” ACM SIGPLAN Notices, vol. 52, no. 4, pp. 737–749, May 2017.
12. A. M. Krause, P. C. Santos, and P. O. A. Navaux, “Avoiding unnecessary caching with history-based preemptive bypassing,” in Proc. IEEE 34th Int. Symp. Comput. Archit. High Perform. Comput. (SBAC-PAD), Nov. 2022, pp. 71–80.
13. S. Kumar and P. K. Singh, “An overview of modern cache memory and performance analysis of replacement policies,” in Proc. IEEE Int. Conf. Eng. Technol. (ICETECH), Mar. 2016, pp. 210–214.
14. J. D. Maag, P. E. I. Marín, T. M. Arnal, V. V. Yúfera, and J. M. L. Gri nó, “ReD: A policy based on reuse detection for demanding block selection in last-level caches,” in Proc. 2nd Cache Replacement Championship Workshop Schedule, 2017, pp. 1–4.
15. J. L. Henning, “SPEC CPU2006 benchmark descriptions,” ACM SIGARCH Comput. Archit. News, vol. 34, no. 4, pp. 1–17, Sep. 2006.
16. Shah, A. Jain, and C. Lin, “Effective mimicry of Belady’s MIN policy,” in Proc. IEEE Int. Symp. High-Perform. Comput. Archit. (HPCA), Apr. 2022, pp. 558–572.
17. V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
18. M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, and J. Emer, “Adaptive insertion policies for high performance caching,” ACM SIGARCH Comput. Archit. News, vol. 35, no. 2, pp. 381–391, Jun. 2007.
19. E. Perelman, G. Hamerly, M. Van Biesbrouck, T. Sherwood, and B. Calder, “Using SimPoint for accurate and efficient simulation,” ACM SIGMETRICS Perform. Eval. Rev., vol. 31, no. 1, pp. 318–319, Jun. 2003.
20. P. Zhang, A. Srivastava, A. V. Nori, R. Kannan, and V. K. Prasanna, “Fine-grained address segmentation for attention-based variable-degree prefetching,” in Proc. 19th ACM Int. Conf. Comput. Frontiers, May 2022, pp. 103–112.
21. A. Vakil-Ghahani, S. Mahdizadeh-Shahri, M.-R. Lotfi-Namin, M. Bakhshalipour, P. Lotfi-Kamran, and H. Sarbazi-Azad, “Cache replacement policy based on expected hit count,” IEEE Comput. Archit. Lett., vol. 17, no. 1, pp. 64–67, Jan. 2018.
22. V. Young, C.-C. Chou, A. Jaleel, and M. Qureshi, “SHiP++: Enhancing signature-based hit predictor for improved cache performance,” in Proc. 2nd Cache Replacement Championship (CRC-2 Workshop ISCA, 2017.
23. C.-J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely, and J. Emer, “SHiP: Signature-based hit predictor for high performance caching,” in Proc. 44th Annu. IEEE/ACM Int. Symp. Microarchitecture (MICRO), Dec. 2011, pp. 430–441.
24. S. Sethumurugan, J. Yin, and J. Sartori, “Designing a cost-effective cache replacement policy using machine learning,” in Proc. IEEE Int. Symp. High-Perform. Comput. Archit. (HPCA), Feb. 2021, pp. 291–303.
25. R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, MA, USA: MIT Press, 2018.
26. Y. Zeng and X. Guo, “Long short term memory based hardware prefetcher: A case study,” in Proc. Int. Symp. Memory Syst., Oct. 2017, pp. 305–311.
27. 27. (2017). The 2nd Cache Replacement Championship. [Online]. Available: https://crc2.ece.tamu.edu/
28. 28. Z. Shi, X. Huang, A. Jain, and C. Lin, “Applying deep learning to the cache replacement problem,” in Proc. 52nd Annu. IEEE/ACM Int. Symp. Microarchitecture, Oct. 2019, pp. 413–425.