Perfect Hash Function Generation on the GPU with RecSplit

Minimale perfekte Hashfunktionen (MPHFs) bilden eine statische Menge S von beliebigen Schlüsseln auf die Menge der ersten |S| natürlichen Zahlen bijektiv ab, d. h., jeder Hashwert wird exakt einmal verwendet. Sie sind in vielen Anwendungen hilfreich, zum Beispiel, um Hashtabellen mit garantiert konstanter Zugriffszeit zu implementieren. MPHFs können sehr kompakt sein — weniger als 2 Bit pro Schlüssel sind möglich. Andererseits sind MPHFs nicht in der Lage zu entscheiden, ob ein gegebener Schlüssel zu S gehört. Zurzeit ist RecSplit die speichereffizienteste MPHF. RecSplit bietet verschiedene Kompromisse zwischen Platzverbrauch, Konstruktionszeit und Anfragezeit an. ... mehrRecSplit kann zum Beispiel eine MPHF mit 1.56 Bits pro Schlüssel in weniger als 2 ms pro Schlüssel konstruieren. Das ist jedoch zu langsam für große Eingaben. Diese Arbeit präsentiert neue RecSplit-Implementierungen, die Multithreading, SIMD und die Leistung von GPUs nutzen, um die Konstruktionszeit zu verbessern. Gemeinsam mit unserer neuen bijection-rotation-Methode erreichen wir Beschleunigungen um Faktoren bis zu 333 für unsere SIMD-Implementierung auf einer 8-Kern CPU und bis zu 1873 für unsere GPU-Implementierung verglichen mit der originalen, sequenziellen RecSplit-Implementierung. Dadurch können wir MPHFs mit 1.56 Bits pro Schlüssel in weniger als 1.5 μs pro Schlüssel konstruieren.

Minimal perfect hash functions (MPHFs) map a static set S of arbitrary keys bijectively into the first |S| natural numbers, i.e., each hash value is used exactly once. They are useful in many applications, for example, to implement hash tables with guaranteed constant access time. MPHFs can be very compact — less than 2 bits per key are possible. On the other hand, MPHFs are not able to decide whether a given key is in S or not. Currently, the most space-efficient practical MPHF is RecSplit. It provides various tradeoffs between the space consumption, construction time, and query time. ... mehrFor example, RecSplit can construct an MPHF with 1.56 bits per key in less than 2 ms per key. This, however, is too slow for large inputs. In this thesis, we present new implementations of RecSplit that use multithreading, SIMD, and the power of GPUs to improve the construction time. Paired with our new bijection rotation technique, we achieve speedups of up to 333 for our SIMD implementation on an 8-core CPU, and up to 1873 for our GPU implementation compared to the original, sequential implementation of RecSplit. This enables us to construct an MPHF with 1.56 bits per key in less than 1.5 μs per key.