A Distributed Hash Table for Shared Memory



Published in: Parallel Processing and Applied Mathematics

DOI: 10.1007/978-3-319-32152-3_2



Distributed algorithms for graph searching require a high-performance CPU-efficient hash table that supports find-or-put. This operation either inserts data or indicates that it has already been added before. This paper focuses on the design and evaluation of such a hash table, targeting supercomputers. The latency of find-or-put is minimized by using one-sided RDMA operations. These operations are overlapped as much as possible to reduce waiting times for roundtrips. In contrast to existing work, we use linear probing and argue that this requires less roundtrips. The hash table is implemented in UPC. A peak-throughput of 114.9 million op/s is reached on an Infiniband cluster. With a load-factor of 0.9, find-or-put can be performed in 4.5μs on average. The hash table performance remains very high, even under high loads.

BibTeX entry:

 author = {Wytse Oortwijn and Tom van Dijk and Jaco van de Pol},
 booktitle = {Parallel Processing and Applied Mathematics},
 doi = {10.1007/978-3-319-32152-3_2},
 publisher = {Springer},
 title = {{A Distributed Hash Table for Shared Memory}},
 year = {2015}