Instruction Cache Management Based on Temporal Locality

Abstract

The present disclosure relates to managing an instruction cache based on temporal locality of cached instructions. One example method includes receiving a request for a first instruction included in a software application; storing the first instruction in a cache structure; receiving a request for a second instruction included in the software application; determining that a cache entry must be removed from the cache structure to create space to store the second instruction; determining that the first instruction should be removed from the cache structure based on temporal locality attributes associated with at least one of the first instruction or the second instruction, the temporal locality attributes representing a likelihood that additional requests will be received for an associated instruction while the instruction is stored in the cache structure; removing the first instruction from the cache structure; and storing the second instruction in the cache structure.

What is claimed is: 
     
         1 . A computer-implemented method executed by one or more processors, the method comprising:
 receiving a request for a first instruction included in a software application;   storing a first cache entry corresponding to the first instruction in a cache structure;   receiving a request for a second instruction included in the software application, the second instruction different than the first instruction;   in response to receiving a request for the second instruction, determining that a cache entry must be removed from the cache structure to create space to store a second cache entry corresponding to the second instruction;   in response to determining that a cache entry must be removed, determining that the first cache entry corresponding to the first instruction should be removed from the cache structure based on temporal locality attributes associated with at least one of the first instruction or the second instruction, the temporal locality attributes representing a likelihood that additional requests will be received for an associated instruction while the instruction is stored in a cache structure;   in response to determining that the first cache entry corresponding to the first instruction should be removed, removing the first cache entry from the cache structure; and   in response to removing the first cache entry, storing the second cache entry in the cache structure.   
     
     
         2 . The method of  claim 1 , wherein storing the first cache entry includes storing the first cache entry in the cache structure at a particular priority level based on the temporal locality attributes, and the determination that the first cache entry should be removed is based at least in part on the particular priority level. 
     
     
         3 . The method of  claim 1 , wherein the first cache entry includes a temporal flag indicating whether the first cache entry is likely to be accessed, and the method further comprises:
 setting the value of the temporal flag of the first cache entry based on the temporal locality attributes, wherein the determination that the first cache entry should be removed is based at least in part on the value of the temporal flag.   
     
     
         4 . The method of  claim 1 , wherein the first cache entry includes a use flag indicating whether the first cache entry has been accessed within the cache, the determination that the first cache entry should be removed is based at least in part on the use flag. 
     
     
         5 . The method of  claim 1 , wherein the temporal locality attributes include historical execution data for the software application. 
     
     
         6 . The method of  claim 1 , wherein the temporal locality attributes include a temporal indicator indicating whether additional requests for the associated instruction are likely or unlikely to be received while stored in the cache structure. 
     
     
         7 . The method of  claim 1 , wherein the temporal locality attributes are associated with a particular instruction region including one or more instructions, and represent a likelihood that additional requests will be received for instructions included in the instruction region. 
     
     
         8 . The method of  claim 1 , wherein the temporal locality attributes are determined at least partly during execution of the software application. 
     
     
         9 . The method of  claim 1 , wherein the temporal locality attributes are determined based at least in part on branch prediction results for the software application. 
     
     
         10 . A computer-implemented method executed by one or more processors, the method comprising:
 determining a first temporal locality indicator for a first instruction region of a software application and a second temporal locality indicator for a second instruction region of the software application different than the first instruction region, the first and second instruction regions each including one or more instructions, the first and second temporal locality indicators representing likelihoods that instructions included in the first and second instruction regions, respectively, will be re-executed while the instructions are stored in a cache structure, the second temporal locality indicator indicating that instructions in the second instruction region are more likely to be re-executed than instructions in the first instruction region; and   providing the first temporal locality indicator and the second temporal locality indicator to the cache structure, wherein the cache structure is configured to store cache entries representing instructions of the software application as the instructions are executed by a processor executing the software application, and wherein the cache structure is configured to remove a first cache entry representing an instruction included in the first instruction region to create space to store a second cache entry representing an instruction included in the second instruction region based at least in part on the first temporal locality indicator and the second temporal locality indicator.   
     
     
         11 . The method of  claim 10 , wherein determining the first and second temporal locality indicators is based at least in part on historical execution data for the software application. 
     
     
         12 . The method of  claim 10 , wherein determining the first and second temporal locality indicators is based at least in part on branch prediction analysis of the software application. 
     
     
         13 . The method of  claim 10 , determining the first and second temporal locality indicators includes:
 monitoring usage of instructions in the first instruction region and the second instruction region during execution of the software application; and   updating the first and second temporal locality indicators based on the monitored usage.   
     
     
         14 . The method of  claim 10 , wherein determining the first and second temporal locality indicators includes marking the first instruction region as non-temporal and the second instruction region as temporal. 
     
     
         15 . The method of  claim 10 , wherein determining the first and second temporal locality indicators includes marking the first and second instruction regions with numerical values represent the likelihoods that instructions included in the first and second instruction regions will be re-executed while the instructions are stored in the cache structure, wherein the numerical value marking with the second instruction region is greater than the numerical value marking the first instruction region. 
     
     
         16 . A non-transitory, computer-readable medium storing instructions operable when executed to cause at least one processor to perform operations comprising:
 receiving a request for a first instruction included in a software application;   storing a first cache entry corresponding to the first instruction in a cache structure;   receiving a request for a second instruction included in the software application, the second instruction different than the first instruction;   in response to receiving a request for the second instruction, determining that a cache entry must be removed from the cache structure to create space to store a second cache entry corresponding to the second instruction;   in response to determining that a cache entry must be removed, determining that the first cache entry corresponding to the first instruction should be removed from the cache structure based on temporal locality attributes associated with at least one of the first instruction or the second instruction, the temporal locality attributes representing a likelihood that additional requests will be received for an associated instruction while the instruction is stored in a cache structure;   in response to determining that the first cache entry corresponding to the first instruction should be removed, removing the first cache entry from the cache structure; and   in response to removing the first cache entry, storing the second cache entry in the cache structure.   
     
     
         17 . The computer-readable medium of  claim 16 , wherein storing the first cache entry includes storing the first cache entry in the cache structure at a particular priority level based on the temporal locality attributes, and the determination that the first cache entry should be removed is based at least in part on the particular priority level. 
     
     
         18 . The computer-readable medium of  claim 16 , wherein the first cache entry includes a temporal flag indicating whether the first cache entry is likely to be accessed, and the operations further comprise:
 setting the value of the temporal flag of the first cache entry based on the temporal locality attributes, wherein the determination that the first cache entry should be removed is based at least in part on the value of the temporal flag.   
     
     
         19 . The computer-readable medium of  claim 16 , wherein the first cache entry includes a use flag indicating whether the first cache entry has been accessed within the cache, the determination that the first cache entry should be removed is based at least in part on the use flag. 
     
     
         20 . A system comprising:
 memory for storing data; and   one or more processors operable to perform operations comprising:
 receiving a request for a first instruction included in a software application; 
 storing a first cache entry corresponding to the first instruction in a cache structure; 
 receiving a request for a second instruction included in the software application, the second instruction different than the first instruction; 
 in response to receiving a request for the second instruction, determining that a cache entry must be removed from the cache structure to create space to store a second cache entry corresponding to the second instruction; 
 in response to determining that a cache entry must be removed, determining that the first cache entry corresponding to the first instruction should be removed from the cache structure based on temporal locality attributes associated with at least one of the first instruction or the second instruction, the temporal locality attributes representing a likelihood that additional requests will be received for an associated instruction while the instruction is stored in a cache structure; 
 in response to determining that the first cache entry corresponding to the first instruction should be removed, removing the first cache entry from the cache structure; and in response to removing the first cache entry, storing the second cache entry in the cache structure.