Accelerator for concurrent insert and lookup operations in cuckoo hashing
AssigneeIntel Corporation
InventorsPrerna Budhkar, Tanvi Sharma, Srivatsa Rangachar Srinivasa, Dileep John Kurian, Tanay Karnik
Life of this patent
Estimating the term…
Abstract
A hash accelerator of a cache memory may receive a query from a processor comprising the cache memory, the query to comprise an input key and an operation to be performed based on a hash table stored in the cache memory. The hash accelerator may determine whether an entry associated with the input key exists in a lock board of the hash accelerator. The hash accelerator may process the query based on whether the entry exists in the lock board.
Claims20
An apparatus, comprising:
- a processor to comprise a cache memory;
- and
- the cache memory to comprise circuitry for a hash accelerator, the circuitry for the hash accelerator to:
- receive a query from the processor, the query to comprise an input key and an operation to be performed based on a hash table to be stored in the cache memory;
- add an entry associated with the input key to a query tracker of the hash accelerator;
- determine whether the entry associated with the input key exists in a lock board of the hash accelerator;
- and
- process the query based on whether the entry exists in the lock board.
A method, comprising:
- receiving, by a hash accelerator of a cache memory, a query from a processor comprising the cache memory, the query to comprise an input key and an operation to be performed based on a hash table stored in the cache memory;
- adding, by the hash accelerator, an entry associated with the input key to a query tracker of the hash accelerator;
- determining, by the hash accelerator, whether the entry associated with the input key exists in a lock board of the hash accelerator;
- and
- processing, by the hash accelerator, the query based on whether the entry exists in the lock board.
A non-transitory computer-readable storage medium including instructions that when executed by a hash accelerator, cause the hash accelerator to:
- receive a query from a processor, the query to comprise an input key and an operation to be performed based on a hash table stored in a cache memory of the processor;
- add an entry associated with the input key to a query tracker of the hash accelerator;
- determine whether the entry associated with the input key exists in a lock board of the hash accelerator;
- and
- process the query based on whether the entry exists in the lock board.
Dependencies are inferred from the claim text.