A Cache Replacement Policy with Considering Fluctuation Patterns of Total Priority Value

Abstract

In recent computer systems, a high-performance memory system is required for improving the computing performance. To improve the performance of the memory system, the capacity and the associativity of cache memories tend to be enlarged in all the memory hierarchy. Therefore, a high-performance cache replacement policy is required, which can be implemented with a small overhead and can adapt the behavior of various applications.

Under such a situation, the adaptive demotion policy with considering global fluctuations of priority values (ADP-G) is proposed. ADP-G is based on the adaptive demotion policy (ADP) which can adapt the behavior of various applications by changing its insertion, promotion, demotion and selection (IPDS) policies. ADP-G selects the appropriate IPDS policies from two alternatives, one is suitable for a temporal locality and the other has a scan/thrashing tolerant. For this selection, ADP-G uses the global fluctuations of priority values of all the blocks in the cache. Although ADP-G is a high-performance cache replacement policy as compared with conventional ones, it causes a problem when the performance of the scan/thrashing tolerant IPDS policies is higher than that of the temporal locality IPDS policies.

This paper discusses a novel cache replacement policy to solve this problem. At first, the fluctuation patterns of total priority value in several benchmarks are analyzed. As a result, two characteristics are observed which are useful to detect that the running application the suitable for the temporal locality IPDS policies or the scan/thrashing tolerant IPDS policies. Based on this analysis, a cache replacement policy with considering fluctuation patterns of total priority value is proposed, and it is called ADP-P. ADP-P has two states which suitable for the temporal locality and the scan/thrashing tolerant. To detect the suitable state, ADP-P uses the total of the priority values of all the blocks in the cache, and the value is stored in the global total register (GTR). When the state is for the temporal locality, the state is changed to the scan/thrashing tolerant state if the reduction of GTR is larger than the threshold value. When the state is for the scan/thrashing tolerant, the state is changed to the temporal locality state if the fluctuation of GTR which is larger than the threshold value is not caused for a fixed number of cache accesses.

Experimental results show the proposed cache replacement policy achieves a reduction of cache misses compared to LRU policy and ADP-G. When the L3 cache size is 4MB, in the geometric mean of all the benchmarks, the proposed cache replacement policy achieves a 6.0% and 11% MPKI reduction compared to ADP-G and LRU policy, respectively.