Publications

Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from http://www.eg.org/EG/DL. ACM papers (Siggraph, ...) can be downloaded from http://www.acm.org/dl/.

 

“Coherent Parallel Hashing”
Ismael Garcia, Sylvain Lefebvre, Samuel Hornus and Anass Lasram
ACM Transactions on Graphics (SIGGRAPH Asia proceedings), 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.

BibTex reference

@ARTICLE{HASH:2011,
   AUTHOR     = "Garcia, Ismael and Lefebvre, Sylvain and Hornus, Samuel and Lasram, A
                   nass",
   TITLE      = "Coherent Parallel Hashing",
   JOURNAL    = "ACM Transactions on Graphics (SIGGRAPH Asia proceedings)",
   VOLUME     = "30",
   NUMBER     = "6",
   PAGES      = "161",
   MONTH      = "dec",
   YEAR       = "2011",
}