# US 2017/0286308 A1 · Providing memory bandwidth compression using multiple last-level cache (llc) lines in a central processing unit (cpu)-based system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286308 A1
- Document ID: US20170286308A1
- Status: Published application
- Kind: A1
- Application number: 15/086,817
- Filed: 2016-03-31
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Colin Beaton Verrilli; Mattheus Cornelis Antonius Adrianus Heddes; Mark Anthony Rinaldi; Natarajan Vaidhyanathan
- Web page: https://patentgrep.com/patent/US20170286308A1

## CPC

- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 12/04: Addressing variable-length words or parts of words
- G06F 12/084: with a shared cache
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 12/12: Replacement control
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0862: with prefetch
- G06F 2212/1016: Performance improvement
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/401: Compressed data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Providing memory bandwidth compression using multiple last-level cache (LLC) lines in a central processing unit (CPU)-based system is disclosed. In some aspects, a compressed memory controller (CMC) provides an LLC comprising multiple LLC lines, each providing a plurality of sub-lines the same size as a system cache line. The contents of the system cache line(s) stored within a single LLC line are compressed and stored in system memory within the memory sub-line region corresponding to the LLC line. A master table stores information indicating how the compressed data for an LLC line is stored in system memory by storing an offset value and a length value for each sub-line within each LLC line. By compressing multiple system cache lines together and storing compressed data in a space normally allocated to multiple uncompressed system lines, the CMC enables compression sizes to be smaller than the memory read/write granularity of the system memory.

## Claims

### Claim 1

A compressed memory controller (CMC), comprising a memory interface configured to access a system memory and a system cache via a system bus, and communicatively coupled to a last-level cache (LLC) comprising a plurality of LLC lines each sized to store a plurality of sub-lines corresponding to a plurality of system cache lines of the system cache;
the CMC configured to:
receive, from the system cache, a memory read request comprising a memory address;
determine whether the memory address corresponds to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC; and
responsive to determining that the memory address does not correspond to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC:
read a master table entry containing an offset value and a length value for the LLC line from a master table in the system memory;
retrieve one or more blocks from the system memory based on the memory address, the offset value, and the length value;
store data from the retrieved one or more blocks in a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC; and
return the data from the retrieved one or more blocks to the system cache.

### Claim 2 (depends on 1)

The CMC of claim 1, configured to determine whether the memory address corresponds to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC by being configured to:
determine whether the memory address corresponds to a sub-line of an existing LLC line within the plurality of LLC lines; and
responsive to determining that the memory address corresponds to a sub-line of an existing LLC line within the plurality of LLC lines, determine whether the sub-line of the existing LLC line is valid.

### Claim 3 (depends on 1)

The CMC of claim 1, further configured to, responsive to determining that the memory address corresponds to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC, return data from the valid sub-line to the system cache.

### Claim 4 (depends on 1)

The CMC of claim 1, configured to store the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC by being configured to:
determine, based on the length value, whether the data from the retrieved one or more blocks is compressed;
responsive to determining that the data from the retrieved one or more blocks is not compressed, store the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC; and
responsive to determining that the data from the retrieved one or more blocks is compressed:
decompress the data from the retrieved one or more blocks; and
store the decompressed data in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC.

### Claim 5 (depends on 1)

The CMC of claim 1, further configured to, prior to storing the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC:
select an LLC line of the plurality of LLC lines as an eviction LLC line;
store data from the plurality of sub-lines of the eviction LLC line in the system memory; and
store the data from the retrieved one or more blocks in a sub-line of the plurality of sub-lines within the eviction LLC line.

### Claim 6 (depends on 5)

The CMC of claim 5, configured to store the data from the plurality of sub-lines of the eviction LLC line in the system memory by being configured to:
read a plurality of master table entries each containing an offset value and a length value for each corresponding sub-line of the plurality of sub-lines of the eviction LLC line; and
for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data:
compress data from the sub-line;
generate an updated length value for the sub-line based on the compressed data from the sub-line;
determine whether the updated length value for the sub-line is different from the length value for the sub-line;
responsive to determining that the updated length value for the sub-line is not different from the length value for the sub-line, write the compressed data for the sub-line to one or more blocks of the system memory based on the offset value and the length value for the sub-line; and
responsive to determining that the updated length value for the sub-line is different from the length value for the sub-line:
generate an updated offset value for the sub-line;
write the compressed data for the sub-line to one or more blocks of the system memory based on the updated offset value and the updated length value for the sub-line; and
update a master table entry for the sub-line with the updated offset value and the updated length value.

