IP Library › Granted Patent US 9,355,038
Granted Patent B2
US 9,355,038 · App. 14/483,902 · Granted May 31, 2016

Cache bank spreading for compression algorithms

Inventors: George Patsilaras (Del Mar, CA); Andrew Edmund Turner (San Diego, CA); Bohuslav Rychlik (San Diego, CA)
Assignee: QUALCOMM Incorporated
G06F12/0893
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,355,038
App. No.
14/483,902
Granted
May 31, 2016
Kind
B2
Abstract

Aspects include computing devices, systems, and methods for implementing a cache memory access requests for compressed data using cache bank spreading. In an aspect, cache bank spreading may include determining whether the compressed data of the cache memory access fits on a single cache bank. In response to determining that the compressed data fits on a single cache bank, a cache bank spreading value may be calculated to replace/reinstate bank selection bits of the physical address for a cache memory of the cache memory access request that may be cleared during data compression. A cache bank spreading address in the physical space of the cache memory may include the physical address of the cache memory access request plus the reinstated bank selection bits. The cache bank spreading address may be used to read compressed data from or write compressed data to the cache memory device.

Claims (78)

1. A method for executing cache memory access requests for compressed data on a computing device, comprising:

reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address; and

executing the cache memory access request at the cache bank spreading address.

2. The method of claim 1 , further comprising determining whether compressed data fits on a cache line of a single cache bank of a cache memory device,

wherein reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address comprises reinstating the one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a single cache bank of the cache memory device.

3. The method of claim 2 , wherein determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises determining whether a compression ratio of the compressed data is greater than or equal to a 2:1 compression ratio.

4. The method of claim 2 , wherein determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises determining whether a size of the compressed data is less than or equal to a size of a cache line of the cache memory device.

5. The method of claim 2 , wherein reinstating one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a cache bank of the cache memory device comprises:

selecting inputs for a cache bank spreading function;

executing the cache bank spreading function;

returning a cache bank spreading value; and

replacing the one or more bank select bits with the cache bank spreading value.

6. The method of claim 5 , wherein:

selecting inputs for the cache bank spreading function comprises selecting a plurality of least significant bits of conserved bits of the physical address of the cache memory device of the cache memory access request as operands for the cache bank spreading function; and

executing the cache bank spreading function comprises using an exclusive OR operator with the operands.

7. The method of claim 5 , wherein executing the cache bank spreading function comprises using one of a logical operation, an arithmetic operation, selecting a random value, selecting the cache bank spreading address associated with the physical address of the cache memory access request from a table.

8. The method of claim 1 , wherein executing the cache memory access request at the cache bank spreading address comprises:

writing compressed data to a first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from a second cache bank indicated by one or more bank select bits of the physical address of a cache memory device of the cache memory access request; and

reading the compressed data from the first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from the second cache bank indicated by one or more bank select bits of the physical address of the cache memory device of the cache memory access request.

9. The method of claim 1 , wherein executing the cache memory access request at the cache bank spreading address comprises executing the cache memory access request for the compressed data at a physical address of a cache memory device indicated by the cache bank spreading address.

10. A computing device, comprising:

a processor;

a bank spreading function component communicatively connected to the processor and configured to perform operations comprising reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address;

a cache memory controller communicatively connected to the bank spreading function component and configured to perform operations comprising executing the cache memory access request at the cache bank spreading address; and

a cache memory communicatively connected to the cache memory controller.

11. The computing device of claim 10 , wherein:

the bank spreading function component is configured to perform operations further comprising determining whether compressed data fits on a cache line of a single cache bank of the cache memory; and

the bank spreading function component is configured to perform operations such that reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address comprises reinstating the one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a single cache bank of the cache memory.

12. The computing device of claim 11 , wherein the bank spreading function component is configured to perform operations such that determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory comprises determining whether a compression ratio of the compressed data is greater than or equal to a 2:1 compression ratio.

13. The computing device of claim 11 , wherein the bank spreading function component is configured to perform operations such that determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory comprises determining whether a size of the compressed data is less than or equal to a size of a cache line of the cache memory.

14. The computing device of claim 11 , wherein the bank spreading function component is configured to perform operations such that reinstating one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a cache bank of the cache memory comprises:

selecting inputs for a cache bank spreading function;

executing the cache bank spreading function;

returning a cache bank spreading value; and

replacing the one or more bank select bits with the cache bank spreading value.

15. The computing device of claim 14 , wherein the bank spreading function component is configured to perform operations such that:

executing the cache bank spreading function comprises using one of an exclusive OR operator with operands, a logical operation, an arithmetic operation, selecting a random value, selecting the cache bank spreading address associated with the physical address of the cache memory access request from a table; and

selecting inputs for the cache bank spreading function comprises selecting a plurality of least significant bits of conserved bits of the physical address of the cache memory of the cache memory access request as the operands for the cache bank spreading function using an exclusive OR operator with the operands.

16. The computing device of claim 10 , wherein the cache memory controller is configured to perform operations such that executing the cache memory access request at the cache bank spreading address in the cache memory comprises:

writing compressed data to a first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from a second cache bank indicated by one or more bank select bits of the physical address of the cache memory of the cache memory access request; and

reading the compressed data from the first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from the second cache bank indicated by one or more bank select bits of the physical address of the cache memory of the cache memory access request.

17. A non-transitory processor-readable medium having stored thereon processor-executable instructions configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations comprising:

reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address; and

executing the cache memory access request at the cache bank spreading address.

18. The non-transitory processor-readable medium of claim 17 , wherein:

the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations further comprising determining whether compressed data fits on a cache line of a single cache bank of a cache memory device, and

the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address comprises reinstating the one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a single cache bank of the cache memory device.

19. The non-transitory processor-readable medium of claim 18 , wherein the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises determining whether a compression ratio of the compressed data is greater than or equal to a 2:1 compression ratio.

20. The non-transitory processor-readable medium of claim 18 , wherein the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises determining whether a size of the compressed data is less than or equal to a size of a cache line of the cache memory device.

21. The non-transitory processor-readable medium of claim 18 , wherein the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that reinstating one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a cache bank of the cache memory device comprises:

selecting inputs for a cache bank spreading function;

executing the cache bank spreading function;

returning a cache bank spreading value; and

replacing the one or more bank select bits with the cache bank spreading value.

22. The non-transitory processor-readable medium of claim 21 , wherein the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that:

executing the cache bank spreading function comprises using one of an exclusive OR operator with operands, a logical operation, an arithmetic operation, selecting a random value, selecting the cache bank spreading address associated with the physical address of the cache memory access request from a table; and

selecting inputs for the cache bank spreading function comprises selecting a plurality of least significant bits of conserved bits of the physical address of the cache memory device of the cache memory access request as the operands for the cache bank spreading function using an exclusive OR operator with the operands.

23. The non-transitory processor-readable medium of claim 17 , wherein the stored processor-executable instructions are configured to cause a processor, a bank spreading function component, and a cache memory controller to perform operations such that executing the cache memory access request at the cache bank spreading address comprises:

writing compressed data to a first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from a second cache bank indicated by one or more bank select bits of the physical address of a cache memory device of the cache memory access request; and

reading the compressed data from the first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from the second cache bank indicated by one or more bank select bits of the physical address of the cache memory device of the cache memory access request.

24. A computing device, comprising:

means for reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address; and

means for executing the cache memory access request at the cache bank spreading address.

25. The computing device of claim 24 , further comprising means for determining whether compressed data fits on a cache line of a single cache bank of a cache memory device,

wherein means for reinstating one or more bank select bits of a physical address of a cache memory access request producing a cache bank spreading address comprises means for reinstating the one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a single cache bank of the cache memory device.

26. The computing device of claim 25 , wherein means for determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises means for determining whether a compression ratio of the compressed data is greater than or equal to a 2:1 compression ratio.

27. The computing device of claim 25 , wherein means for determining whether the compressed data of the cache memory access request fits on a single cache bank of the cache memory device comprises means for determining whether a size of the compressed data is less than or equal to a size of a cache line of the cache memory device.

28. The computing device of claim 25 , wherein means for reinstating one or more bank select bits of the physical address of the cache memory access request producing the cache bank spreading address in response to determining that the compressed data fits on a cache bank of the cache memory device comprises:

means for selecting inputs for a cache bank spreading function;

means for executing the cache bank spreading function;

means for returning a cache bank spreading value; and

means for replacing the one or more bank select bits with the cache bank spreading value.

29. The computing device of claim 28 , wherein:

means for executing the cache bank spreading function comprises means for using one of an exclusive OR operator with operands, a logical operation, an arithmetic operation, selecting a random value, selecting the cache bank spreading address associated with the physical address of the cache memory access request from a table; and

means for selecting inputs for the cache bank spreading function comprises means for selecting a plurality of least significant bits of conserved bits of the physical address of the cache memory device of the cache memory access request as the operands for the cache bank spreading function using an exclusive OR operator with the operands.

30. The computing device of claim 24 , wherein means for executing the cache memory access request at the cache bank spreading address comprises:

means for writing compressed data to a first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from a second cache bank indicated by one or more bank select bits of the physical address of a cache memory device of the cache memory access request; and

means for reading the compressed data from the first cache bank indicated by the one or more reinstated bank select bits of the cache bank spreading address different from the second cache bank indicated by one or more bank select bits of the physical address of the cache memory device of the cache memory access request.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 15, 2014
From: PATSILARAS, GEORGE; TURNER, ANDREW EDMUND; RYCHLIK, BOHUSLAV
To: QUALCOMM INCORPORATED
Reel/Frame 033736/0139 →
Continuity (1)
Related Publication 20160077973A1 · Mar 17, 2016