Paper Info
Title
Phase-concurrent hash tables for determinism
Abstract
We present a deterministic phase-concurrent hash table in which operations of the same type are allowed to proceed concurrently, but operations of different types are not. Phase-concurrency guarantees that all concurrent operations commute, giving a deterministic hash table state, guaranteeing that the state of the table at any quiescent point is independent of the ordering of operations. Furthermore, by restricting our hash table to be phase-concurrent, we show that we can support operations more efficiently than previous concurrent hash tables. Our hash table is based on linear probing, and relies on history-independence for determinism. We experimentally compare our hash table on a modern 40-core machine to the best existing concurrent hash tables that we are aware of (hopscotch hashing and chained hashing) and show that we are 1.3--4.1 times faster on random integer keys when operations are restricted to be phase-concurrent. We also show that the cost of insertions and deletions for our deterministic hash table is only slightly more expensive than for a non-deterministic version that we implemented. Compared to standard sequential linear probing, we get up to 52 times speedup on 40 cores with dual hyper-threading. Furthermore, on 40 cores insertions are only about 1.3 times slower than random writes (scatter). We describe several applications which have deterministic solutions using our phase-concurrent hash table, and present experiments showing that using our phase-concurrent deterministic hash table is only slightly slower than using our non-deterministic one and faster than using previous concurrent hash tables, so the cost of determinism is small.
Year
DOI
Venue
2014
10.1145/2612669.2612687
SPAA
Keywords
Field
DocType
applications,determinism,hash table,parallel programming
Primary clustering,Hopscotch hashing,Double hashing,Computer science,Parallel computing,Rolling hash,Algorithm,Hash function,Dynamic perfect hashing,Hash table,Linear hashing,Distributed computing
Conference
Citations 
PageRank 
References 
11
0.48
28
Authors
2
Name
Order
Citations
PageRank
Julian Shun159332.57
Guy E. Blelloch22927207.30