### Claim 7 (depends on 6)

The CMC of claim 6, configured to generate the updated offset value for the sub-line based on one or more allocation rules comprising preventing the compressed data from straddling memory sub-line regions of the system memory corresponding to more than one sub-line, aligning the compressed data within the memory sub-line regions of the system memory, and grouping the compressed data for the plurality of sub-lines.

### Claim 8 (depends on 1)

The CMC of claim 1, further comprising a master table (MT) cache comprising a plurality of MT cache entries each configured to store a previously read master table entry;
the CMC further configured to, prior to reading the master table entry, determine whether the memory address corresponds to an MT cache entry of the plurality of MT cache entries of the MT cache;
the CMC configured to read the master table entry in the master table responsive to determining that the memory address does not correspond to an MT cache entry of the plurality of MT cache entries of the MT cache; and
the CMC further configured to:
responsive to determining that the memory address does not correspond to an MT cache entry of the plurality MT cache entries of the MT cache, write the master table entry to an MT cache entry of the plurality of MT cache entries of the MT cache; and
responsive to determining that the memory address corresponds to an MT cache entry of the plurality MT cache entries of the MT cache, read the MT cache entry of the MT cache.

### Claim 9 (depends on 8)

The CMC of claim 8, further configured to, prior to writing the master table entry to the MT cache entry of the plurality of MT cache entries of the MT cache:
determine whether a current MT cache entry of the plurality of MT cache entries of the MT cache should be evicted; and
responsive to determining that the current MT cache entry should be evicted:
determine whether the current MT cache entry has been updated; and
responsive to determining that the current MT cache entry has been updated, write contents of the current MT cache entry to the master table.

### Claim 10 (depends on 1)

The CMC of claim 1, further configured to:
read one or more master table entries containing one or more offset values and one or more length values for one or more remaining sub-lines of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC;
retrieve the one or more blocks from the system memory based on the one or more offset values and the one or more length values; and
store the data from the retrieved one or more blocks in the one or more remaining sub-lines of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC.

### Claim 11 (depends on 1)

The CMC of claim 1 integrated into an integrated circuit (IC).

### Claim 12 (depends on 1)

The CMC of claim 1 integrated into a device selected from the group consisting of: a set top box; an entertainment unit; a navigation device; a communications device; a fixed location data unit; a mobile location data unit; a mobile phone; a cellular phone; a smart phone; a tablet; a phablet; a computer; a portable computer; a desktop computer; a personal digital assistant (PDA); a monitor; a computer monitor; a television; a tuner; a radio; a satellite radio; a music player; a digital music player; a portable music player; a digital video player; a video player; a digital video disc (DVD) player; a portable digital video player; and an automobile.

### Claim 13

A compressed memory controller (CMC), comprising a memory interface configured to access a system memory and a system cache via a system bus, and communicatively coupled to a last-level cache (LLC) comprising a plurality of LLC lines each sized to store a plurality of sub-lines corresponding to a contiguous plurality of system cache lines of the system cache;
the CMC configured to:
receive, from the system cache, a memory write request comprising write data and a memory address;
determine whether the memory address corresponds to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC; and
responsive to determining that the memory address does not correspond to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC:
select an LLC line within the plurality of LLC lines of the LLC as an eviction LLC line;
for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data:
compress data from the sub-line;
generate an updated offset value and an updated length value for the sub-line based on the compressed data from the sub-line;
store the compressed data for the sub-line in one or more blocks of the system memory based on the updated offset value and the updated length value for the sub-line; and
store the updated offset value and the updated length value in a master table entry for the sub-line in a master table; and
store the write data in a sub-line of the plurality of sub-lines of the eviction LLC line.

### Claim 14 (depends on 13)

The CMC of claim 13, further configured to, responsive to determining that the memory address corresponds to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC, store the write data in the sub-line of the LLC line.

### Claim 15 (depends on 13)

The CMC of claim 13, configured to generate the updated offset value for the sub-line based on one or more allocation rules comprising preventing the compressed data from straddling memory sub-line regions of the system memory corresponding to more than one sub-line, aligning the compressed data within the memory sub-line regions of the system memory, and grouping the compressed data for the plurality of sub-lines.

