Highly efficient design of storage array utilizing multiple pointers to indicate valid and invalid lines for use in first and second cache spaces and memory subsystems

Abstract

A method of operating a cache memory includes the step of storing a set of data in a first space in a cache memory, a set of data associated with a set of tags. A subset of the set of data is stored in a second space in the cache memory, the subset of the set of data associated with a tag of a subset of the set of tags. The tag portion of an address is compared with the subset of data in the second space in the cache memory in that said subset of data is read when the tag portion of the address and the tag associated with the subset of data match. The tag portion of the address is compared with the set of tags associated with the set of data in the first space in cache memory and the set of data in the first space is read when the tag portion of the address matches one of the sets of tags associated with the set of data in the first space and the tag portion of the address and the tag associated with the subset of data in the second space do not match.

What is claimed is: 
     
       1. A method of operating a cache memory comprising the steps of:
 storing a set of data in a first space in the cache memory, the set of data associated with a set of tags, the set of data in the first space in the cache memory being comprised of a first plurality of cache lines, each cache line in the first plurality of cache lines being associated with a valid indicator indicative as to whether data associated with the cache line is valid; 
 maintaining a first pointer to a location in the first space in the cache memory, the first pointer referencing a first cache line in the first space in the cache memory; 
 maintaining a second pointer to a location in the first space in the cache memory, the second pointer referencing a second cache line in the first space in the cache memory; 
 storing a subset of the set of data in a second space in the cache memory and associated with a tag, the tag associated with the subset of data and being a subset of the set of tags, the set of data in the second space in the cache memory being comprised of a second plurality of cache lines, each cache line in the second plurality of cache lines being associated with a valid indicator indicative as to whether data associated with the cache line is valid; 
 wherein one of the second plurality of the cache lines is associated with the tag associated with the subset of data; 
 comparing a tag portion of an address with the tag associated with the subset of data in the second space in the cache memory; 
 reading the subset of data in the second space when the tag portion of the address and the tag associated with the subset of data match; 
 comparing the tag portion of the address with the set of tags associated with the set of data in the first space in the cache memory; and 
 reading the set of data in the first space when the tag portion of the address matches one of the set of tags associated with the set of data in the first space and the tag portion of the address and the tag associated with the subset of data in the second space do not match. 
 
     
     
       2. The method of  claim 1  further comprising the steps of:
 when the tag portion of the address matches does not match one of the set of tags associated with the set of data in the first space, storing a second set of data in the first space in cache memory and associated with a second set of tags, the second set of data including a second subset of data associated with a tag matching the tag portion of the address; and 
 storing the second subset of data in the second space in the cache memory tagged with the tag matching the tag portion of the address. 
 
     
     
       3. The method of  claim 1  further comprising the steps of:
 during a write operation, comparing the tag portion of the write address with the set of tags associated with the set of data in the first memory space; and 
 if the tag portion of the write address matches one of the set of tags associated with the set of data in the first memory space, overwriting the data in the first memory space associated with the matching tag. 
 
     
     
       4. The method of  claim 3  and further comprising the steps of:
 if the tag portion of the write address does not match one of the set of tags associated with the set of data in the first space in the cache memory, retrieving the data associated with the tag portion of the write address from a second memory; and 
 storing the retrieved data in the first space of the cache memory tagged with a tag corresponding to the tag portion of the write address. 
 
     
     
       5. The method of  claim 2  wherein said step of storing the second set of data in the first space in the cache memory comprises the step of storing the second set of data in a least recently used set of locations in the first space. 
     
     
       6. The method of  claim 2  wherein said step of storing the second set of data in the first space in the cache memory comprises the step of storing the second set of data in a randomly selected set of locations in the first space. 
     
     
       7. The method of  claim 4  wherein said step of storing the retrieved data comprises the step of storing the retrieved data at a least recently used set of locations in the first space. 
     
     
       8. The method of  claim 4  wherein said step of storing the retrieved data comprises the step of storing the retrieved data at a randomly selected set of locations in the first space. 
     
     
       9. A processing system comprising:
 a system memory; 
 a cache memory comprising first and second peer cache memory spaces; 
 a first table for storing tags associated with data stored in the first cache memory space; 
 a second table for storing tags associated with data stored in the second cache memory space; 
 processing circuitry operable to:
 access a plurality of blocks of data from said system memory in response to a plurality of addresses; 
 store said blocks of data accessed from said system memory within said first cache memory space, said blocks of data associated with a set of tags in said first table, said blocks further being associated with a set of valid indicators, each valid indicator indicating whether data associated with a particular block is valid; 
 maintain a first pointer to a location in the first cache memory space, the first pointer referencing a first block in the first space in the cache memory; 
 maintain a second pointer to a location in the first cache memory space, the second pointer referencing a second block in the first space in the cache memory; 
 store a selected block of said blocks of data accessed from said system memory within said second cache memory space, the selected block being associated with a valid indicator indicative of whether the data associated with the block is valid, and said block associated with a tag in said second table; 
 generate a read address including a tag field; 
 compare said tag field of said read address with said tag in said second table associated with said selected block and access said selected block from said second cache memory space when said tag field and said tag in said second table match; and 
 compare said tag field of said read address with said set of tags in said first table when said tag field and said tag in said second table do not match and access a corresponding block in said first cache memory space when said tag field and a tag in said first table match. 
 
 
     
     
       10. The processing system of  claim 9  wherein said processing circuitry is further operable when said tag field does not match a tag in the first table to:
 retrieve a second plurality of blocks of data from said system memory; 
 store the second plurality of blocks of data in the first cache memory space, the second plurality of blocks associated with a second set of tags in said first table; and 
 store a second selected block of the second plurality of blocks in said second cache memory space, said second selected block associated with a second tag in said second table matching said tag field of said address. 
 
     
     
       11. The processing system of  claim 9  wherein said processing circuitry is further operable to:
 generate a write address including a tag field; 
 compare said tag field of said write address with the set of tags in the first table; and 
 overwrite data in the first memory space associated with a corresponding tag in the first table matching said tag field of said write address associated with a set of tags; 
 storing a subset of the set of data in a second space in the cache memory and associated with a tag, the tag associated with the subset of data being a subset of the set of tags; 
 comparing a tag portion of an address with the tag associated with the subset of data in the second space in the cache memory; 
 reading the subset of data in the second space when the tag portion of the address and the tag associated with the subset of data match; 
 comparing the tag portion of the address with the set of tags associated with the set of data in the first space in the cache memory; and 
 reading the set of data in the first space when the tag portion of the address matches one of the set of tags associated with the set of data in the first space and the tag portion of the address and the tag associated with the subset of data in the second space do not match. 
 
     
     
       12. The processing system of  claim 9  wherein said second cache memory space is smaller than said first cache memory space. 
     
     
       13. The processing system of  claim 9  wherein said cache memory system comprise a discrete cache memory system. 
     
     
       14. The processing system of  claim 9  wherein said cache memory system comprises an on-board cache memory system integrated with said processing circuitry. 
     
     
       15. The processing system of  claim 9  wherein said processing circuitry comprises a central processing unit. 
     
     
       16. The processing system of  claim 9  wherein said processing circuitry comprises a cache memory controller. 
     
     
       17. The method of claim 3 further comprising the steps of:
 comparing the tag portion of the write address with the tag associated with the subset of the set of data; and   when the tag portion of the write address matches the tag associated with the subset of the set of data, changing the valid indicator of the cache line associated with the tag associated with the subset of the set of data to indicate that the data associated with the cache line is invalid.   
     
     
       18. The method of claim 1 further comprising the steps of:
 writing data associated with a write address from a processor coupled to the cache memory to a memory location associated with the first cache line in the first space in the cache memory;   comparing the tag portion of the write address with the tag associated with the subset of the set of data stored in the second space in the cache memory; and   setting the valid indicator of the cache line associated with the tag to indicate that the data associated with the cache line is invalid when the tag portion of the write address matches the tag associated with the subset of the set of data.   
     
     
       19. The method of claim 1 further comprising the steps of:
 when the tag portion of the address does not match one of the set of tags associated with the set of data in the first space, storing a second set of data to a memory location associated with the second cache line in the first space in the cache memory; and   incrementing the second pointer to reference a third cache line in the first space in the cache memory.   
     
     
       20. The method of claim 19 further comprising the step of writing data associated with a write address from a processor coupled to the cache memory to a memory location associated with the first cache line in the first space in the cache memory. 
     
     
       21. The method of claim 20 further comprising the steps of:
 maintaining a third pointer to a location in the second space in the cache memory, the third pointer referencing a first cache line in the second memory space; and   storing a subset of the second set of data to a memory location associated with the first cache line in the second memory space.   
     
     
       22. The method of claim 20 further comprising the step of incrementing the first pointer to reference a fourth cache line wherein the valid indicator associated with the fourth cache line indicates that the data associated with the fourth cache line is invalid. 
     
     
       23. The method of claim 20 further comprising the steps of:
 comparing the tag portion of the write address with the tag associated with the subset of the set of data stored in the second space in the cache memory; and   setting the valid indicator of the cache line associated with the tag to indicate that the data associated with the cache line is invalid when the tag portion of the write address matches the tag associated with the subset of the set of data.   
     
     
       24. The method of claim 23 wherein the associativity of the first space in the cache memory and the second space of the cache memory is dynamic. 
     
     
       25. The method of claim 1 wherein the cache memory is part of a multiprocessor system. 
     
     
       26. The method of claim 1 wherein the cache memory is implemented using DRAM. 
     
     
       27. The method of claim 1 wherein the cache memory is implemented using SRAM. 
     
     
       28. The method of claim 1 wherein the cache memory is implemented using multi-ported memory. 
     
     
       29. The method of claim 1 further comprising the steps of:
 prefetching data into the first space in the cache memory; and   responding to a read request from a processor coupled to the cache memory with data from the second space in the cache memory.   
     
     
       30. The method of claim 1 further comprising the steps of:
 reading data associated with the cache line referenced by the second pointer; and   at substantially the same time writing data to the cache line referenced by the first pointer.   
     
     
       31. The system of claim 9 further comprising:
 a processor coupled to the cache memory;   the processing circuitry being further operable to write data associated with a write address from the processor to the block referenced by the first pointer, compare the tag portion of the write address with the tag in said second table, and set the valid indicator associated with the block associated with the tag in said second table when the tag portion of the write address matches the tag in said second table.   
     
     
       32. The system of claim 9 wherein the processing circuitry is further operable when the tag portion of the read address does not match one of the set of tags stored in said first table, store a second set of blocks of data to a memory location referenced by the second pointer, and increment the second pointer to reference a third block in the first space in the cache memory. 
     
     
       33. The system of claim 32 wherein the processing circuitry is further operable to write data associated with a write address from the processor to the block referenced by the first pointer. 
     
     
       34. The system of claim 33 wherein the processing circuitry is further operable to:
 maintain a third pointer to a second block within the second cache memory space;   store a block of data that is a subset of the second set of blocks of data within the block referenced by the third pointer.   
     
     
       35. The system of claim 33 wherein the processing circuitry is further operable to increment the first pointer to reference a fourth block wherein the valid indicator associated with the fourth block indicates that the data associated with the fourth block is invalid. 
     
     
       36. The system of claim 33 wherein the processing circuitry is further operable to:
 compare the tag portion of the write address with the tag stored in the second table; and   set the valid indicator associated with the block associated with the tag stored in the second table to indicate that the data associated with the block is invalid when the tag portion of the write address matches the tag associated stored in the second table.   
     
     
       37. The system of claim 36 wherein the associativity of the first space in the cache memory and second space in the cache memory is dynamic. 
     
     
       38. The system of claim 9 further comprising a first processor coupled to the cache memory, and a second processor coupled to the cache memory. 
     
     
       39. The system of claim 9 wherein the cache memory is implemented using DRAM. 
     
     
       40. The system of claim 9 wherein the cache memory is implemented using SRAM. 
     
     
       41. The system of claim 9 wherein the cache memory is implemented using multi-ported memory. 
     
     
       42. The system of claim 9 further comprising:
 prefetching circuitry operable to prefetch data into the first space in the cache memory; and wherein the processing circuitry is further operable to respond to a read request with data from the second space in the cache memory.   
     
     
       43. The system of claim 9 further comprising:
 a processor coupled to the cache memory; and   wherein the processing circuitry is further operable to read data associated with the block referenced by the second pointer; and   at substantially the same time write data to the block referenced by the first pointer.   
     
     
       44. A method of operating a cache memory comprising the steps of:
 storing a set of data in a first space in the cache memory, the set of data associated with a set of tags, the set of data in the first space in the cache memory being comprised of a first plurality of cache lines, each cache line in the first plurality of cache lines being associated with a valid indicator indicative as to whether data associated with the cache line is valid;   storing a subset of the set of data in a second space in the cache memory and associated with a tag, the tag associated with the subset of data and being a subset of the set of tags, the set of data in the second space in the cache memory being comprised of a second plurality of cache lines, each cache line in the second plurality of cache lines being associated with a valid indicator indicative as to whether data associated with the cache line is valid;   wherein one of the second plurality of the cache lines is associated with the tag associated with the subset of data;   comparing a tag portion of an address with the tag associated with the subset of data in the second space in the cache memory;   reading the subset of data in the second space when the tag portion of the address and the tag associated with the subset of data match;   comparing the tag portion of the address with the set of tags associated with the set of data in the first space in the cache memory; and   reading the set of data in the first space when the tag portion of the address matches one of the set of tags associated with the set of data in the first space and the tag portion of the address and the tag associated with the subset of data in the second space do not match;   writing data associated with a write address from a processor coupled to the cache memory to a memory location of the first space in the cache memory;   comparing the tag portion of the write address with the tag associated with the subset of the set of data stored in the second space in the cache memory;   setting the valid indicator of the cache line associated with the tag to indicate that the data associated with the cache line is invalid when the tag portion of the write address matches the tag associated with the subset of the set of data;   maintaining a first pointer to a location in the first space in the cache memory, the first pointer referencing a first cache line in the first space in the cache memory; and   maintaining a second pointer to a location in the first space in the cache memory, the first pointer referencing a second cache line in the first space in the cache memory, wherein the valid indicator associated with the second cache line indicates that the data associated with the second cache line is invalid.   
     
     
       45. The method of claim 44 further comprising the steps of:
 when the tag portion of the address does not match one of the set of tags associated with the set of data in the first space, storing a second set of data to a memory location associated with the second cache line in the first space in the cache memory;   incrementing the second pointer to reference a third cache line in the first space in the cache memory;   maintaining a third pointer to a location in the second space in the cache memory, the third pointer referencing a first cache line in the second memory space; and   storing a subset of the second set of data to a memory location associated with the first cache line in the second memory space.   
     
     
       46. The method of claim 45 further comprising the steps of:
 comparing the tag portion of the write address with the tag associated with the subset of the set of data stored in the second space in the cache memory; and   setting the valid indicator of the cache line associated with the tag to indicate that the data associated with the cache line is invalid when the tag portion of the write address matches the tag associated with the subset of the set of data.   
     
     
       47. The method of claim 44 further comprising the steps of:
 reading data associated with the cache line referenced by the second pointer; and   at substantially the same time writing data to the cache line referenced by the first pointer.   
     
     
       48. A processing system comprising:
 a system memory;   a cache memory comprising first and second peer cache memory spaces;   a processor coupled to the cache memory;   a first table for storing tags associated with data stored in the first cache memory space;   a second table for storing tags associated with data stored in the second cache memory space;   processing circuitry operable to:
 access a plurality of blocks of data from said system memory in response to a plurality of addresses; 
 store said blocks of data accessed from said system memory within said first cache memory space, said blocks of data associated with a set of tags in said first table, said blocks further being associated with a set of valid indicators, each valid indicator indicating whether data associated with a particular block is valid; 
 store a selected block of said blocks of data accessed from said system memory within said second cache memory space, the selected block being associated with a valid indicator indicative of whether the data associated with the block is valid, and said block associated with a tag in said second table; 
 generate a read address including a tag field; 
 compare said tag field of said read address with said tag in said second table associated with said selected block and access said selected block from said second cache memory space when said tag field and said tag in said second table match; 
 compare said tag field of said read address with said set of tags in said first table when said tag field and said tag in said second table do not match and access a corresponding block in said first cache memory space when said tag field and a tag in said first table match; 
   the processing circuitry being further operable to write data associated with a write address from the processor to a block in the first cache memory space, compare the tag portion of the write address with the tag in said second table, and set the valid indicator associated with the block associated with the tag in said second table when the tag portion of the write address matches the tag in said second table; and   wherein the processing circuitry is further operable to:
 maintain a first pointer to a location in the first cache memory space, the first pointer referencing a first block in the first space in the cache memory; and 
   maintain a second pointer to a location in the first cache memory space, the second pointer referencing a second block in the first space in the cache memory wherein the valid indicator associated with the second block indicates that the associated with the second block is invalid.