Compression status bit cache and backing store

• US 8,700,862 B2
• Filed: 12/03/2008
• Issued: 04/15/2014
• Est. Priority Date: 12/03/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Glasco, David B., Holmqvist, Peter B., Lynch, George R., Marchand, Patrick R., Mehra, Karan, Roberts, James
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US12/327,790
• Publication Number:
  US 20100138614A1
• Time in Patent Office: 1,959 Days
• Field of Search: 711/118, 711/119, 711/120, 711/144, 711/147, 711/153, 711/154, 711/170, 711/173, 711/207
• US Class Current: 711/144
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

A compression status bit cache provides on-chip availability of compression status bits used to determine how many bits are needed to access a potentially compressed block of memory. A backing store residing in a reserved region of attached memory provides storage for a complete set of compression status bits used to represent compression status of an arbitrarily large number of blocks residing in attached memory. Physical address remapping (“swizzling”) used to distribute memory access patterns over a plurality of physical memory devices is partially replicated by the compression status bit cache to efficiently integrate allocation and access of the backing store data with other user data.

Claims

1. A plurality of intermediate caches coupled to one or more clients, each intermediate cache comprising:

a compression status bit cache configured to cache compression information for blocks of memory stored within a corresponding one of a plurality of portions of external memory; and

a data cache unit configured to request, in response to a cache miss in the data cache unit involving a first memory access request received from a first client, compressed data from the corresponding one of the plurality of portions of external memory based on compression information associated with the first memory access request and stored in either the compression status bit cache or a data structure residing in the corresponding one of the plurality of portions of external memory, wherein the compression information indicates the number of bits that comprise the compressed data, and wherein the compressed data comprises a reduced set of data for representing the requested data,

wherein each intermediate cache is coupled to the one or more clients via a memory crossbar and to the corresponding one of the plurality of portions of external memory, and

wherein each intermediate cache is configured to access at least one data surface and the data structure storing compression information for and residing in the corresponding one of the plurality of portions of external memory.

2. The plurality of intermediate caches of claim 1, each intermediate cache further comprising a command crossbar configured to route a command associated with the first memory access request received from the first client.

3. The plurality of intermediate caches of claim 2, each intermediate cache further comprising a data crossbar configured to route data associated with the first memory access request.

4. The plurality of intermediate caches of claim 3, each intermediate cache further comprising a set and tag unit configured to perform a first remapping operation on a memory address associated with the first memory access request to produce a first physical memory address for the first memory access request.

5. The plurality of intermediate caches of claim 4, wherein the compression status bit cache is configured to receive from a memory management unit a tag line associated with the first memory access request and to derive a cache tag from the tag line.

6. The plurality of intermediate caches of claim 5, wherein the tag line resides within a page table entry that is stored within the memory management unit and is generated during a virtual address to physical address translation performed by the memory management unit.

7. The plurality of intermediate caches of claim 6, wherein the compression status bit cache is configured to determine, based on the cache tag, whether the compression information associated with the first memory access request is currently stored within the compression status bit cache or the data structure.

8. The plurality of intermediate caches of claim 7, wherein the compression information associated with the first memory access request is stored within the data structure, and the compression status bit cache is configured to generate a second memory access request to retrieve the compression information from the data structure.

9. The plurality of intermediate caches of claim 8, wherein the compression status bit cache is configured to compute an address within the data structure from where the compression information associated with the first memory access request may be retrieved by adding an offset to an index derived from the tag line.

10. The plurality of intermediate caches of claim 9, wherein a second physical memory address for the second memory access request is computed by performing the first remapping operation on the address within the data structure from where the compression information associated with the first memory access request may be retrieved.

11. The plurality of intermediate caches of claim 10, wherein the compression status bit cache reads the compression information associated with the first memory access request from the data structure based on the second physical memory address via the second memory access request and stores the compression information within a data store residing in the compression status bit cache.