### Claim 16 (depends on 13)

The CMC of claim 13, further configured to:
prior to storing the compressed data for the sub-line in the one or more blocks of the system memory based on the updated offset value and the updated length value for the sub-line, read an offset value and an length value for the sub-line;
determine whether the updated length value for the sub-line is different from the length value for the sub-line;
responsive to determining that the updated length value for the sub-line is different from the length value for the sub-line:
generate the updated offset value for the sub-line;
store the compressed data for the sub-line in one or more blocks of the system memory based on the updated offset value and the length value for the sub-line; and
update the master table entry for the sub-line in the master table with the updated offset value and the length value; and
the CMC configured to store the compressed data for the sub-line in the one or more blocks of the system memory based on the offset value and the length value for the sub-line responsive to determining that the updated length value for the sub-line is not different from the length value for the sub-line.

### Claim 17 (depends on 13)

The CMC of claim 13, further comprising a master table (MT) cache comprising a plurality of MT cache entries each configured to store a previously read master table entry;
the CMC further configured to, prior to storing the updated offset value and the updated length value in the master table entry for the sub-line in the master table, determine whether the memory address corresponds to an MT cache entry of the plurality of MT cache entries of the MT cache; and
the CMC further configured to:
responsive to determining that the memory address does not correspond to an MT cache entry of the plurality of MT cache entries of the MT cache, store the updated offset value and the updated length value in an MT cache entry of the MT cache; and
responsive to determining that the memory address corresponds to an MT cache entry of the plurality of MT cache entries of the MT cache, update the MT cache entry of the MT cache with the updated offset value and the updated length value.

### Claim 18 (depends on 17)

The CMC of claim 17, further configured to, prior to writing the master table entry to the MT cache entry of the MT cache:
determine whether a current MT cache entry of the plurality of MT cache entries of the MT cache should be evicted; and
responsive to determining that the current MT cache entry should be evicted:
determine whether the current MT cache entry has been modified; and
responsive to determining that the current MT cache entry has been modified, write the master table entry of the MT cache entry to the master table.

### Claim 19 (depends on 13)

The CMC of claim 13 integrated into an integrated circuit (IC).

### Claim 20 (depends on 13)

The CMC of claim 13 integrated into a device selected from the group consisting of: a set top box; an entertainment unit; a navigation device; a communications device; a fixed location data unit; a mobile location data unit; a mobile phone; a cellular phone; a smart phone; a tablet; a phablet; a computer; a portable computer; a desktop computer; a personal digital assistant (PDA); a monitor; a computer monitor; a television; a tuner; a radio; a satellite radio; a music player; a digital music player; a portable music player; a digital video player; a video player; a digital video disc (DVD) player; a portable digital video player; and an automobile.

### Claim 21

A method for providing memory bandwidth compression for memory read operations, comprising:
receiving, by a compressed memory controller (CMC) from a system cache, a memory read request comprising a memory address;
determining whether the memory address corresponds to a valid sub-line of a plurality of sub-lines within a last-level cache (LLC) line of a plurality of LLC lines of an LLC; and
responsive to determining that the memory address does not correspond to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC:
reading a master table entry containing an offset value and a length value for the LLC line from a master table in a system memory;
retrieving one or more blocks from the system memory based on the memory address, the offset value, and the length value;
storing data from the retrieved one or more blocks in a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC; and
returning the data from the retrieved one or more blocks to the system cache.

### Claim 22 (depends on 21)

The method claim 21, wherein determining whether the memory address corresponds to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC comprises:
determining whether the memory address corresponds to a sub-line of the plurality of sub-lines within an existing LLC line of the plurality of LLC lines of the LLC; and
responsive to determining that the memory address corresponds to a sub-line of the plurality of sub-lines within an existing LLC line of the plurality of LLC lines of the LLC, determining whether the sub-line of the existing LLC line is valid.

### Claim 23 (depends on 21)

The method of claim 21, further comprising, responsive to determining that the memory address corresponds to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC, returning data from the valid sub-line to the system cache.

### Claim 24 (depends on 21)

