Method and apparatus for application-specific dynamic cache placement

Abstract

One embodiment of the present method and apparatus for application-specific dynamic cache placement includes grouping sets of data in a cache memory system into two or more virtual partitions and processing a load/store instruction in accordance with the virtual partitions, where the load/store instruction specifies at least one of the virtual partitions to which the load/store instruction is assigned.

1 . A method for accessing data in a cache memory system, the method comprising:
 grouping sets of data in the cache memory system into two or more virtual partitions; and   processing a load/store instruction in accordance with the two or more virtual partitions, where the load/store instruction specifies at least one of the two or more virtual partitions to which the load/store instruction is assigned.   
   
   
       2 . The method of  claim 1 , wherein the processing comprises:
 checking at least a subset of the two or more virtual partitions for a data item referenced by the load/store instruction;   fetching the data item referenced by the load/store instruction from one of the two or more virtual partitions, if the data item is located therein and the load/store instruction specifies a load operation;   storing the data item referenced by the load/store instruction in one of the two or more virtual partitions, if the load/store instruction specifies a store operation; and   loading the data item to the at least one of the two or more virtual partitions to which the load/store instruction is assigned, if the data item is not located in the subset of the two or more virtual partitions.   
   
   
       3 . The method of  claim 2 , wherein the checking comprises:
 checking each of the two or more virtual partitions for the data item.   
   
   
       4 . The method of  claim 2 , wherein the checking comprises:
 identifying one or more sets in the cache memory system that comprise the at least one of the two or more virtual partitions to which the load/store instruction is assigned; and   checking the one or more sets for the data item.   
   
   
       5 . The method of  claim 2 , wherein the loading and storing comprises:
 selecting a virtual partition from among two or more virtual partitions to which the load/store instruction is assigned, in accordance with a cache replacement policy.   
   
   
       6 . The method of  claim 1 , wherein the at least one of the two or more virtual partitions to which the load/store instruction is assigned is specified by an identifier in the load/store instruction. 
   
   
       7 . The method of  claim 6 , wherein the load/store instruction comprises a number of extra bits for specifying the identifier. 
   
   
       8 . The method of  claim 6 , wherein the identifier is implemented as a prefix instruction to the load/store instruction, the prefix instruction specifying one or the two or more virtual partitions that is associated with a next sequential load/store instruction. 
   
   
       9 . The method of  claim 6 , wherein the identifier is specified in accordance with one or more registers implemented as operands of the load/store instruction. 
   
   
       10 . The method of  claim 1 , wherein the grouping comprises:
 identifying one or more load/store instructions that are encountered most frequently from among a plurality of load/store instructions;   identifying one or more data items accessed by the one or more load/store instructions;   modeling the one or more load/store instructions as a graph; and   assigning each of the one or more load/store instructions to at least one virtual partition in accordance with the graph.   
   
   
       11 . The method of  claim 10 , wherein the modeling comprises:
 dividing each of the one or more load/store instructions into one or more sub-instructions, each of the one or more sub-instructions comprising a node of the graph;   calculating an affinity metric for each pair of load/store instructions within the one or more load/store instructions;   calculating a conflict metric for each pair of load/store instructions; and   assigning weights to edges of the graph in accordance with the affinity metric and the conflict metric, the weights indicating whether each pair of load/store instructions should be assigned to a common virtual partition or to different virtual partitions.   
   
   
       12 . A computer readable medium containing an executable program for accessing data in a cache memory system, where the program performs the steps of:
 grouping sets of data in the cache memory system into two or more virtual partitions; and   processing a load/store instruction in accordance with the two or more virtual partitions, where the load/store instruction specifies at least one of the two or more virtual partitions to which the load/store instruction is assigned.   
   
   
       13 . The computer readable medium of  claim 12 , wherein the processing comprises:
 checking at least a subset of the two or more virtual partitions for a data item referenced by the load/store instruction;   fetching the data item referenced by the load/store instruction from one of the two or more virtual partitions, if the data item is located therein and the load/store instruction specifies a load operation;   storing the data item referenced by the load/store instruction in one of the two or more virtual partitions, if the load/store instruction specifies a store operation; and   loading the data item to the at least one of the two or more virtual partitions to which the load/store instruction is assigned, if the data item is not located in the subset of the two or more virtual partitions.   
   
   
       14 . The computer readable medium of  claim 13 , wherein the checking comprises:
 checking each of the two or more virtual partitions for the data item.   
   
   
       15 . The computer readable medium of  claim 13 , wherein the checking comprises:
 identifying one or more sets in the cache memory system that comprise the at least one of the two or more virtual partitions to which the load/store instruction is assigned; and   checking the one or more sets for the data item.   
   
   
       16 . The computer readable medium of  claim 12 , wherein the at least one of the two or more virtual partitions to which the load/store instruction is assigned is specified by an identifier in the load/store instruction. 
   
   
       17 . The computer readable medium of  claim 16 , wherein the load/store instruction comprises a number of extra bits for specifying the identifier. 
   
   
       18 . The computer readable medium of  claim 12 , wherein the grouping comprises:
 identifying one or more load/store instructions that are encountered most frequently from among a plurality of load/store instructions;   identifying one or more data items accessed by the one or more load/store instructions;   modeling the one or more load/store instructions as a graph; and   assigning each of the one or more load/store instructions to at least one virtual partition in accordance with the graph.   
   
   
       19 . The computer readable medium of  claim 18 , wherein the modeling comprises:
 dividing each of the one or more load/store instructions into one or more sub-instructions, each of the one or more sub-instructions comprising a node of the graph;   calculating an affinity metric for each pair of load/store instructions within the one or more load/store instructions;   calculating a conflict metric for each pair of load/store instructions; and   assigning weights to edges of the graph in accordance with the affinity metric and the conflict metric, the weights indicating whether each pair of load/store instructions should be assigned to a common virtual partition or to different virtual partitions.   
   
   
       20 . A cache controller for controlling access to a cache memory, the cache controller comprising:
 means for grouping sets of data in the cache memory system into two or more virtual partitions; and   means for processing a load/store instruction in accordance with the two or more virtual partitions, where the load/store instruction specifies at least one of the two or more virtual partitions to which the load/store instruction is assigned.