Item


Coherent parallel hashing

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

This work was supported by the Agence Nationale de la Recherche (SIMILAR-CITIES 2008-COORD-021-01), the European Research Council (GOODSHAPE FP7-ERC-StG-205693), and the Ministerio de Ciencia e Innovacion, Spain (TIN2010-20590-C02-02)

© ACM Transactions on Graphics, 2011, vol. 30, núm. 6, art. 161

Association for Computing Machinery (ACM)

Author: García Fernández, Ismael
Lefebvre, Sylvain
Hornus, Samuel
Lasram, Anass
Date: 2011
Abstract: 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
This work was supported by the Agence Nationale de la Recherche (SIMILAR-CITIES 2008-COORD-021-01), the European Research Council (GOODSHAPE FP7-ERC-StG-205693), and the Ministerio de Ciencia e Innovacion, Spain (TIN2010-20590-C02-02)
Format: application/pdf
ISSN: 0730-0301 (versió paper)
1557-7368 (versió electrònica)
Document access: http://hdl.handle.net/10256/11990
Language: eng
Publisher: Association for Computing Machinery (ACM)
Collection: MICINN/PN 2011-2013/TIN2010-20590-C02-02
Versió postprint del document publicat a: http://dx.doi.org/10.1145/2024156.2024195
Articles publicats (D-IMA)
Is part of: © ACM Transactions on Graphics, 2011, vol. 30, núm. 6, art. 161
Rights: Tots els drets reservats
Subject: Infografia
Computer graphics
Title: Coherent parallel hashing
Type: info:eu-repo/semantics/article
Repository: DUGiDocs

Subjects

Authors