12. The plurality of intermediate caches of claim 11, wherein the data cache unit reads compressed data from the corresponding one of the plurality of portions of external memory based on the first physical memory address via the first memory access request and stores the compressed data within the data cache unit according to the compression information.

13. The plurality of intermediate caches of claim 12, wherein the data cache unit transmits compressed data to the first client, if the first client is configured to receive compressed data, and decompresses the compressed data and transmits the decompressed data to the first client, if the first client is not configured to receive compressed data.

14. The plurality of intermediate caches of claim 7, wherein the compression information associated with the first memory access request is stored within the compression status bit cache, and the compression status bit cache is configured to transmit the compression information to the data cache unit.

15. The plurality of intermediate caches of claim 14, wherein the data cache unit reads compressed data from the corresponding one of the plurality of portions of external memory based on the first physical memory address via the first memory access request and stores the compressed data within the data cache unit according to the compression information.

16. The plurality of intermediate caches of claim 3, wherein the compression information associated with the first memory access request comprises two bits that encode one of four compression status states.

17. The plurality of intermediate caches of claim 16, wherein one compression status state is defined to indicate that no compression is applied to an associated block of memory.

24. The plurality of intermediate caches of claim 1, wherein the data cache unit is an L2 data cache.

18. A computing device, comprising:

one or more clients;

a plurality of intermediary caches, each intermediate cache including;

a command crossbar configured to route a command associated with a first memory access request received from a first client,

a data crossbar configured to route data associated with the first memory access request,

a compression status bit cache configured to cache compression information for blocks of memory stored within a corresponding one of a plurality of portions of external memory, and

a data cache unit configured to request, in response to a cache miss in the data cache unit, compressed data from the corresponding one of the plurality of portions of external memory based on compression information associated with the first memory access request and stored in either the compression status bit cache or a data structure residing in the corresponding one of the plurality of portions of external memory, wherein the compression information indicates the number of bits that comprise the compressed data, and wherein the compressed data comprises a reduced set of data for representing the requested data,

wherein each intermediate cache is coupled to the one or more clients via a crossbar unit and to the corresponding one of the plurality of portions of external memory, and

wherein each intermediate cache is configured to access at least one data surface and the data structure storing compression information for and residing in the corresponding one of the plurality of portions of external memory.

19. The computing device of claim 18, wherein the compression status bit cache is further configured to determine, based on a cache tag, whether the compression information associated with the first memory access request is currently stored within the compression status bit cache or the data structure, and wherein the cache tag is derived from a tag line associated with the first memory access request received from a memory management unit, and the tag line is generated during a virtual address to physical address translation performed by the memory management unit.

20. The computing device of claim 19, wherein the compression information associated with the first memory access request is stored within the data structure, the compression status bit cache is further configured to:

generate a second memory access request to retrieve the compression information from the data structure,

compute an address within the data structure from where the compression information associated with the first memory access request may be retrieved by adding an offset to an index derived from the tag line,

compute a second physical memory address for the second memory access request by performing the first remapping operation on the address within the data structure from where the compression information associated with the first memory access request may be retrieved,

read the compression information associated with the first memory access request from the data structure based on the second physical memory address via the second memory access request, and

store the compression information within a data store residing in the compression status bit cache, and

the data cache unit is further configured to;

read compressed data from the corresponding one of the plurality of portions of external memory based on the first physical memory address via the first memory access request, and

store the compressed data according to the compression information.

21. The computing device of claim 19, wherein the compression information associated with the first memory access request is stored within the compression status bit cache, the compression status bit cache is further configured to transmit the compression information to the data cache unit, and the data cache unit is further configured to read compressed data from the corresponding one of the plurality of portions of external memory based on the first physical memory address via the first memory access request, and store the compressed data according to the compression information.

22. The computing device of claim 19, wherein the compression information associated with the first memory access request comprises two bits that encode one of four compression status states.

23. The computing device of claim 18, wherein the data cache unit transmits compressed data to the first client, if the first client is configured to receive compressed data, and decompresses the compressed data and transmits the decompressed data to the first client, if the first client is not configured to receive compressed data.