Method and apparatus for indexing a cache

Abstract

A method for indexing a cache includes searching on a cache index using a partial physical address, the partial physical address including any bits of the virtual address which are untranslated between the virtual address and the physical address. The partial physical address is used to identify a block of the cache index sets that might contain an address of requested data. The identification is performed prior to translation of the virtual address to the physical address. Once identified, the block is read out into an auxiliary memory structure. After the full physical address becomes available, the block is multiplexed down to one set, and a compare is performed on the ways of the set to determine if the requested data is in the cache and, if so, which way the data is in. A device for achieving the method includes a cache index organized into two arrays, each having a number of sets and a number of ways. One of the arrays may used to store micro-tags for way prediction. In addition, the device includes an auxiliary memory structure for receiving and storing intermediate search results.

What is claimed is:  
     
         1 . A cache index, comprising: 
 a first array for storing a plurality of first partial address tags, the first array organized into a plurality of first-array sets, the plurality of first-array sets organized into a plurality of blocks, each of the plurality of blocks containing a subset of the plurality of first-array sets, each of the plurality of first-array sets containing a plurality of ways, each of the plurality of ways of the first-array sets containing one of the plurality of first partial address tags; and    an auxiliary memory structure.    
     
     
         2 . The cache index according to  claim 1 , further comprising a control block, the control block receiving a first string of bits, the first string of bits being untranslated between a virtual address and a physical address, the control block using the first string of bits to identify a selected one of the plurality of blocks, the selected one of the plurality of blocks being read into the auxiliary memory structure; 
 the control block receiving a second string of bits and using the second string of bits to multiplex the subset of first-array sets contained in the selected one of the plurality of blocks down to a selected first-array set; and    the control block receiving a third string of bits and comparing the third string of bits on each of the plurality of ways contained in the selected first-array set, a hit being predicted when the third string of bits matches one of the first partial address tags contained in the selected first-array set.    
     
     
         4 . The cache index according to  claim 2 , wherein the first string of bits is a 5-bit string.  
     
     
         5 . The cache index according to  claim 4 , wherein the first string of bits includes bits  7 - 11  of the virtual address.  
     
     
         6 . The cache index according to  claim 2 , further comprising a second array for storing a plurality of second partial address tags, the second array organized into a plurality of second-array sets, each of the second-array sets containing a plurality of ways, each of the plurality of ways of the second-array sets containing one of the plurality of second partial address tags; 
 the control block identifying a corresponding second-array set using the first and second strings of bits; and    the control block receiving a fourth string of bits and comparing the fourth string of bits on each of the ways contained in the corresponding second-array set, a hit being confirmed when the fourth string of bits matches one of the second partial address tags contained in the corresponding second-array set.    
     
     
         7 . The cache index according to  claim 6 , wherein the first string of bits is a 5-bit string.  
     
     
         8 . The cache index according to  claim 7 , wherein the first string of bits includes bits  7 - 1   1  of the virtual address.  
     
     
         9 . The cache index according to  claim 8 , wherein each of the plurality of first partial address tags is a 9-bit string and each of the plurality of second partial address tags is a 12-bit string.  
     
     
         10 . The cache index according to  claim 8 , wherein the first string of bits includes bits  7 - 11  of the virtual address and the second string of bits includes bits  12 - 14  of the physical address.  
     
     
         11 . A method for searching a cache index, the cache index organized into blocks each containing a plurality of sets, each of the plurality of sets containing at least one way, each of the ways containing an address tag, comprising the steps of: 
 a. receiving a virtual address of a requested data element which has at least one common bit, the common bit being untranslated between the virtual address and a physical address; and    b. searching the cache index using the at least one common bit, before the virtual address is completely translated, to identify a selected block.    
     
     
         12 . The method according to  claim 11 , further comprising the steps of: 
 c. reading out the selected block into an auxiliary data structure;    d. receiving a first string of translated bits and a second string of translated bits;    e. multiplexing the selected block using the first string of translated bits to identify a single selected set that might contain the requested address tag;    f. comparing the second string of translated bits on the at least one way contained within the single selected set to determine if the requested data is in the cache; and    g. shipping a predicted way to the cache when the second string of translated bits matches one of the at least one address tags contained in the single selected set.    
     
     
         13 . The method according to  claim 12 , further comprising the following step, which is performed concurrent with steps (b) and (c) and prior to step (d): 
 h. translating a remainder of the virtual address to generate a remainder of the physical address, the remainder of the physical address including the first string of translated bits and the second string of translated bits.    
     
     
         14 . The method according to  claim 13 , wherein the at least one common bit includes bits  7 - 11  of the virtual address.  
     
     
         15 . A method for searching a cache index connected to a cache, the cache index comprising a first array and a second array, the first array organized into a plurality of first-array sets and the second array organized into a plurality of second-array sets, each of the first-array sets and the second-array sets containing at least one way, the ways of the first array containing micro address tags and the ways of the second array containing confirmation address tags, comprising the steps of: 
 a. receiving a virtual address of a requested data element which includes at least one common bit untranslated from a bit in a physical address;    b. searching on the first array using the at least one common bit, before the virtual address is completely translated, to identify a selected block of the plurality of first-array sets; and    c. reading out the selected block into an auxiliary data structure.    
     
     
         16 . The method according to  claim 15 , further comprising the steps of: 
 d. receiving a first string of translated bits and a second string of translated bits;    e. multiplexing the selected block using the first string of translated bits to identify a single potential first-array set;    f. comparing the second string of translated bits on the at least one way contained within the single potential first-array set, a hit being predicted when the second string of bits matches one of the micro address tags contained within the single selected set; and    g. shipping an identity of a predicted way to the second array and the cache when the second string of bits matches one of the micro address tags contained within the single selected set, the predicted way being located in the cache.    
     
     
         17 . The method according to  claim 16 , further comprising the following step, which is performed while steps (e), (f), and (g) are performed: 
 h. identifying and reading out from the second array a corresponding second-array set.    
     
     
         18 . The method according to  claim 17 , further comprising the following step, which is performed while steps (e), (f), and (g) are performed: 
 i. identifying and reading out a corresponding data set from the cache, the corresponding data set containing the predicted way.    
     
     
         19 . The method according to  claim 18 , further comprising the following step: 
 j. reading out predicted data from the cache, the predicted data being contained in the predicted way.    
     
     
         20 . The method according to  claim 19 , further comprising the following steps, which are performed concurrent with step (j): 
 k. receiving a third string of translated bits; and    l. comparing the third string of translated bits on the at least one way of the corresponding second-array set, a hit being confirmed when the third string of translated bits matches one of the confirmation address tags contained within the corresponding second array set.    
     
     
         21 . The method according to  claim 20 , further comprising the following step, which is preformed concurrent with steps (b) and (c) and prior to step (d): 
 m. translating a remainder of the virtual address to generate a remainder of the physical address, the remainder of the physical address including the first string of translated bits, the second string of translated bits, and the third string of translated bits.    
     
     
         22 . The method according to  claim 20 , wherein the at least one common bit includes bits  7 - 11  of the virtual address.  
     
     
         23 . The method according to  claim 22 , wherein the first string of translated bits includes bits  12 - 14  of the physical address, the second string of translated bits includes bits  15 - 23  of the physical address, and the third string of translated bits includes bits  24 - 35  of the physical address.