Coherent Parallel Hashing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Graphics Année : 2011

Coherent Parallel Hashing

Samuel Hornus
Anass Lasram
  • Fonction : Auteur
  • PersonId : 885216

Résumé

Recent spatial hashing schemes hash millions of keys in parallel, compacting sparse spatial data in small hash tables while still allowing for fast access from the GPU. Unfortunately, available schemes suffer from two drawbacks: Multiple runs of the construction process are often required before success, and the random nature of the hash functions decreases access performance. We introduce a new parallel hashing scheme which reaches high load factor with a very low failure rate. In addition our scheme has the unique advantage to exploit coherence in the data and the access patterns for faster performance. Compared to existing approaches, it exhibits much greater locality of memory accesses and consistent execution paths within groups of threads. This is especially well suited to Computer Graphics applications, where spatial coherence is common. In absence of coherence our scheme performs similarly to previous methods, but does not suffer from construction failures. Our scheme is based on the Robin Hood scheme modified to quickly abort queries of keys that are not in the table, and to preserve coherence. We demonstrate our scheme on a variety of data sets. We analyze construction and access performance, as well as cache and threads behavior.
Nous décrivons une nouvelle technique de construction de table de hachage en parallèle qui permet d'insérer plusieurs centaines de millions de clés par secondes dans des tables pleines à 99%. Cette technique rend possible un accès très rapide aux données quand l'ordre des requêtes est cohérent, ce qui la rend particulièrement adaptée aux applications de l'informatique graphique.
Fichier principal
Vignette du fichier
paper.pdf (7.33 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00624777 , version 1 (19-09-2011)

Identifiants

Citer

Ismael García, Sylvain Lefebvre, Samuel Hornus, Anass Lasram. Coherent Parallel Hashing. ACM Transactions on Graphics, 2011, Proceedings of ACM SIGGRAPH Asia 2011, 30 (6), ⟨10.1145/2070781.2024195⟩. ⟨inria-00624777⟩
441 Consultations
749 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More