“Real-time parallel hashing on the GPU” – ACM SIGGRAPH HISTORY ARCHIVES

“Real-time parallel hashing on the GPU”

  • ©

Conference:


Type(s):


Title:

    Real-time parallel hashing on the GPU

Session/Category Title:   GPU algorithms & systems

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.

References:


    1. Adalsteinsson, D., and Sethian, J. A. 1995. A fast level set method for propagating interfaces. Journal of Computational Physics 118, 2, 269–277. Google ScholarDigital Library
    2. Azar, Y., Broder, A. Z., Karlin, A. R., and Upfal, E. 2000. Balanced allocations. SIAM Journal on Computing 29, 1 (Feb.), 180–200. Google ScholarDigital Library
    3. Barequet, G. 1997. Using geometric hashing to repair CAD objects. IEEE Computational Science&Engineering 4, 4 (Oct./Dec.), 22–28. Google ScholarDigital Library
    4. Bast, H., and Hagerup, T. 1991. Fast and reliable parallel hashing. In ACM Symposium on Parallel Algorithms and Architectures, 50–61. Google ScholarDigital Library
    5. Bastos, T., and Celes, W. 2008. GPU-accelerated adaptively sampled distance fields. In IEEE International Conference on Shape Modeling and Applications, 171–178.Google Scholar
    6. Bhosle, U., Chaudhuri, S., and Roy, S. D. 2002. The use of geometric hashing for automatic image mosaicing. In Proceedings of the National Conference on Communication, 533–537.Google Scholar
    7. Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 303–312. Google ScholarDigital Library
    8. DeCoro, C., and Tatarchuk, N. 2007. Real-time mesh simplification using the GPU. In Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games, 161–166. Google ScholarDigital Library
    9. Devroye, L., and Morin, P. 2003. Cuckoo hashing: Further analysis. Information Processing Letters 86, 4, 215–219. Google ScholarDigital Library
    10. Fotakis, D., Pagh, R., Sanders, P., and Spirakis, P. 2005. Space efficient hash tables with worst case constant access time. Theory of Computing Systems 38, 2, 229–248.Google ScholarCross Ref
    11. Fox, E. A., Heath, L. S., Chen, Q. F., and Daoud, A. M. 1992. Practical minimal perfect hash functions for large databases. Communications of the ACM 35, 1 (Jan.), 105–121. Google ScholarDigital Library
    12. Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a sparse table with O(1) worst case access time. Journal of the ACM 31, 3 (July), 538–544. Google ScholarDigital Library
    13. Frieze, A., Mitzenmacher, M., and Melsted, P. 2009. An analysis of random-walk cuckoo hashing. In submission.Google Scholar
    14. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Transactions on Graphics 25, 1 (July), 130–150. Google ScholarDigital Library
    15. Germain, R. S., Califano, A., and Colville, S. 1997. Fingerprint matching using transformation parameter clustering. IEEE Computational Science&Engineering 4, 4 (Oct./Dec.), 42–49. Google ScholarDigital Library
    16. Gil, J., and Matias, Y. 1991. Fast hashing on a PRAM—designing by expectation. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 271–280. Google ScholarDigital Library
    17. Gil, J., and Matias, Y. 1998. Simple fast parallel hashing by oblivious execution. SIAM Journal of Computing 27, 5, 1348–1375. Google ScholarDigital Library
    18. Guéziec, A. P., Pennec, X., and Ayache, N. 1997. Medical image registration using geometric hashing. IEEE Computational Science&Engineering 4, 4 (Oct./Dec.), 29–41. Google ScholarDigital Library
    19. Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. ACM Transactions on Graphics 21, 3 (July), 657–664. Google ScholarDigital Library
    20. Lamdan, Y., and Wolfson, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Second International Conference on Computer Vision (ICCV), 238–249.Google Scholar
    21. Lamdan, Y., Schwartz, J. T., and Wolfson, H. J. 1988. On recognition of 3-D objects from 2-D images. In IEEE International Conference on Robotics and Automation, vol. 3, 1407–1413.Google Scholar
    22. Lamdan, Y., Schwartz, J. T., and Wolfson, H. J. 1990. Affine invariant model-based object recognition. IEEE Transactions on Robotics and Automation 6, 5 (Oct.), 578–589.Google ScholarCross Ref
    23. Lefebvre, S., and Hoppe, H. 2006. Perfect spatial hashing. ACM Transactions on Graphics 25, 3 (July), 579–588. Google ScholarDigital Library
    24. Lefohn, A. E., Kniss, J., Strzodka, R., Sengupta, S., and Owens, J. D. 2006. Glift: Generic, efficient, random-access GPU data structures. ACM Transactions on Graphics 26, 1 (Jan.), 60–99. Google ScholarDigital Library
    25. Matias, Y., and Vishkin, U. 1990. On parallel hashing and integer sorting. In Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, 729–743. Google ScholarDigital Library
    26. Matias, Y., and Vishkin, U. 1991. Converting high probability into nearly-constant time, with application to parallel hashing. In ACM Symposium on the Theory of Computing (STOC), 307–316. Google ScholarDigital Library
    27. Nehab, D., and Hoppe, H. 2007. Texel programs for random-access antialiased vector graphics. Tech. Rep. MSR-TR-2007-95, Microsoft.Google Scholar
    28. Nussinov, R., and Wolfson, H. J. 1991. Efficient detection of three-dimensional structural motifs in biological macro-molecules by computer vision techniques. In Proceedings of the National Academy of Sciences of the United States of America, National Academy of Sciences, vol. 88, 10495–10499.Google ScholarCross Ref
    29. Pagh, R., and Rodler, F. F. 2001. Cuckoo hashing. In 9th Annual European Symposium on Algorithms, Springer, vol. 2161 of Lecture Notes in Computer Science, 121–133. Google ScholarDigital Library
    30. Qin, Z., McCool, M. D., and Kaplan, C. 2008. Precise vector textures for real-time 3D rendering. In Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, 199–206. Google ScholarDigital Library
    31. Satish, N., Harris, M., and Garland, M. 2009. Designing efficient sorting algorithms for manycore GPUs. In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium. Google ScholarDigital Library
    32. Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware 2007, 97–106. Google ScholarDigital Library
    33. Sun, X., Zhou, K., Stollnitz, E., Shi, J., and Guo, B. 2008. Interactive relighting of dynamic refractive objects. ACM Transactions on Graphics 27, 3 (Aug.), 35:1–35:9. Google ScholarDigital Library
    34. Vöcking, B. 2003. How asymmetry helps load balancing. Journal of the ACM 50, 4 (July), 568–589. Google ScholarDigital Library
    35. Zhou, K., Gong, M., Huang, X., and Guo, B. 2008. Highly parallel surface reconstruction. Tech. Rep. MSR-TR-2008-53, Microsoft Research, 1 Apr.Google Scholar
    36. Zhou, K., Hou, Q., Wang, R., and Guo, B. 2008. Real-time KD-tree construction on graphics hardware. ACM Transactions on Graphics 27, 5 (Dec.), 126:1–126:11. Google ScholarDigital Library
    37. Zhou, K., Ren, Z., Lin, S., Bao, H., Guo, B., and Shum, H.-Y. 2008. Real-time smoke rendering using compensated ray marching. ACM Transactions on Graphics 27, 3 (Aug.), 36:1–36:12. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org