Prefetch-adaptive intelligent cache replacement policy for high performance

Abstract

The invention discloses a prefetch-adaptive intelligent cache replacement policy for high performance, in the presence of hardware prefetching, a prefetch request and a demand request are distinguished, a prefetch predictor based on an ISVM (Integer Support Vector Machine) is used for carrying out re-reference interval prediction on a cache line of prefetching access loading, and a demand predictor based on an ISVM is utilized to carry out re-reference interval prediction on a cache line of demand access loading. A PC of a current access load instruction and PCs of past load instructions in an access historical record are input, different ISVM predictors are designed for prefetch and demand requests, reuse prediction is performed on a loaded cache line by taking a request type as granularity, the accuracy of cache line reuse prediction in the presence of prefetching is improved, and performance benefits from hardware prefetching and cache replacement is better fused.

We claim: 
     
       1. A prefetch-adaptive intelligent cache replacement policy for high performance comprising:
 distinguishing prefetch and demand requests, using an ISVM-based prefetch predictor to predict re-reference interval for cache lines loaded by prefetch access, using an ISVM-based demand predictor to predict re-reference interval for cache lines loaded by demand access; 
 wherein cache replacement is performed based on predicted results, each predictor corresponding to a set of ISVM tables, ISVM table A corresponds to a PC address B, and ISVM table A consists of PC addresses B and 16 ISVM weights, of which the 16 ISVM weights correspond to 16 PC addresses that have the most occurrences in PCHR except B, and an initial value of the weight is set to 0; 
 wherein training process of the two predictors is the same, including the following steps: 
 preparation of training data: 
 step 1. select part of cache sets in a last level cache as sampling sets, input data of the demand predictor includes a PC address of a load instruction that generates a demand access. and past PCs stored in PCHR; 
 the input data of the prefetch predictor includes PC address of the load instruction that triggers the prefetch access, and past PCs stored in the PCHR; 
 PCHR added on the hardware is used to save the past load instructions in the process of running PC history record; 
 step 2, add a component DMINgen, and reconstruct Demand-MIN algorithm on the hardware to provide training labels for the input data of a training predictor; the training labels are divided into positive example labels and negative example labels; the positive example label indicates that a currently accessed cache line is cache-friendly which can be inserted into the cache; the negative label indicates that the currently accessed cache line is cache-averse and cannot be inserted into the cache; the specific generation method is as follows: 
 for a usage interval that ends with the prefetch access P, namely D-P and P-P. DMINgen determines that the currently accessed cache line will not generate a demand hit, and at this time generates a negative label for a PC that accessed the cache line last time; 
 for the usage interval that ends with demand access D, namely P-D and D-D, DMINgen determines that the currently accessed cache line will generate a demand hit; a positive label is generated for the PC that accessed the cache line last time; if the cache space is full at a certain moment in the usage interval, a negative label is generated for the PC that accessed the cache line last time; 
 the described usage interval refers to a time interval that starts with a reference to X and proceeds up to its next reference X; the usage interval of line X represents a requirement of line X to the cache, and is used to determine whether the reference to line X will cause a cache hit; 
 predictor training: 
 ISVM-based prefetch predictor and the ISVM-based demand predictor are trained separately according to the memory access behavior of the sampled cache sets with the same training method, specifically: after the predictor reads the input data, the ISVM table corresponding to the predictor find the weights corresponding to the current input data of PC and in PCHR, if the label corresponding to the input data is positive, the weight will increase by 1; otherwise, the weight will decrease by 1; if a sum of weights corresponding to the current input data PC and PCHR in the ISVM table is greater than a threshold, the weight will not be updated this time. 
 
     
     
       2. The prefetch-adaptive intelligent cache replacement policy for high performance according to  claim 1 , wherein prediction process of the two predictors is the same, including the following steps:
 the demand predictor or the prefetch predictor is selected for prediction according to the requested type of access; first, create a 4-bit hash for each PC in PCHR, which is used to find the weights corresponding to the current contents of the PCHR, and search the weights in the corresponding ISVM table; these weights are then summed, and if the summation is greater than or equal to the threshold, a currently loaded cache line is predicted to be cache friendly, and insert it with high priority; if the summation is less than 0, a line is predicted to not meet a cache requirement, and the line is inserted corresponding to a low priority; for the rest, the line is predicted to be cache-friendly with a low confidence, and the line is inserted corresponding to medium priority, the priority represents the reusability and importance of the line, with higher priority lines staying longer in the cache and lower priority lines being evicted earlier. 
 
     
     
       3. The prefetch-adaptive intelligent cache replacement policy for high performance according to  claim 1 , wherein the cache replacement methods are as follows:
 when replacing a cache line, the cache line with low priority will be selected as an eviction candidate; if there is no such line, an earliest line entering the cache will be selected from the cache-friendly lines for eviction.