Computer Science ›› 2019, Vol. 46 ›› Issue (3): 327-331.doi: 10.11896/j.issn.1002-137X.2019.03.048

• Interdiscipline & Frontier • Previous Articles     Next Articles

Prefetching Algorithm of Sarsa Learning Based on Space Optimization

LIANG Yuan, YUAN Jing-ling, CHEN Min-cheng   

  1. School of Computer Science and Technology,Wuhan University of Technology,Wuhan 430070,China
  • Received:2018-01-26 Revised:2018-04-01 Online:2019-03-15 Published:2019-03-22

Abstract: As the cluster centers for high-performance computers,data centers are busy with CPU clusters.Irregular data structures and algorithms are frequently used,so that most prefetching technologies based on spatio-temporal locality are no longer applicable.This paper referred to the concept of semantic locality,used the reinforcement learning Sarsa algorithm to approximate semantic locations,and predicted irregular data structures and future memory accesses of algorithms.Due to the large state space and action space,this paper used Deep Q-learning method to optimize the State-action space to fit the new state with the old one and took a similar approach if the two states are similar to improve the generalization ability.The experiment on the standard data set SPECCPU 2006 proves that this method has a widegene-ralization ability and can improve the Cache hit rate effectively.

Key words: Deep Q-learning, Prefetching technology, Sarsa, Semantic locality, State-action space optimization

CLC Number: 

  • TP302
[1]SMITH A J.Cache Memories[J].Acm Computing Surveys,
1982,14(3):473-530.
[2]WENISCH T F.Temporal memory streaming[D].Pittsburgh:Carnegie Mellon University,2007.
[3]SOMOGYI S,WENISCH T F,AILAMAKI A,et al.Spatio-
temporal memory streaming[J].Acm Sigarch Computer Architecture News,2009,37(3):69-80.
[4]COOKSEY R N,JOURDAN S J.Method and apparatus for
next-line prefetching from a predicted memory address:US,US 7093077 B2[P].2006.
[5]JOSEPH D,GRUNWALD D.Prefetching using Markov predictors[C]∥Proceedings of the 24th Annual International Sympo-sium on Computer Architecture.IEEE,1997:252-263.
[6]SOMOGYI S,WENISCH T F,AILAMAKI A,et al.Spatial
Memory Streaming[C]∥International Symposium on Computer Architecture.IEEE,2006:252-263.
[7]SOMOGYI S,WENISCH T F,AILAMAKI A,et al.Spatio-
temporal memory streaming[J].AcmSigarch Computer Architecture News,2009,37(3):69-80.
[8]PELED L,MANNOR S,WEISER U,et al.Semantic locality and context-based prefetching using reinforcement learning[C]∥International Symposium on Computer Architecture.ACM,2015:285-297.
[9]MOZER S,M C,HASSELMO M.Reinforcement Learning:An Introduction[J].IEEE Transactions on Neural Networks,2005,16(1):285-286.
[10]IPEK E,MUTLU O,CARUANA R.Self-Optimizing Memory Controllers:A Reinforcement Learning Approach[C]∥International Symposium on Computer Architecture.IEEE,2008:39-50.
[11]SUTTON R S,MCALLESTER D,SINGH S,et al.Policy Gradient Methods for Reinforcement Learning with Function Approximation[J].Advances in Neural Information Processing Systems,2000,12:1057-1063.
[12]TAN F,YAN P,GUAN X.Deep Reinforcement Learning:From Q-Learning to Deep Q-Learning[C]∥International Conference on Neural Information Processing.Springer,Cham,2017:475-483.
[13]LIN L M,WANG H,WANG Y X.Sarsa Reinforcement Lear-
ning Algorithm Based on Neural Networks[J].Computer Technology & Development,2006(1):30-32.(in Chinese)
林联明,王浩,王一雄.基于神经网络的Sarsa强化学习算法.计算机技术与发展,2006(1):30-32.
[14]DURYEA E,GANGER M,HU W.Exploring Deep Reinforcement Learning with Multi Q-Learning[J].Intelligent Control & Automation,2016,7(4):129-144.
[15]HENNING J L.SPEC CPU2006 benchmark descriptions[J].
Acm Sigarch Computer Architecture News,2006,34(4):1-17.
[1] LI Bin, LIU Quan. Double Weighted Learning Algorithm Based on Least Squares [J]. Computer Science, 2020, 47(12): 210-217.
[2] XU De-zhi, LIAO Hui-huan and XU Lian-jun. Research on Locality Rules of Description Logic SHJF for Module Reusing [J]. Computer Science, 2015, 42(1): 249-252.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!