The method of claim 21, wherein storing the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC comprises:
determining, based on the length value, whether the data from the retrieved one or more blocks is compressed;
responsive to determining that the data from the retrieved one or more blocks is not compressed, storing the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC; and
responsive to determining that the data from the retrieved one or more blocks is compressed:
decompressing the data from the retrieved one or more blocks; and
storing the decompressed data in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC.

### Claim 25 (depends on 21)

The method of claim 21, further comprising, prior to storing the data from the retrieved one or more blocks in the sub-line of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC:
selecting an LLC line of the plurality of LLC lines as an eviction LLC line;
storing data from the plurality of sub-lines of the eviction LLC line in the system memory; and
storing the data from the retrieved one or more blocks in a sub-line of the plurality of sub-lines within the eviction LLC line.

### Claim 26 (depends on 25)

The method of claim 25, wherein storing the data from the plurality of sub-lines of the eviction LLC line in the system memory comprises:
reading a plurality of master table entries each containing an offset value and a length value for each corresponding sub-line of the plurality of sub-lines of the eviction LLC line; and
for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data:
compressing data from the sub-line;
generating an updated length value for the sub-line based on the compressed data from the sub-line;
determining whether the updated length value for the sub-line is different from the length value for the sub-line;
responsive to determining that the updated length value for the sub-line is not different from the length value for the sub-line, writing the compressed data for the sub-line to one or more blocks of the system memory based on the offset value and the length value for the sub-line; and
responsive to determining that the updated length value for the sub-line is different from the length value for the sub-line:
generate an updated offset value for the sub-line;
writing the compressed data for the sub-line to one or more blocks of the system memory based on the updated offset value and the updated length value for the sub-line; and
updating the master table entry for the sub-line with the updated offset value and the updated length value.

### Claim 27 (depends on 26)

The method of claim 26, wherein generating the updated offset value for the sub-line is based on one or more allocation rules comprising preventing the compressed data from straddling memory sub-line regions of the system memory corresponding to more than one sub-line, aligning the compressed data within the memory sub-line regions of the system memory, and grouping the compressed data for the plurality of sub-lines.

### Claim 28 (depends on 21)

The method of claim 21, further comprising:
prior to reading the master table entry in the master table, determining whether the memory address corresponds to a master table (MT) cache entry of a plurality of MT cache entries of an MT cache, each MT cache entry configured to store a previously read master table entry;
responsive to determining that the memory address does not correspond to an MT cache entry of the plurality MT cache entries of the MT cache:
reading the master table entry in the master table; and
writing the master table entry to an MT cache entry of the plurality of MT cache entries of the MT cache; and
responsive to determining that the memory address corresponds to an MT cache entry of the plurality MT cache entries of the MT cache, reading the MT cache entry of the plurality of MT cache entries of the MT cache.

### Claim 29 (depends on 28)

The method of claim 28, further comprising, prior to writing the master table entry to the MT cache entry of the plurality of MT cache entries of the MT cache:
determining whether a current MT cache entry of the plurality of MT cache entries of the MT cache should be evicted; and
responsive to determining that the current MT cache entry should be evicted:
determining whether the current MT cache entry has been updated; and
responsive to determining that the current MT cache entry has been updated, writing contents of the current MT cache entry to the master table.

### Claim 30 (depends on 21)

The method of claim 21, further comprising:
reading one or more master table entries containing one or more offset values and one or more length values for one or more remaining sub-lines of the plurality of sub-lines of an LLC line of the plurality of LLC lines of the LLC;
retrieving one or more blocks from the system memory based on the one or more offset values and the one or more length values; and
storing the data from the retrieved one or more blocks in the one or more remaining sub-lines of the plurality of sub-lines within the LLC line of the plurality of LLC lines of the LLC.

### Claim 31

A method for providing memory bandwidth compression for memory write operations, comprising:
receiving, by a compressed memory controller (CMC) from a system cache, a memory write request comprising write data and a memory address;
determining whether the memory address corresponds to a sub-line of a plurality of sub-lines within a last-level cache (LLC) line of a plurality of LLC lines of an LLC;
responsive to determining that the memory address does not correspond to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC:
selecting an LLC line within the plurality of LLC lines of the LLC as an eviction LLC line;
for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data:
compressing data from the sub-line;
generating an updated offset value and an updated length value for the sub-line based on the compressed data from the sub-line;
storing the compressed data for the sub-line in one or more blocks of a system memory based on the updated offset value and the updated length value for the sub-line; and
storing the updated offset value and the updated length value in a master table entry for the sub-line in a master table; and
storing the write data in a sub-line of the plurality of sub-lines of the eviction LLC line.

