# US 7,412,564 B2 · Adaptive cache compression system

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

- Number: US 7,412,564 B2
- Document ID: US7412564B2
- Status: Granted
- Kind: B2
- Application number: 11/265,975
- Filed: 2005-11-03
- Published: 2006-05-11
- Granted: 2008-08-12
- Earliest claimed: 2004-11-05
- Assignees: Wisconsin Alumni Research Foundation
- Inventors: David A. Wood; Alaa R. Alameldeen
- Web page: https://patentgrep.com/patent/US7412564B2

## CPC

- 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
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 2212/401: Compressed data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Data in a cache is selectively compressed based on predictions as to whether the benefit of compression in reducing cache misses exceeds the cost of decompressing the compressed data. The prediction is based on an assessment of actual costs and benefits for previous instruction cycles of the same program providing dynamic and concurrent adjustment of compression to maximize the benefits of compression in a variety of applications.

## Claims

### Claim 1

A cache system for use with an electronic computer comprising:
a cache memory;
a data compressor controllably compressing data to be stored in the cache memory;
a data decompressor decompressing compressed data stored in the cache memory; and
a predictor communicating with the data compressor to control compression of data to be stored in the cache memory according to a predicted effect of the compression of data on a speed of execution of a program using the data, based on a current utilization of the cache memory by the program.

### Claim 2 (depends on 1)

The cache recited in claim 1 wherein the data compressor can be switched by the predictor between compressing or not compressing the data to be stored in the cache.

### Claim 3 (depends on 1)

The cache recited in claim 1 wherein the data decompressor includes a bypass allowing uncompressed data to bypass the data decompressor reducing latency for uncompressed data stored in the cache memory.

### Claim 4 (depends on 2)

The cache recited in claim 2 wherein the predictor creates a prediction value indicating a predicted effect of compression on the speed of execution, and wherein the predictor controls the data compressor to compress the data when the prediction value is above a predetermined amount and to not compress the data when the prediction value is below the predetermined amount.

### Claim 5 (depends on 2)

The cache recited in claim 2 wherein the predictor creates a prediction value indicating a predicted effect of compression of the speed of execution, and wherein the predictor controls the data compressor to switch between compressing the data and not compressing the data so as to create an average compression being a semi-continuous function of the prediction value.

### Claim 6 (depends on 1)

The cache recited in claim 1 wherein the data compressor can be switched by the predictor between multiple degrees of compression having different latency.

### Claim 7 (depends on 1)

The cache recited in claim 1 wherein the predictor compares a cost and benefit of compression over a predetermined previous time.

### Claim 8 (depends on 7)

The cache recited in claim 7 wherein the predictor is a counter tallying historical time saved and lost attributable to compressed data in the cache memory.

### Claim 9 (depends on 8)

The cache recited in claim 8 wherein the predictor tallies a time saved when data accessed would not have been held in the cache but for compression, and tallies a time lost when the data is compressed, but would have been held in the cache regardless of compression.

### Claim 10 (depends on 8)

The cache recited in claim 8 wherein the predictor tallies a time saved when data was not in the cache, but could have been in the cache with more compression.

### Claim 11 (depends on 1)

The cache recited in claim 1 wherein the cache includes tag data indicating compressed lengths of associated line data.

### Claim 12 (depends on 11)

The cache recited in claim 11 wherein the tag data indicates a compressed size of associated line data regardless of whether the line data is compressed.

### Claim 13 (depends on 1)

The cache recited in claim 1 wherein the cache includes tag data indicating whether associated cache data is compressed.

### Claim 14 (depends on 1)

The cache recited in claim 1 wherein the data compressor identifies small magnitude data values and compresses them by truncating unused more significant data storage elements.

### Claim 15 (depends on 1)

The cache recited in claim 1 wherein the data compressor identifies common data patterns and replaces them with abbreviated patterns to compress the data.

### Claim 16 (depends on 15)

The cache recited in claim 15 wherein the common data patterns include low magnitude numbers, zero, and repeated data blocks.

### Claim 17 (depends on 1)

The cache recited in claim 1 also includes a second cache memory reading from the cache memory.

### Claim 18 (depends on 17)

The cache recited in claim 17 further including a victim cache holding data expelled from the second cache memory.

### Claim 19

A method of operating a cache memory in an electronic computer comprising the steps of:
(a) monitoring access of the cache memory;
(b) based on the monitoring of step (a) predicting an effect of compressing data in the cache on a speed of execution of a program using the data of the cache memory, based on a current utilization of the cache memory by the program; and
(c) compressing selected data stored in the cache memory based on a prediction of step (b); and
(d) repeating steps (a)-(c) to update the prediction during operation of the electronic computer in executing the program.

### Claim 20 (depends on 19)

The method recited in claim 19 wherein the step (c) of compressing the data selects between compressing or not compressing the data to be stored in the cache according to the prediction.

### Claim 21 (depends on 20)

The method recited in claim 20 wherein the step (c) of compressing the data compresses the data when the prediction is above a predetermined threshold and does not compress the data when the prediction is below the predetermined threshold.

### Claim 22 (depends on 20)

The method recited in claim 20 wherein the step (c) of compressing the data switches between compressing the data and not compressing the data so as to create an average compression being a semi-continuous function of the prediction.

### Claim 23 (depends on 19)

The method recited in claim 19 wherein the step (c) of compressing the data selects between multiple degrees of compression having different latency.

### Claim 24 (depends on 19)

The method recited in claim 19 wherein the step (b) of predicting compares an historical cost and benefit of compression over a predetermined previous time.

### Claim 25 (depends on 24)

The method recited in claim 24 wherein the step (b) of predicting tallies historical time saved and lost attributable to compressed data in the cache memory.

### Claim 26 (depends on 25)

The method recited in claim 25 wherein the step (b) of predicting tallies a time saved when data accessed would not have been held in the cache but for compression, and tallies a time lost when the data is compressed but would have been held in the cache regardless of compression.

### Claim 27 (depends on 25)

The method recited in claim 25 wherein the step (b) of predicting tallies a time saved when data was not in the cache but could have been in the cache with more compression.

### Claim 28 (depends on 19)

The method recited in claim 19 wherein step (c) of compressing identifies small magnitude data values and compresses them by truncating unused more significant data storage elements.

### Claim 29 (depends on 19)

The method recited in claim 19 wherein step (c) of compressing identifies common data patterns and replaces them with abbreviated patterns to compress the data.

### Claim 30 (depends on 29)

The method recited in claim 29 wherein the common data patterns include low magnitude numbers, zero, repeated data blocks.