25447

Better GPU Hash Tables

Muhammad A. Awad, Saman Ashkiani, Serban D. Porumbescu, Martín Farach-Colton, John D. Owens
Dept. of Elect. and Comp. Engineering, UC Davis, Davis, CA, USA
arXiv:2108.07232 [cs.DS], (16 Aug 2021)

@misc{awad2021better,

   title={Better GPU Hash Tables},

   author={Muhammad A. Awad and Saman Ashkiani and Serban D. Porumbescu and Martín Farach-Colton and John D. Owens},

   year={2021},

   eprint={2108.07232},

   archivePrefix={arXiv},

   primaryClass={cs.DS}

}

Download Download (PDF)   View View   Source Source   

206

views

We revisit the problem of building static hash tables on the GPU and design and build three bucketed hash tables that use different probing schemes. Our implementations are lock-free and offer efficient memory access patterns; thus, only the probing scheme is the factor affecting the performance of the hash table’s different operations. Our results show that a bucketed cuckoo hash table that uses three hash functions (BCHT) outperforms alternative methods that use power-of-two choices, iceberg hashing, and a cuckoo hash table that uses a bucket size one. At high load factors as high as 0.99, BCHT enjoys an average probe count of 1.43 during insertion. Using three hash functions only, positive and negative queries require at most 1.39 and 2.8 average probes per key, respectively.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: