Abstract:
A method of operating a sub-sector cache includes receiving a request for a first sub-sector of a first cache line. The method further includes identifying a first replaced line in a cache data RAM, the first replaced line including a plurality of replaced sub-sectors. The method further includes storing the first sub-sector in the cache data RAM in place of a first replaced sub-sectors and storing an identifier of at least a second replaced sub-sector in a victim sector tag buffer.

Description:
[0001]     This is a continuation of application Ser. No. 10/365,636 filed Feb. 13, 2003, the contents of which are incorporated herein by reference. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention is directed to computer cache memory. More particularly, the present invention is directed to a cache memory having sectors and a victim sector tag buffer.  
       BACKGROUND INFORMATION  
       [0003]     Advances in computer processor speeds increasingly highlight a growing gap between the relatively high speed of the computer processors and the relatively low speed of computer memory systems. If a computer processor is constantly waiting for data from the memory system, the speed of the processor cannot always be utilized.  
         [0004]     One way to increase the speed of a computer memory system is to improve the memory hierarchy design of the computer memory system. Computer memory systems typically include different levels of memory, including fast cache memory, slower main memory, and even slower disk memory. Improved designs of cache memory increase the likelihood of a cache memory “hit”, which avoids the time penalty of having to retrieve data from main memory.  
         [0005]     One improved type of cache memory is sector cache. With sector cache, a cache “line” is divided into sub-sectors. One example of sector cache is found on the Pentium 4 processor from Intel Corp. The Pentium 4 processor includes an L2 cache which has a 128-byte long cache line that is divided into two 64-byte sub-sectors.  
         [0006]     With sector cache, a cache line miss results in all sub-sectors of the cache line being marked as “invalid” using an invalid bit. However, only a single sub-sector is read on a miss. Therefore, the remaining sub-sectors of the line continue to have invalid or unusable data that takes up space in the cache memory.  
         [0007]     Based on the foregoing, there is a need for an improved cache memory system having sub-sectors. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]      FIG. 1  is a block diagram of a computer system that includes a cache in accordance with one embodiment of the present invention.  
         [0009]      FIG. 2  provides an example of the storage of sub-sector tags in a victim sector tag buffer in accordance with one embodiment of the present invention.  
         [0010]      FIG. 3  illustrates a sequence of streaming accesses that are handled by a victim sector tag buffer in accordance with one embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0011]     One embodiment of the present invention is a cache that includes a victim sector tag (“VST”) buffer. The VST buffer identifies sub-sectors of replaced lines that include valid data, despite the presence of an “invalid” flag for that sub-sector.  
         [0012]      FIG. 1  is a block diagram of a computer system  40  that includes a cache  10  in accordance with one embodiment of the present invention. Computer system  40  includes a processor  20 , cache  10  and a memory bus  24 . Processor  20  can be any type of general purpose processor. Cache  10  may be integrated within processor  20 , or external to processor  20  as shown in  FIG. 1 . Memory bus  24  connects processor  20  and cache  10  to the remaining memory sub-system of computer system  40 . Memory that may be coupled to memory bus  24  may include additional cache memory, random access memory (“RAM”), read-only memory (“ROM”), disk-drive memory, or any type of memory that may be present in a computer system.  
         [0013]     Cache  10  includes a cache data RAM  16 . Cache data RAM  16  stores cache data that is received either from processor  20 , or from memory coupled to memory bus  24 . In one embodiment, the data stored in cache data RAM  16  is stored in the form of cache “lines”, which are blocks of data. Each cache line is divided into multiple sub-sectors (i.e., sub-sector  22  and sub-sector  24 ).  
         [0014]     Cache  10  further includes a cache tag RAM  12 . Cache tag RAM  12  stores “tags” or identifiers of each line stored in cache data RAM  16 , and the corresponding location in cache data RAM  16  where the line is stored. For example, the first line in cache data RAM  16  may have a tag of “A” and may be stored in location 0200. Further, the second line in cache data RAM  16  may have a tag of “B” and may be stored in location 0400.  
         [0015]     Cache  10  further includes a valid bits module  14 . Valid bits module  14  stores a “valid” bit for each sub-sector of each line stored in cache data RAM  16 . The valid bit indicates whether the corresponding sub-sector includes valid or invalid data.  
         [0016]     Cache  10  further includes a VST buffer  18 . VST buffer  18  stores entries which indicate when a sub-sector of a line stored in cache data RAM  16 , which is marked as an invalid sector by valid bits module  14 , actually stores valid data which can be used by processor  20 .  
         [0017]     Cache data RAM  16 , Cache tag RAM  12  and valid bits module  14  generally operate as the prior art equivalent modules that implement a sub-sector cache system. In general, this operation begins when processor  20  requests a sub-sector of a line of data stored in memory. The memory request is processed by cache  10  by first identifying the tag of the line requested. The presence of the tag is searched in cache tag RAM  12 . If the desired tag exists, the valid bit for the requested sub-sector of the line is queried in valid bits module  14 . If the requested sub-sector is valid, then that sub-sector is retrieved from cache data RAM  16  and sent to processor  20 .  
         [0018]     A cache miss may occur if either the desired tag is not found in cache tag RAM  12  (i.e., the desired line is not in cache data RAM  16 ), or the requested sub-sector is invalid. When a cache miss occurs, one of the lines in cache data RAM  16  is designated as a “replaced line”, and each sub-sector of the replaced line is marked as “invalid” in valid bits module  14  (and can be referred to as “replaced sub-sectors”). The requested sub-sector is then retrieved from memory bus  24  and stored in place of the corresponding sub-sector of the replaced line. The corresponding cache tag and valid bit is also updated. The remaining sub-sectors of the replaced line are not changed, but in prior art systems they remain unusable because these sub-sectors remain marked as invalid in valid bits module  14 .  
         [0019]     In one embodiment of the present invention, VST buffer  18  stores the sub-sector tags of recently replaced lines that include usable data.  FIG. 2  provides an example of the storage of sub-sector tags in VST  18  in accordance with one embodiment of the present invention.  
         [0020]     At box  100 , tag A cache line, identified at  101 , includes two valid sub-sectors (identified by the two “V”s)  
         [0021]     At box  110 , processor  20  requests the first sub-sector of tag B cache line. Tag B is not stored in cache data RAM  16 . Therefore, tag A cache line is designated as the replaced line and both sub-sectors are marked as invalid, The first sub-sector of tag B cache line is then retrieved and stored in cache data RAM  16  in place of tag A cache line. As identified at  111 , tag B cache line has valid data in its first sub-sector, and invalid data in its second sub-sector. However, the data in the second sub-sector is in fact valid data of the second sub-sector of tag A cache line. Consequently, an entry  112  is stored in VST buffer  18  that indicates that the second half sub-sector of tag B cache line includes valid data for tag A.  
         [0022]     At box  120 , processor  20  requests the second sub-sector of tag A cache line. The first check of cache tag RAM  12  results initially in a cache miss because tag A cache line was replaced by tag B cache line at box  110 . However, VST buffer  18  is then queried, and entry  112  indicates that the data is available at the second half of tag B cache line. Consequently, the requested data is retrieved from tag B cache line (indicated by shaded portion of  111 ) and a cache miss is avoided.  
         [0023]     In other embodiments, VST buffer  18  can be queried before the requested cache line tag is searched in cache tag RAM  12 .  
         [0024]     The existence of VST buffer  18  in accordance with embodiments of the present invention prevents some cache misses, thus increasing the efficiency of cache  10 . Unlike the traditional data buffers, VST buffer  18  buffers the sector tags that have been replaced out of the cache recently, so that valid data still stored in the cache can be used.  
         [0025]     In order to provide an example of the advantages of embodiments of the present invention, simulation studies were done using a cache hierarchy of 8 KB direct level  1  (“DL1”), a cache line size of 32-byte, an 8-way associate level  2  (“L2”) cache size of 512 KB, the L 2  using a least recently used (“LRU”) replacement policy with a 128-byte long cache line, and a 64-byte long sub cache line. All extra actions related with the VST buffer, including insert update and remove, are performed when there is a cache miss (whole cache line miss or sub-sector miss), so the VST buffer will not influence the cache hit penalty. The efficiency of the VST buffer can be computed from the following formula: 
 
