Deep Reinforcement Learning for Cache Replacement Policy

Requirements

torch
numpy
pandas
matplotlib

Data Generation

mkdir data
python3 utils/gen_zipf.py ./data/zipf_10k.csv 10000 50000 1.5 10

Reproducing Results

To reproduce the results in the report, run one of the scripts ending in run_<agent>.sh which correspond to different agents. For more specific results, run python3 train.py with the right command line arguments. Every option has a default argument for an easier start.

Running Code

The cache environment simulator has been adopted from DRLCache. The file outputs.zip contains all the train logs from running the run_<agent>.sh commands. Unzip this folder to a convenient location and open the parse_logs.ipynb jupyter notebook. In this notebook, set OUTPUT_DIR = "/path/to/where/you/unzipped" and then set the Model variable on Line 9 of the notebook to one of ['Baselines', 'SarsaLambda', 'ActorCritic', 'ActorCriticQ', 'PPO_shallow', 'PPO_deep', 'DQN', 'REINFORCE (shallow)', 'REINFORCE (deep)', 'REINFORCE (attention)', 'FINAL'] to re-create plots from the paper.

References

1. Al-Zoubi, Hussein, Aleksandar Milenkovic, and Milena Milenkovic. "Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite." Proceedings of the 42nd annual Southeast regional conference. 2004.
2. Belady, Laszlo A. "A study of replacement algorithms for a virtual-storage computer." IBM Systems journal 5.2 (1966): 78-101.
3. Berger, Daniel S. "Towards lightweight and robust machine learning for cdn caching." Proceedings of the 17th ACM Workshop on Hot Topics in Networks. 2018.
4. Berger, Daniel S., Nathan Beckmann, and Mor Harchol-Balter. "Practical bounds on optimal caching with variable object sizes." Proceedings of the ACM on Measurement and Analysis of Computing Systems 2.2 (2018): 1-38.
5. BreslauL, CaoP, and ShenkerS PhilipsG. "Webcachingand Zipf likedistributions: Evidenceandimplications." Proceedingsofthe IEEEInternationalConferenceonComputerCommunications. NewYork, USA 126 (1999): 134.
6. Brownlee, Jason. "A gentle introduction to the rectified linear unit (ReLU)." Machine learning mastery 6 (2019).
7. Chen, Jiayi, et al. "Darwin: Flexible learning-based cdn caching." Proceedings of the ACM SIGCOMM 2023 Conference. 2023.
8. What is a content delivery network (cdn)?
9. Gober, Nathan, et al. "The championship simulator: Architectural simulation for education and competition." arXiv preprint arXiv:2210.14324 (2022).
10. Hackenberg, Daniel, Daniel Molka, and Wolfgang E. Nagel. "Comparing cache architectures and coherency protocols on x86-64 multicore SMP systems." Proceedings of the 42Nd Annual IEEE/ACM International Symposium on microarchitecture. 2009.
11. Henning, John L. "SPEC CPU2006 benchmark descriptions." ACM SIGARCH Computer Architecture News 34.4 (2006): 1-17.
12. Liu, Evan, et al. "An imitation learning approach for cache replacement." International Conference on Machine Learning. PMLR, 2020.
13. Puzak, Thomas Roberts. Analysis of cache replacement-algorithms. University of Massachusetts Amherst, 1985.
14. Rummery, Gavin A., and Mahesan Niranjan. On-line Q-learning using connectionist systems. Vol. 37. Cambridge, UK: University of Cambridge, Department of Engineering, 1994.
15. Sadeghi, Alireza, et al. "Reinforcement learning for adaptive caching with dynamic storage pricing." IEEE Journal on Selected Areas in Communications 37.10 (2019): 2267-2281.
16. Schulman, John, et al. "Proximal policy optimization algorithms." arXiv preprint arXiv:1707.06347 (2017).
17. Sethumurugan, Subhash, Jieming Yin, and John Sartori. "Designing a cost-effective cache replacement policy using machine learning." 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 2021.
18. Shi, Zhan, et al. "Applying deep learning to the cache replacement problem." Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture. 2019.
19. Singh, Inderpreet, et al. "Cache coherence for GPU architectures." 2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA). IEEE, 2013.
20. Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
21. Peihao Wang, Yuehao Wang, and Rui Wang. Drlcache: Deep reinforcement learning-based cache replacement policy.
22. Williams, Ronald J. "Simple statistical gradient-following algorithms for connectionist reinforcement learning." Machine learning 8 (1992): 229-256.
23. Wu, Carole-Jean, et al. "SHiP: Signature-based hit predictor for high performance caching." Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture. 2011.
24. Young, Vinson, et al. "Ship++: Enhancing signature-based hit predictor for improved cache performance." The 2nd Cache Replacement Championship (CRC-2 Workshop in ISCA 2017). 2017.
25. Zhong, Chen, M. Cenk Gursoy, and Senem Velipasalar. "Deep reinforcement learning-based edge caching in wireless networks." IEEE Transactions on Cognitive Communications and Networking 6.1 (2020): 48-61.
26. Zhou, Yang, et al. "An end-to-end automatic cache replacement policy using deep reinforcement learning." Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 32. 2022.
27. Zhou, Yang, et al. "An Efficient Deep Reinforcement Learning-based Automatic Cache Replacement Policy in Cloud Block Storage Systems." IEEE Transactions on Computers (2023).
28. Zhu, Hao, et al. "Caching transient data for Internet of Things: A deep reinforcement learning approach." IEEE Internet of Things Journal 6.2 (2018): 2074-2083.