Granted Patent B2

US 8,806,174 · App. 13/677,791 · Granted Aug 12, 2014

Abstract

Claims (66)

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

receiving data;

determining a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is determined based on the data, wherein the location identifier comprises a set number, and wherein the determining the location identifier for the data includes determining a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;

compressing the data by extracting the location identifier from the data, wherein the compressing includes:

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

calculating a decimal value of the plurality of middle bits;

if the decimal value is greater than the total number of sets;

determining the set number by subtracting the total number of sets from the decimal value; and

setting a wrapped bit to 1;

otherwise,

determining the set number as the decimal value; and

setting the wrapped bit to 0; and

storing the compressed data in the identified location of the hash table.

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

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

4. A storage device for storing data in 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;

determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is derived from the data, wherein the location identifier includes a set number, and wherein the logic configured to determine the location identifier for the data includes logic configured to determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;

compress the data by extracting the location identifier, wherein the logic configured to compress the data includes logic configured to:

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

calculate a decimal value of the plurality of middle bits;

if the decimal value is greater than the total number of sets;

determine the set number by subtracting the total number of sets from the decimal value; and

set a wrapped bit to 1;

otherwise,

determine the set number as the decimal value; and

set the wrapped bit to 0; and

store the compressed data in the identified location of the hash table.

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

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

7. The storage device of claim 4 , wherein the memory controller further comprises logic for retrieving data from the hash table, the logic 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;

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.

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

receive data;

determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is derived from the data, wherein the location identifier includes a set number, and wherein the instructions operable to cause the data processing apparatus to determine the location identifier for the data comprise instructions operable to cause the 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) a total number of sets in the hash table;

compress the data by extracting the location identifier, wherein the instructions operable to cause the data processing apparatus to compress the data include instructions operable to cause the data processing apparatus to:

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

calculate a decimal value of the plurality of middle bits;

if the decimal value is greater than the total number of sets;

determine the set number by subtracting the total number of sets from the decimal value; and

set a wrapped bit to 1;

otherwise;

determine the set number as the decimal value; and

set the wrapped bit to 0; and

store the compressed data in the identified location of the hash table.

9. The computer program product of claim 8 , wherein the hash table comprises an index-to-key map for use in a cache.

10. The computer program product of claim 8 , wherein the hash table comprises an index-to-key map for use in a set associative cache.

11. The computer program product of claim 8 , wherein the computer program product further includes instructions operable to cause a data processing apparatus to retrieve data from the hash table, 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.

Assignments (10)