research-article

Coherent parallel hashing

Authors:

Ismael García,

Sylvain Lefebvre,

Samuel Hornus,

Anass LasramAuthors Info & Claims

SA '11: Proceedings of the 2011 SIGGRAPH Asia Conference

Article No.: 161, Pages 1 - 8

https://doi.org/10.1145/2024156.2024195

Published: 12 December 2011 Publication History

Get Access

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.

References

[1]

Alcantara, D. A., Sharf, A., Abbasinejad, F., Sengupta, S., Mitzenmacher, M., Owens, J. D., and Amenta, N. 2009. Real-time parallel hashing on the GPU. ACM Transactions on Graphics (Proc. ACM SIGGRAPH Asia) 28, 5.

Digital Library

Google Scholar

[2]

Alcantara, D. A., Volkov, V., Sengupta, S., Mitzenmacher, M., Owens, J. D., and Amenta, N. 2011. Building an efficient hash table on the GPU. In GPU Computing Gems, W.-m. W. Hwu, Ed., vol. 2. Morgan Kaufmann, ch. 1.

Google Scholar

[3]

Botelho, F. C., and Ziviani, N. 2007. External perfect hashing for very large key sets. In Proceedings of the sixteenth ACM Conference on Conference on Information and Knowledge Management, ACM, CIKM '07, 653--662.

Digital Library

Google Scholar

[4]

Celis, P. 1986. Robin Hood Hashing. PhD thesis, University of Waterloo, Ontario, Canada.

Digital Library

Google Scholar

[5]

Devroye, L., Morin, P., and Viola, A. 2004. On worst-case robin hood hashing. SIAM Journal on Computing 33, 923--936.

Crossref

Google Scholar

[6]

Lefebvre, S., and Hoppe, H. 2006. Perfect spatial hashing. ACM Transactions on Graphics (Proc. ACM SIGGRAPH) 25, 3, 579--588.

Digital Library

Google Scholar

[7]

Linial, N., and Sasson, O. 1996. Non-expansive hashing. In Proceedings of the twenty-eighth annual ACM Symposium on Theory of Computing, ACM, STOC '96, 509--518.

Digital Library

Google Scholar

[8]

Pagh, R., and Rodler, F. F. 2004. Cuckoo hashing. Journal of Algorithms 51, 2, 122--144.

Digital Library

Google Scholar

[9]

Peterson, W. W. 1957. Addressing for random-access storage. IBM Journal of Research and Development 1, 2, 130--146.

Digital Library

Google Scholar

Cited By

View all

Lessley BChilds H(2020)Data-Parallel Hashing Techniques for GPU ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.292976831:1(237-250)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TPDS.2019.2929768
Zhang RWijeratne SYang YKuppannagari SPrasanna V(2020)A High Throughput Parallel Hash Table on FPGA using XOR-based Memory2020 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC43674.2020.9286199(1-7)Online publication date: 22-Sep-2020
https://doi.org/10.1109/HPEC43674.2020.9286199
Yang YKuppannagari SSrivastava AKannan RPrasanna V(2020)FASTHash: FPGA-Based High Throughput Parallel Hash TableHigh Performance Computing10.1007/978-3-030-50743-5_1(3-22)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-50743-5_1
Show More Cited By

Index Terms

Coherent parallel hashing
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics file formats

Recommendations

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 ...
Extendible hashing—a fast access method for dynamic files

Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that ...
Complementary Projection Hashing
ICCV '13: Proceedings of the 2013 IEEE International Conference on Computer Vision

Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. Generally, these hashing approaches generate 2^c buckets, where c is the length of the hash code. A good hashing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SA '11: Proceedings of the 2011 SIGGRAPH Asia Conference

December 2011

730 pages

ISBN:9781450308076

DOI:10.1145/2024156

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGCHI: ACM Special Interest Group on Computer-Human Interaction

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 December 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SA '11

Sponsor:

SIGGRAPH

SA '11: SIGGRAPH Asia 2011

December 12 - 15, 2011

Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
508
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lessley BChilds H(2020)Data-Parallel Hashing Techniques for GPU ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.292976831:1(237-250)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TPDS.2019.2929768
Zhang RWijeratne SYang YKuppannagari SPrasanna V(2020)A High Throughput Parallel Hash Table on FPGA using XOR-based Memory2020 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC43674.2020.9286199(1-7)Online publication date: 22-Sep-2020
https://doi.org/10.1109/HPEC43674.2020.9286199
Yang YKuppannagari SSrivastava AKannan RPrasanna V(2020)FASTHash: FPGA-Based High Throughput Parallel Hash TableHigh Performance Computing10.1007/978-3-030-50743-5_1(3-22)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-50743-5_1
Stotko PKrumpen SHullin MWeinmann MKlein R(2019)SLAMCast: Large-Scale, Real-Time 3D Reconstruction and Streaming for Immersive Multi-Client Live TelepresenceIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.289923125:5(2102-2112)Online publication date: May-2019
https://doi.org/10.1109/TVCG.2019.2899231
Gao LXu YWang RYang HLuan ZQian D(2019)Accelerating in-memory transaction processing using general purpose graphics processing unitsFuture Generation Computer Systems10.1016/j.future.2019.03.03497:C(836-848)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1016/j.future.2019.03.034
Junger DHundt CSchmidt B(2018)WarpDrive: Massively Parallel Hashing on Multi-GPU Nodes2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2018.00054(441-450)Online publication date: May-2018
https://doi.org/10.1109/IPDPS.2018.00054
Ashkiani SFarach-Colton MOwens J(2018)A Dynamic Hash Table for the GPU2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2018.00052(419-429)Online publication date: May-2018
https://doi.org/10.1109/IPDPS.2018.00052
Zhou JGuo QJagadish HKrcal LLiu SLuan WTung AYang YZheng Y(2018)A Generic Inverted Index Framework for Similarity Search on the GPU2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00085(893-904)Online publication date: Apr-2018
https://doi.org/10.1109/ICDE.2018.00085
Buckley LByrne JMoloney D(2018)Investigating the Impact of Suboptimal Hashing Functions2018 IEEE Games, Entertainment, Media Conference (GEM)10.1109/GEM.2018.8516265(324-331)Online publication date: Aug-2018
https://doi.org/10.1109/GEM.2018.8516265
Wang HWang ZLi NKong X(2018)Efficient OLAP algorithms on GPU-accelerated Hadoop clustersDistributed and Parallel Databases10.1007/s10619-018-7239-z37:4(507-542)Online publication date: 31-Jul-2018
https://doi.org/10.1007/s10619-018-7239-z
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations