Granted Patent B2

US 9,378,214 · App. 14/841,635 · Granted Jun 28, 2016

Abstract

Claims (77)

1. A method for compressing data for a hash table, the method comprising:

receiving data;

extracting a plurality of middle bits from the data, based on a number of bits to extract;

calculating a decimal value of the plurality of middle bits;

when the decimal value is greater than a total number of sets:

determining a location identifier by subtracting the total number of sets from the decimal value; and

setting a wrapped bit to 1;

otherwise:

determining a location identifier as the decimal value; and

setting the wrapped bit to 0; and

compressing the data based on the location identifier and the wrapped bit.

2. The method of claim 1 , wherein the location identifier comprises a set number.

3. The method of claim 2 , further comprising determining a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) the total number of sets in the hash table.

4. The method of claim 1 , wherein the hash table comprises an index-to-key map for use in a cache.

5. The method of claim 1 , wherein the hash table comprises an index-to-key map for use in a set associative cache.

6. The method of claim 1 , further comprising retrieving target data from the hash table based on the location identifier.

7. The method of claim 6 , wherein retrieving the target data comprises:

receiving an index;

retrieving compressed data stored at the index of the hash table;

determining a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;

determining whether wrapping is required;

when wrapping is required,

expanding the compressed data based on the set number and a total number of sets in the hash table; and

otherwise,

expanding the compressed data based on the set number.

8. A storage device for compressing data for a hash table, the storage device comprising:

a host interface for communicating with a host device;

a memory for storing data;

a memory controller comprising logic stored in a computer readable medium, the logic configured to:

receive data;

extract a plurality of middle bits from the data, based on a number of bits to extract;

calculate a decimal value of the plurality of middle bits;

when the decimal value is greater than a total number of sets:

determine a location identifier by subtracting the total number of sets from the decimal value; and

set a wrapped bit to 1;

otherwise:

determine a location identifier as the decimal value; and

set the wrapped bit to 0; and

compress the data based on the location identifier and the wrapped bit.

9. The storage device of claim 8 , wherein the location identifier comprises a set number.

10. The storage device of claim 9 , wherein the memory controller is configured to determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) the total number of sets in the hash table.

11. The storage device of claim 9 , wherein the memory controller is further configured to retrieve target data from the hash table based on the location identifier.

12. The storage system of claim 11 , wherein the memory controller is configured to:

receive an index;

retrieve compressed data stored at the index of the hash table;

determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;

determine whether wrapping is required;

when wrapping is required,

expand the compressed data based on the set number and a total number of sets in the hash table; and

otherwise,

expand the compressed data based on the set number.

13. The storage device of claim 8 , wherein the hash table comprises an index-to-key map for use in a cache.

14. The storage device of claim 8 , wherein the hash table comprises an index-to-key map for use in a set associative cache.

15. A non-transitory computer program product, tangibly embodied in a computer-readable medium, the computer program product including instructions operable to cause a data processing apparatus to:

receive data;

extract a plurality of middle bits from the data, based on a number of bits to extract;

calculate a decimal value of the plurality of middle bits;

when the decimal value is greater than a total number of sets:

determine a location identifier by subtracting the total number of sets from the decimal value; and

set a wrapped bit to 1;

otherwise;

determine a location identifier as the decimal value; and

set the wrapped bit to 0; and

compress the data based on the location identifier and the wrapped bit.

16. The non-transitory computer program product of claim 15 , wherein the location identifier comprises a set number.

17. The non-transitory computer program product of claim 16 , wherein the computer program product further includes instructions operable to cause a data processing apparatus to determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) the total number of sets in the hash table.

18. The non-transitory computer program product of claim 16 , the computer program product further includes instructions operable to cause a data processing apparatus to retrieve data from the hash table based on the location identifier, the instructions operable to cause a data processing apparatus to:

receive an index;

retrieve compressed data stored at the index of the hash table;

determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;

determine whether wrapping is required;

if wrapping is required,

expand the compressed data based on the set number and a total number of sets in the hash table; and

otherwise,

expand the compressed data based on the set number.

19. The non-transitory computer readable product of claim 16 , wherein the hash table comprises an index-to-key map for use in a cache.

20. The non-transitory computer readable product of claim 16 , wherein the hash table comprises an index-to-key map for use in a set associative cache.

Assignments (12)