[cache misses save rate=(cache misses of sector cache−cache misses of sector cache with VST buffer)/(cache misses of sector cache−cache misses of non-sector cache)]
 
         [0026]     Where “non-sector cache” is a 512 KB size, 64-byte cache line size, 8-way associative L 2  cache with LRU replacement policy. Several benchmarks are used for the evaluation: “mesa”, “art” and “ammp” from the Spec2K organization, and a commercial-like workload “LVCSR” which is a speech recognition system.  
         [0027]     The following cache misses save rate of a VST buffer of Table 1 in accordance with one embodiment of the present invention was obtained with an LRU replaced VST buffer:  
                                                                           TABLE 1                           cache misses save rate of the victim sector tag buffer                8   16   32   64   128   256           entries   entries   entries   entries   entries   entries                        LVCSR   0.38%   0.73%   1.36%   2.64%   4.91%   8.31%       Mesa   4.54%   5.04%   6.43%   9.01%   9.40%   9.49%       Ammp   3.84%   5.95%   8.88%   13.1%   18.3%   25.1%       Art   20.9%   29.4%   43.2%   59.5%   69.8%    151%                  
 
         [0028]     One embodiment of a VST buffer can be implemented using the following software or hardware code of Table 2:  
                                                                                                                                                                         TABLE 2                       Victim sector tag buffer handling code when cache misses                                if ((blockmiss == 0) &amp;&amp; (miss == 1)) { //cache line hit, sub sector miss,                if (ExistVSTbuffer == 1 &amp;&amp; FitforVSTbuffer == 1) {//fit for Vbuffer           currently &amp; victim buffer exists                int match;           match = indexBufSaddr(c,           D4ADDR2SUBBLOCK(c,m.address));            //Search the victim buffer via the subblockaddr            //if find, the sub-sector is buffered by VST buffer and            will be replaced soon, disable the VST entry           if (match &gt;= 0) disableVbufferEntry(c, match);                 }            }                ................................            if (blockmiss == 1) { //whole cache line miss                if (ExistVSTbuffer == 1 &amp;&amp; FitforVSTbuffer == 1) {//fit for Vbuffer           currently &amp; victim buffer exists                match = indexBufVaddr(c,           D4ADDR2SUBBLOCK(c,m.address));           //search the victim buffer via the victimaddr           if(match &gt;= 0) { //if find, means the sub-sector are actually           in cache, VST can help to identify them                ptr = reverseVbufferEntry(c,match);                 //revise the victim buffer, cache structure           if (ptr != NULL) {                blockmiss = 0;                 miss = 0; //identify a hit here                 }                }                }            }                  
 
         [0029]     Embodiments of the present invention also provide advantages over prior art victim buffer systems when a number of streaming (or sequential) accesses are going to the cache. With prior art victim buffer systems, many cache lines will be evicted which will thrash the victim buffer.  
         [0030]      FIG. 3  illustrates a sequence of streaming accesses that are handled by a VST buffer in accordance with one embodiment of the present invention. At  200 , the VST buffer (assuming a ½ sector cache) is empty. At  210 , after a “read add1” instruction, a VST buffer entry is created. At  220 , after a “read add1+subsectorsize” instruction, the VST buffer entry is disabled. Finally, at  230 , after a “read add1+subsectorsize*2” instruction, an additional buffer entry in the VST buffer is created in the same space as the previous VST buffer entry, without influencing other VST buffer entries. Therefore, as shown, the VST buffer is not thrashed during the streaming of instructions.  
         [0031]     Several embodiments of the present invention are specifically illustrated and/or described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.