Apparatus and method for hash table access

摘要

A system and method for accessing a hash table are provided. A hash table includes buckets where each bucket includes multiple chains. When a single instruction multiple data (SIMD) processor receives a group of threads configured to execute a key look-up instruction that accesses an element in the hash table, the threads executing on the SIMD processor identify a bucket that stores a key in the key look-up instruction. Once identified, the threads in the group traverse the multiple chains in the bucket, such that the elements at a chain level in the multiple chains are traversed in parallel. The traversal continues until a key look-up succeeds or fails.

主权项

1. A system comprising:
a memory configured to store a hash table, wherein the hash table comprises a bucket including first and second chains storing elements, wherein the first and second chains in the bucket are folded to enable a single hash table look-up operation that is parallelized for single instruction multiple data (SIMD) processing; and a SIMD processor configured to:
fold the first and second chains in the hash table into folded chains, wherein a folded chain stores multiple chains and substantially same number of elements as other folded chains;determine that the bucket stores an element associated with a key in a key look-up instruction; andtraverse elements in the first chain using a first thread in parallel with traversing elements in the second chain using a second thread in a wide sweep search until a key look-up instruction succeeds or fails, the first chain and the second chain being at the same depth level, wherein the first and second threads are associated with a group of threads configured to execute the key look-up instruction in parallel.