Apparatus and method for controlling eviction from a storage structure

Abstract

A technique is provided for controlling eviction from a storage structure. An apparatus has a storage structure with a plurality of entries to store data. The apparatus also has eviction control circuitry configured to maintain eviction control information in accordance with an eviction policy, the eviction policy specifying how the eviction control information is to be updated in response to accesses to the entries of the storage structure. The eviction control circuitry is responsive to a victim selection event to employ the eviction policy to select, with reference to the eviction control information, one of the entries to be a victim entry whose data is to be discarded from the storage structure. The eviction control circuitry is further configured to maintain, for each of one or more groups of entries in the storage structure, an indication of a most-recent entry. The most-recent entry is an entry in that group that was most recently subjected to at least a given type of access. For each group, in response to an access to a given entry of that group other than the most-recent entry for that group, the eviction control circuitry is configured to update the eviction control information according to the eviction policy. However, in response to an access to the most-recent entry for that group, the eviction control circuitry is configured to prevent an update to at least the eviction control information associated with the most-recent entry.

The invention claimed is: 
     
       1. An apparatus comprising:
 a storage structure with a plurality of entries to store data; and 
 eviction control circuitry configured to maintain eviction control information in accordance with an eviction policy, the eviction policy specifying how the eviction control information is to be updated in response to accesses to the entries of the storage structure; 
 wherein: 
 the eviction control circuitry is responsive to a victim selection event to employ the eviction policy to select, with reference to the eviction control information, one of the entries to be a victim entry whose data is to be discarded from the storage structure; 
 the eviction control circuitry is further configured to maintain, for each of one or more groups of entries in the storage structure, an indication of a most-recent entry, wherein for each group the most-recent entry is an entry in that group that was most recently subjected to at least a given type of access; 
 for each group, in response to an access to a given entry of that group other than the most-recent entry for that group, the eviction control circuitry is configured to update the eviction control information according to the eviction policy, and in response to an access to the most-recent entry for that group, the eviction control circuitry is configured to prevent an update to at least the eviction control information associated with the most-recent entry; 
 the eviction control circuitry is configured to implement the eviction policy to maintain the eviction control information to distinguish between a used-many state for entries storing data subject to one or more accesses following an initial access and a used-once state for entries storing data not subject to an access following an initial access; and 
 the eviction control circuitry is configured to prevent an update to the eviction control information associated with the most-recent entry from the used-once state to the used-many state. 
 
     
     
       2. The apparatus according to  claim 1 , wherein each entry is arranged to store a plurality of data items that can be accessed independently, and by preventing the update to at least the eviction control information associated with the most-recent entry, this prevents multiple sequential accesses to the individual data items of the entry from causing the eviction control information associated with the most-recent entry to change from the used-once state to the used-many state. 
     
     
       3. The apparatus according to  claim 1 , wherein the eviction control information comprises an eviction influencing value for each entry in the storage structure, the eviction influencing value being initialised to a first value on allocation of data into that entry, and the eviction influencing value being modified from the first value on occurrence of a subsequent access to the entry after the data has been allocated unless prevented due to that entry being identified as the most-recent entry. 
     
     
       4. The apparatus according to  claim 3 , wherein:
 the eviction policy is a re-reference interval prediction policy (RRIP) for which the eviction control information comprises a prediction value for each entry in the storage structure, indicative of a predicted re-reference interval for that entry; and 
 preventing the update comprises preventing an update of the prediction value for the most-recent entry. 
 
     
     
       5. The apparatus according to  claim 1 , wherein:
 the given type of access is a fill access that causes an identified entry of the storage structure to be filled with data. 
 
     
     
       6. The apparatus according to  claim 5 , wherein:
 the eviction control circuitry is configured to update, on each occurrence of the fill access to an entry of a particular group, the indication of the most-recent entry for the particular group to indicate the identified entry that was filled with data in response to the fill access. 
 
     
     
       7. The apparatus according to  claim 1 , wherein:
 each group is associated with a sub-structure of the storage structure. 
 
     
     
       8. The apparatus according to  claim 7 , wherein:
 the storage structure is a set associative storage structure and each sub-structure is a set of the set associative storage structure; and 
 the indication of a most-recent entry is maintained by the eviction control circuitry for each set of the set associative storage structure to provide an indication of a most-recent way of the set most recently subjected to at least the given type of access. 
 
     
     
       9. The apparatus according to  claim 1 , wherein:
 the storage structure comprises a single group of all of the entries in the storage structure and the indication of a most-recent entry comprises an indication of the entry in the storage structure most recently subjected to at least the given type of access. 
 
     
     
       10. The apparatus according to  claim 1 , wherein:
 the storage structure is a cache and each entry of the plurality of entries of the cache comprises a cache line; and 
 each cache line is arranged to cache a plurality of individually addressable data items. 
 
     
     
       11. The apparatus according to  claim 10 , wherein:
 the cache is a level 1 (L1) cache responsive to accesses from processing circuitry and the access to the given entry is an access to a particular data item of a cache line specified by the processing circuitry. 
 
     
     
       12. The apparatus according to  claim 1 , wherein:
 the storage structure is at least one of:
 a cache to store data for access by processing circuitry; 
 a translation lookaside buffer (TLB) to store address translation data used to convert a virtual address specified by the processing circuitry into a physical address in memory; 
 a storage used to maintain branch prediction information referred to by branch prediction circuitry; and 
 a storage structure used to maintain access pattern information used to determine data to be prefetched into the cache. 
 
 
     
     
       13. The apparatus according to  claim 1 , wherein:
 the storage structure is a storage structure within a hierarchy of storage structures and the storage structure is configured to obtain, in response to a request to access data absent from the storage structure, the data from an additional storage structure at a different level of the hierarchy. 
 
     
     
       14. The apparatus according to  claim 1 , wherein:
 the most-recent entry in a particular group is an entry in the particular group that was most recently subjected to any of a plurality of supported types of access. 
 
     
     
       15. The apparatus according to  claim 1 , wherein:
 the victim selection event is triggered to make space in the storage structure for allocating data in response to a request to access data not already stored in the storage structure. 
 
     
     
       16. The apparatus according to  claim 1 , wherein:
 the victim selection event is triggered by a cache maintenance operation. 
 
     
     
       17. A method of managing a storage structure having a plurality of entries for storing data, the method comprising:
 maintaining eviction control information in accordance with an eviction policy, the eviction policy specifying how the eviction control information is to be updated in response to accesses to the entries of the storage structure, the eviction control information distinguishing between a used-many state for entries storing data subject to one or more accesses following an initial access and a used-once state for entries storing data not subject to an access following an initial access; 
 employing the eviction policy to select, responsive to a victim selection event, with reference to the eviction control information, one of the entries to be a victim entry whose data is to be discarded from the storage structure; 
 maintaining, for each of one or more groups of entries in the storage structure, an indication of a most-recent entry, wherein for each group the most-recent entry is an entry in that group that was most recently subjected to at least a given type of access; 
 for each group, in response to an access to a given entry of that group other than the most-recent entry for that group, updating the eviction control information according to the eviction policy; and 
 for each group, in response to an access to the most-recent entry for that group, preventing an update to at least the eviction control information associated with the most-recent entry from the used-once state to the used-many state. 
 
     
     
       18. An apparatus comprising:
 a storage structure with a plurality of entries to store data; and 
 eviction control circuitry configured to maintain eviction control information in accordance with an eviction policy, the eviction policy specifying how the eviction control information is to be updated in response to accesses to the entries of the storage structure; 
 wherein: 
 the eviction control circuitry is responsive to a victim selection event to employ the eviction policy to select, with reference to the eviction control information, one of the entries to be a victim entry whose data is to be discarded from the storage structure; 
 the eviction control circuitry is further configured to maintain, for each of one or more groups of entries in the storage structure, an indication of a most-recent entry, wherein for each group the most-recent entry is an entry in that group that was most recently subjected to at least a given type of access, wherein the given type of access is a fill access that causes an identified entry of the storage structure to be filled with data; 
 for each group, in response to an access to a given entry of that group other than the most-recent entry for that group, the eviction control circuitry is configured to update the eviction control information according to the eviction policy, and in response to an access to the most-recent entry for that group, the eviction control circuitry is configured to prevent an update to at least the eviction control information associated with the most-recent entry; and 
 the eviction control circuitry is configured to update, on each occurrence of the fill access to an entry of a particular group, the indication of the most-recent entry for the particular group to indicate the identified entry that was filled with data in response to the fill access. 
 
     
     
       19. An apparatus comprising:
 a storage structure with a plurality of entries to store data; and 
 eviction control circuitry configured to maintain eviction control information in accordance with an eviction policy, the eviction policy specifying how the eviction control information is to be updated in response to accesses to the entries of the storage structure; 
 wherein: 
 the eviction control circuitry is responsive to a victim selection event to employ the eviction policy to select, with reference to the eviction control information, one of the entries to be a victim entry whose data is to be discarded from the storage structure; 
 the eviction control circuitry is further configured to maintain, for each of one or more groups of entries in the storage structure, an indication of a most-recent entry, wherein for each group the most-recent entry is an entry in that group that was most recently subjected to at least a given type of access; 
 for each group, in response to an access to a given entry of that group other than the most-recent entry for that group, the eviction control circuitry is configured to update the eviction control information according to the eviction policy, and in response to an access to the most-recent entry for that group, the eviction control circuitry is configured to prevent an update to at least the eviction control information associated with the most-recent entry; 
 each group is associated with a sub-structure of the storage structure; 
 the storage structure is a set associative storage structure and each sub-structure is a set of the set associative storage structure; and 
 the indication of a most-recent entry is maintained by the eviction control circuitry for each set of the set associative storage structure to provide an indication of a most-recent way of the set most recently subjected to at least the given type of access.