Adaptive cache compression system
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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. The cache recited in claim 1 wherein the data compressor can be switched by the predictor between multiple degrees of compression having different latency.
7. The cache recited in claim 1 wherein the predictor compares a cost and benefit of compression over a predetermined previous time.
8. 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.
9. 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.
10. 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.
11. The cache recited in claim 1 wherein the cache includes tag data indicating compressed lengths of associated line data.
12. 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.
13. The cache recited in claim 1 wherein the cache includes tag data indicating whether associated cache data is compressed.
14. 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.
15. The cache recited in claim 1 wherein the data compressor identifies common data patterns and replaces them with abbreviated patterns to compress the data.
16. The cache recited in claim 15 wherein the common data patterns include low magnitude numbers, zero, and repeated data blocks.
17. The cache recited in claim 1 also includes a second cache memory reading from the cache memory.
18. The cache recited in claim 17 further including a victim cache holding data expelled from the second cache memory.
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.
20. 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.
21. 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.
22. 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.
23. The method recited in claim 19 wherein the step (c) of compressing the data selects between multiple degrees of compression having different latency.
24. 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.
25. 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.
26. 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.
27. 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.
28. 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.
29. 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.
30. The method recited in claim 29 wherein the common data patterns include low magnitude numbers, zero, repeated data blocks.