A Cache Replacement Policy Based on Instruction Flow Access Pattern Prediction

Traditional cache replacement policies are mainly based on heuristics. In recent years, researchers have used prediction technologies to improve the performance of cache replacement. The application of prediction technologies is gradually becoming one research focus in cache replacement. Because the behaviors of loads and stores are complex, predicting these behaviors in caching systems is difficult with uncertainty. Some existing approaches have been proposed to resolve the problem with more and more complicated prediction algorithms. However, these methods cannot reduce uncertainty, and these methods cannot avoid the interference of out-of-order execution and cache prefetching at the same time. To solve these problems, we propose an approach to predict future memory reference, named IFAPP (instruction flow access pattern prediction). IFAPP recognizes loads and stores in programs based on the instructions flow predicted by branch prediction, and then IFAPP predicts the behavior of each of the loads and stores. IFAPP calculates reuse distance through predicted memory reference, and evicts the candidate with the largest reuse distance. IFAPP avoids the interference of out-of-order execution and cache prefetching. Besides, the objects of prediction are single loadstore behaviors which are easy to predict. Both of these alleviate the uncertainty of caching predictions. The evaluations prove that IFAPP reduces the cache misses by 3.2% compared with LRU in L1D. Compared with BRRIP and BIP, IFAPP reduces the cache misses by 12.3% and 14.4% in L1D.