### Claim 32 (depends on 31)

The method of claim 31, further comprising, responsive to determining that the memory address corresponds to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC, storing the write data in the sub-line of the LLC line.

### Claim 33 (depends on 31)

The method of claim 31, wherein generating the updated offset value for the sub-line is based on one or more allocation rules comprising preventing the compressed data from straddling memory sub-line regions of the system memory corresponding to more than one sub-line, aligning the compressed data within the memory sub-line regions of the system memory, and grouping the compressed data for the plurality of sub-lines.

### Claim 34 (depends on 31)

The method of claim 31, wherein generating the updated offset value and the updated length value for the sub-line based on the compressed data from the sub-line comprises:
generating the updated length value for the sub-line based on the compressed data;
reading an offset value and a length value for the sub-line;
determining whether the updated length value for the sub-line is different from the length value for the sub-line;
responsive to determining that the updated length value for the sub-line is different from the length value for the sub-line, generating the updated offset value based on the compressed data; and
responsive to determining that the updated length value for the sub-line is not different from the length value for the sub-line, using the offset value as the updated offset value.

### Claim 35 (depends on 31)

The method of claim 31, further comprising:
prior to storing the updated offset value and the updated length value in the master table entry for the sub-line in the master table, determining whether the memory address corresponds to a master table (MT) cache entry of a plurality of MT cache entries of an MT cache, each MT cache entry configured to store a previously read master table entry;
responsive to determining that the memory address does not correspond to an MT cache entry of the plurality of MT cache entries of the MT cache:
storing the updated offset value and the updated length value in the master table entry for the sub-line in the master table; and
writing the master table entry to an MT cache entry of the plurality of MT cache entries of the MT cache; and
responsive to determining that the memory address corresponds to an MT cache entry of the plurality of MT cache entries of the MT cache, updating the MT cache entry of the MT cache with the master table entry.

### Claim 36 (depends on 35)

The method of claim 35, further comprising, prior to writing the master table entry to the MT cache entry of the plurality of MT cache entries of the MT cache:
determining whether a current MT cache entry of the plurality of MT cache entries of the MT cache should be evicted; and
responsive to determining that the current MT cache entry should be evicted:
determining whether the current MT cache entry has been modified; and
responsive to determining that the current MT cache entry has been modified, writing contents of the MT cache entry to the master table.

### Claim 37

A compressed memory controller (CMC), comprising:
a means for receiving, from a system cache, a memory read request comprising a memory address;
a means for determining whether the memory address corresponds to a valid sub-line of a plurality of sub-lines within a last-level cache (LLC) line of a plurality of LLC lines of an LLC;
a means for reading a master table entry containing an offset value and a length value for the LLC line from a master table in a system memory, responsive to determining that the memory address does not correspond to a valid sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC;
a means for retrieving one or more blocks from the system memory based on the memory address, the offset value, and the length value;
a means for storing data from the retrieved one or more blocks in a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC; and
a means for returning the data from the retrieved one or more blocks to the system cache.

### Claim 38

A compressed memory controller (CMC), comprising:
a means for receiving, from a system cache, a memory write request comprising write data and a memory address;
a means for determining whether the memory address corresponds to a sub-line of a plurality of sub-lines within a last-level cache (LLC) line of a plurality of LLC lines of an LLC;
a means for selecting an LLC line within the plurality of LLC lines of the LLC as an eviction LLC line, responsive to determining that the memory address does not correspond to a sub-line of the plurality of sub-lines within an LLC line of the plurality of LLC lines of the LLC;
a means for compressing data from each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data;
a means for generating, for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data, an updated offset value and an updated length value based on the compressed data from the sub-line;
a means for storing, for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data, the compressed data in one or more blocks of a system memory based on the updated offset value and the updated length value for the sub-line;
a means for storing, for each sub-line of the plurality of sub-lines of the eviction LLC line containing modified data, the updated offset value and the updated length value in a master table entry for the sub-line in a master table; and
a means for storing the write data in a sub-line of the plurality of sub-lines of the eviction LLC line.