Method and apparatus for prefetching data items to a cache

Abstract

An apparatus, a computer program and a method for prefetching a predetermined number of data items to a cache. The method comprises obtaining a list of candidate data items and associated scores thereof, that comprises more candidate data items than the predetermined number of data items to be prefetched to the cache. The method comprises repeatedly selecting, based on scores of the candidate data items, a candidate data item from the list and determining whether to add the candidate data item to the cache. Determining whether to add the candidate data item to the cache comprises determining whether the candidate data item is retained by the cache; and in response to determining that the candidate data item is not retained by the cache, adding the candidate data item thereto. The repeatedly selecting and determining are performed until the predetermined number of data items is added to the cache.

What is claimed is: 
     
       1. A method for prefetching a predetermined number of data items to a cache, comprising:
 obtaining a list of candidate data items to be prefetched, wherein a number of candidate data items is larger than the predetermined number of data items to be prefetched to the cache, wherein each candidate data item is associated with a score, the score indicating a likelihood of the candidate data item to be retrieved from the cache; and 
 repeatedly selecting a candidate data item from the list and determining whether to add the candidate data item to the cache, wherein said selecting is based on an order of the list, wherein the order of the list is based on scores of the candidate data items, wherein said determining whether to add the candidate data item to the cache comprises:
 determining whether the candidate data item is retained by the cache; and 
 in response to determining that the candidate data item is not retained by the cache, adding the candidate data item to the cache; 
 
 wherein said repeatedly selecting and determining are performed until the predetermined number of data items is added to the cache. 
 
     
     
       2. The method of  claim 1  further comprising:
 in response to determining that the candidate data item is retained by the cache in a cache line, updating an evacuation measurement of the cache line. 
 
     
     
       3. The method of  claim 2 , wherein the cache is a Least Recently Used (LRU) cache, wherein the evacuation measurement is a freshness measurement of the cache line. 
     
     
       4. The method of  claim 2 , wherein said adding the candidate data item to the cache requires a first processing time duration, wherein said updating the evacuation measurement of the cache line requires a second processing time duration, wherein the second processing time duration is smaller than the first processing time duration. 
     
     
       5. The method of  claim 1 , wherein a score associated with each candidate data item indicates the likelihood of the candidate data item being retrieved from the cache. 
     
     
       6. The method of  claim 5 , wherein the score associated with each candidate data item is determined by a Machine Learning-based predictor. 
     
     
       7. The method of  claim 6 , wherein Machine Learning-based predictor is based on a Long Short-Term Memory (LSTM) network. 
     
     
       8. The method of  claim 1 , wherein said determining whether to add the candidate data item to the cache further comprises determining that the score of the candidate data item is above a predetermined threshold. 
     
     
       9. The method of  claim 1 , wherein said obtaining a list comprises:
 obtaining an initial list that comprises the list and additional data items; and 
 selecting an N-top candidate data items from the initial list based on corresponding scores thereof, whereby obtaining the list. 
 
     
     
       10. An apparatus having a processor, a memory and a cache, the processor being adapted to perform the steps of:
 obtaining a list of candidate data items to be prefetched, wherein a number of candidate data items is larger than the predetermined number of data items to be prefetched to the cache, wherein each candidate data item is associated with a score, the score indicating a likelihood of the candidate data item to be retrieved from the cache; and 
 repeatedly selecting a candidate data item from the list and determining whether to add the candidate data item to the cache, wherein said selecting is based on an order of the list, wherein the order of the list is based on scores of the candidate data items, wherein said determining whether to add the candidate data item to the cache comprises:
 determining whether the candidate data item is retained by the cache; and 
 in response to determining that the candidate data item is not retained by the cache, adding the candidate data item to the cache; 
 
 wherein said repeatedly selecting and determining are performed until the predetermined number of data items is added to the cache. 
 
     
     
       11. The apparatus of  claim 10 , wherein the processor is further adapted to perform:
 in response to determining that the candidate data item is retained by the cache in a cache line, updating an evacuation measurement of the cache line. 
 
     
     
       12. The apparatus of  claim 11 , wherein the cache is a Least Recently Used (LRU) cache, wherein the evacuation measurement is a freshness measurement of the cache line. 
     
     
       13. The apparatus of  claim 11 , wherein said adding the candidate data item to the cache requires a first processing time duration, wherein said updating the evacuation measurement of the cache line requires a second processing time duration, wherein the second processing time duration is smaller than the first processing time duration. 
     
     
       14. The apparatus of  claim 10 , wherein a score associated with each candidate data item indicates the likelihood of the candidate data item being retrieved from the cache. 
     
     
       15. The apparatus of  claim 14 , wherein the score associated with each candidate data item is determined by a Machine Learning-based predictor. 
     
     
       16. The apparatus of  claim 15 , wherein Machine Learning-based predictor is based on a Long Short-Term Memory (LSTM) network. 
     
     
       17. The apparatus of  claim 10 , wherein said determining whether to add the candidate data item to the cache further comprises determining that the score of the candidate data item is above a predetermined threshold. 
     
     
       18. The apparatus of  claim 10 , wherein said obtaining a list comprises:
 obtaining an initial list that comprises the list and additional data items; and 
 selecting an N-top candidate data items from the initial list based on corresponding scores thereof, whereby obtaining the list. 
 
     
     
       19. A computer program product comprising a non-transitory computer readable storage medium retaining program instructions, which program instructions when read by a processor, cause the processor to perform a method comprising:
 obtaining a list of candidate data items to be prefetched, wherein a number of candidate data items is larger than the predetermined number of data items to be prefetched to the cache, wherein each candidate data item is associated with a score, the score indicating a likelihood of the candidate data item to be retrieved from the cache; and 
 repeatedly selecting a candidate data item from the list and determining whether to add the candidate data item to the cache, wherein said selecting is based on an order of the list, wherein the order of the list is based on scores of the candidate data items, wherein said determining whether to add the candidate data item to the cache comprises: 
 determining whether the candidate data item is retained by the cache; and 
 in response to determining that the candidate data item is not retained by the cache, adding the candidate data item to the cache; 
 wherein said repeatedly selecting and determining are performed until the predetermined number of data items is added to the cache.