Device and method for cache utilization aware data compression

1. A processing device comprising:

memory comprising:

main memory; and

cache memory in communication with the main memory via a link; and

at least one processor configured to:

receive a request for a cache line;

read the cache line from main memory;

compress the cache line according to a compression algorithm; and

when the compressed cache line includes at least one byte predicted to not be accessed, drop the at least one byte from the compressed cache line based on whether the compression algorithm is determined to successfully compress the cache line according to a compression parameter.

2. The processing device according to claim 1 , wherein the at least one processor is further configured to:

predict, for each byte of the cache line, whether or not a byte will be accessed;

send the request for the cache line across the link along with prediction information comprising the prediction of whether or not each byte will be accessed; and

determine whether the cache line includes the at least one byte predicted to not be accessed based on the prediction information.

3. The processing device according to claim 2 , wherein the at least one processor is further configured to:

predict, for each byte of the cache line, whether or not the byte will be accessed prior to the cache line being evicted from the cache; and

determine that the cache line includes the at least one byte predicted to not be accessed when the at least one byte is predicted to not be accessed prior to the cache line being evicted from the cache.

4. The processing device according to claim 1 , wherein

the compression parameter is a number of clock cycles used to send the cache line across the link; and

the at least one processor is further configured to determine whether the compression algorithm successfully compresses the cache line based on whether the number of clock cycles used to send the cache line across the link is reduced by the compression of the cache line using the compression algorithm.

5. The processing device according to claim 1 , wherein

the compression parameter is an effective cache capacity of the cache; and

the at least one processor is further configured to determine whether the compression algorithm successfully compresses the cache line based on whether the effective cache capacity of the cache is increased by the compression of the cache line using the compression algorithm.

6. The processing device according to claim 1 , wherein the at least one processor is further configured to:

determine whether or not a compression success rate is less than a compression success rate threshold;

determine whether or not to drop the at least one byte predicted to be accessed when the compression success rate is determined to not be less than the compression success rate threshold; and

send the compressed cache line across the link when the compression success rate is determined to be less than the compression success rate threshold.

7. The processing device according to claim 6 , wherein the at least one processor is further configured to:

monitor and store, over time, requests to access each byte of the cache line from multiple portions of a program;

determine the compression success rate based on the stored requests; and

compare the compression success rate to the compression success rate threshold.

8. The processing device according to claim 1 , wherein the at least one processor is further configured to:

determine whether or not the cache line includes a number of bytes which are not predicted to be accessed;

when the at least one processor determines that the cache line includes a plurality of bytes which are not predicted to be accessed, start dropping the plurality of bytes, one at a time, from the cache line;

after each one of the plurality of dropped bytes is dropped, determine whether the dropped byte causes the compression algorithm to successfully compress the cache line according to the compression parameter; and

send the compressed cache line with the at least one dropped byte across the link when it is determined that the compression algorithm successfully compresses the cache line according to the compression parameter.

9. The processing device according to claim 1 , wherein the at least one processor is further configured to:

identify at least one invalid byte, which is requested to be accessed after the cache line is sent across the link with at least one dropped byte, by using an associated write mask of the at least one dropped byte; and

invalidate the cache line when the at least one invalid byte is identified.

10. A data processing method comprising:

receiving a request for a cache line;

reading the cache line from main memory;

compressing the cache line according to a compression algorithm; and

when the compressed cache line includes at least one byte predicted to not be accessed, dropping the at least one byte from the compressed cache line based on whether the compression algorithm is determined to successfully compress the cache line according to a compression parameter.

11. The method according to claim 10 , further comprising:

predicting, for each byte of the cache line, whether or not a byte will be accessed;

sending the request for the cache line across the link along with prediction information comprising the prediction of whether or not each byte will be accessed; and

determining whether the cache line includes at least one byte which is predicted not to be accessed based on the prediction information.

12. The method according to claim 11 , further comprising:

predicting, for each byte of the cache line, whether or not a byte will be accessed prior to the cache line being evicted from the cache; and

determining that the cache line includes the at least one byte predicted to not be accessed when the at least one byte is predicted to not be accessed prior to the cache line being evicted from the cache.

13. The method according to claim 10 , wherein

the compression parameter is a number of clock cycles used to send the cache line across the link; and

the method further comprises determining whether the compression algorithm successfully compresses the cache line based on whether the number of clock cycles used to send the cache line across the link is reduced by the compression of the cache line using the compression algorithm.

14. The method according to claim 10 , wherein

the compression parameter is an effective cache capacity of the cache; and

the method further comprises determining whether the compression algorithm successfully compresses the cache line based on whether the effective cache capacity of the cache is increased by the compression of the cache line using the compression algorithm.

15. The method according to claim 10 , further comprising:

determining whether or not a compression success rate is less than a compression success rate threshold;

determine whether or not to drop the at least one byte predicted to be accessed when the compression success rate is determined to not be less than the compression success rate threshold; and

send the compressed cache line across the link when the compression success rate is determined to be less than the compression success rate threshold.

16. The method according to claim 15 , further comprising:

monitoring and storing, over time, requests to access each byte of the cache line from multiple portions of a program;

determining the compression success rate based on the stored requests; and

comparing the compression success rate to the compression success rate threshold.

17. The method according to claim 10 , further comprising:

determining whether or not the cache line includes a number of bytes which are not predicted to be accessed;

when the at least one processor determines that the cache line includes a plurality of bytes which are not predicted to be accessed, start dropping the plurality of bytes, one at a time, from the cache line;

after each one of the plurality of dropped bytes is dropped, determining whether the dropped byte causes the compression algorithm to successfully compress the cache line according to the compression parameter; and

sending the compressed cache line with the at least one dropped byte across the link when it is determined that the compression algorithm successfully compresses the cache line according to the compression parameter.

18. The method according to claim 10 , further comprising:

identifying at least one invalid byte, which is requested to be accessed after the cache line is sent across the link with at least one dropped byte, by using an associated write mask of the at least one dropped byte; and

invalidating the cache line when the at least one invalid byte is identified.

19. A non-transitory computer readable medium having instructions for causing a computer to execute a data processing method comprising:

receiving a request for a cache line;

reading the cache line from main memory;

compressing the cache line according to a compression algorithm; and

when the compressed cache line includes at least one byte predicted to not be accessed, dropping the at least one byte from the compressed cache line based on whether the compression algorithm is determined to successfully compress the cache line according to a compression parameter.

20. The computer readable medium according to claim 19 , wherein the instructions further comprise:

predicting, for each byte of the cache line, whether or not a byte will be accessed;

sending the request for the cache line across the link along with prediction information comprising the prediction of whether or not each byte will be accessed; and

determining whether the cache line includes at least one byte which is predicted not to be accessed based on the prediction information.