SIMD (Single Instruction, Multiple Data) instructions are a type of computer processor instruction that allows the same operation to be performed on multiple pieces of data at the same time. Typically, one can find all occurrences of a given byte value in a sequence of 16 bytes with a single instruction. When used effectively, this can greatly accelerate performance.
In this talk we explore some current SIMD versions of hash tables. For example, an idea is to build a table of size-16 buckets for the keys, each equipped with a 16-bytes word that contains a 1-byte fingerprint of the keys it contains: when looking for a key, one first checks with only one SIMD instruction if there are keys with the same fingerprint present in the bucket.
In a work that is currently in the writing phase, with Cyril Nicaud, we have successfully derived the mathematical equations that precisely describe the evolution of these tables as elements are inserted. Notably, we study the number of full-buckets (e.g., containing 16 keys). These solutions are not merely the functions resulting from the analysis of standard hash tables multiplied by a constant factor. Instead, they are obtained through a probabilistic approach and are implicitly expressed as solutions of systems of differential equations. This relies on probabilistic techniques developed by Nicholas Wormald for studying dynamic random graphs.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne