Energy optimized cache memory architecture exploiting spatial locality
Aspects of the present invention provide a “SuperTag” cache that manages cache at three granularities: (i) coarse grain, multi-block “super blocks,” (ii) single cache blocks and (iii) fine grain, fractional block “data segments.” Since contiguous blocks have the same tag address, by tracking multi-block super blocks, the SuperTag cache inherently increases per-block tag space, allowing higher compressibility without incurring high area overheads. To improve compression ratio, the SuperTag cache uses variable-packing compression allowing variable-size compressed blocks without requiring costly compactions. The SuperTag cache also stores data segments dynamically. In addition, the SuperTag cache is able to further improve the compression ratio by co-compressing contiguous blocks. As a result, the Super Tag cache improves energy and performance for memory intensive applications over conventional compressed caches.
1. A cache memory system comprising:
a cache memory storing a plurality of data segments, wherein the data segments are compressed from a multi-block including contiguous data blocks originating from a higher level of memory;
a tag, memory array coupled to the cache memory, wherein the tag memory array stores a plurality of tag addresses with each tag address corresponding to a multi-block originating from the higher level of memory; and
a back pointer array coupled to the cache memory and the tag memory array, wherein the back pointer array stores a plurality of back pointer entries with each back pointer entry corresponding to a data segment in the cache memory and each back pointer entry identifying a multi-block associated with a tag address in the tag memory array and a data block of the multi-block compressed to form the data segment;
wherein the data segments are stored non-contiguously in the cache memory.
2. The cache memory of claim 1 , wherein each tag address corresponds to four data blocks originating from the higher level of memory.
3. The cache memory of claim 2 , wherein a first data block is compressed with a second data block into one or more data segments.
4. The cache memory of claim 3 , wherein the first and second data blocks are from the same plurality of data blocks corresponding to a tag address.
5. The cache memory of claim 2 , further comprising each back pointer entry identifying a tag address in the tag memory array.
6. The cache memory of claim 1 , wherein four data segments compressed from four data blocks are stored non-contiguously in the cache memory.
7. The cache memory of claim 1 , wherein a data block is compressed using the C-PACK algorithm.
8. The cache memory of claim 1 , wherein the cache memory is a last level cache.
9. The cache memory of claim 1 , wherein the tag memory array stores a cache coherency state for each data block.
10. The cache memory of claim 1 , wherein the tag memory array stores a compression status for each data block.
11. The cache memory of claim 1 , wherein the tag memory array and the back pointer array are accessed in parallel during a cache lookup.
12. The cache memory of claim 1 , wherein each tag address corresponds to four contiguous data blocks.
13. A method for caching data in a computer system comprising:
(a) compressing a plurality of contiguous data blocks originating from a higher level of memory into a plurality of data segments, the plurality of contiguous data blocks being a multi-block;
(b) storing the plurality of data segments in a cache memory, the data segments being stored non-contiguously in the cache memo;
(c) storing a tag address in a tag memory array, the tag address corresponding to the multi-block originating from the higher level of memory; and
(d) storing a plurality of back pointer entries in a back pointer array, each of the plurality of back pointer entries corresponding to a data segment in the cache memory and a multi-block identifying a data block compressed to form the data segment, the multi-block being associated with a tag address in the tag memory array.
14. The method of claim 13 , further comprising compressing a first data block with a second data block into a plurality of data segments.
15. The method of claim 13 , further comprising compressing four data blocks to form four data segments, and storing the four data segments non-contiguously in the cache memory.
16. The method of claim 13 , further comprising compressing data blocks using the C-PACK algorithm.
17. The method of claim 13 , further comprising storing a cache coherency state for each data block in the tag memory array.
18. A computer system with a cache memory comprising:
a data array having a plurality of data segments;
a back pointer array having a plurality of back pointer entries, each back pointer entry corresponding to a data segment;
a tag array having a plurality of group identification entries, each group identification entry having a group identification number; and
a cache controller in communication with the data array, the back pointer array, the tag array and a higher level of memory, wherein the cache controller operates to:
(a) obtain from the higher level of memory a plurality of contiguous data blocks at a memory address, each of the plurality of contiguous data blocks receiving a sub-group identification number;
(b) compress the plurality of contiguous data blocks into a plurality of data segments;
(c) store the plurality of data segments in the data array, the data segments being stored non-contiguously in the data memory;
(d) store the memory address and the sub-group identification numbers in a group identification entry having a group identification number in the tag array; and
(e) in each back pointer entry corresponding to a stored data segment, store the group identification number and the sub-group identification numbers corresponding to the data block from which the stored data segment was compressed.
19. The computer system of claim 18 , wherein the cache controller further operates to compress a first data block with a second data block into a plurality of data segments.
20. The computer system of claim 18 , wherein four data segments compressed from four data blocks are stored non-contiguously in the data array.