HCC: Medium: Collaborative Research: Data-Parallel Hash Tables: Theory, Practice and Applications

并行数据结构和算法正成为越来越重要的研究领域，这是由于GPU和其他大规模并行商用多核硬件沿着对这些设备进行编程所需的软件的快速发展。 在这项涉及加州大学戴维斯分校和哈佛大学的合作努力中，PI将专注于并行哈希表的设计和实现，这是新平台上最基本的数据结构之一。 实时并行散列将使各种图形应用程序能够动态变化的数据，包括空间散列，表面和图像匹配，以及散列八叉树，这些八叉树又使许多其他应用程序成为可能，包括布尔表面操作，点云最近邻，光线跟踪加速和光子映射。 在之前的工作中，PI构建了一个基线实现，表明可以在GPU上完成有效的并行哈希;他们可以像最快的基数排序一样快速地构建表，并且可以比二进制搜索更快地对元素执行并行随机访问。 在目前的研究中，PI计划显着改进其基线实现，同时还专注于相关结构，如多映射和Bloom过滤器。 新的设计和构造算法将被开发，实现和分析的性能方面，然后应用到各种计算机图形应用程序。PI期望这项工作会导致有趣的理论结果;现代哈希表结构从来没有被认为是在并行上下文中，所以找到正确的分析模型是研究的目标之一。更广泛的影响：这个项目将有助于计算基础设施，不仅为计算机图形，而且为通用计算。 PI将免费发布他们的实现，部分是通过扩展和构建他们现有的（和流行的）通用数据结构库（CUDA数据并行原语）。 PI指出，充分利用新兴的并行GPU资源需要训练下一代程序员并行思考;因此，他们计划利用这个项目作为一个机会，除了与研究生一起学习并行算法之外，还可以恢复长期未教的本科并行编程课程。

Parallel data structures and algorithms are becoming an increasingly important research area, due to the rapid advances in GPUs and other massively parallel commodity multi-core hardware along with the software needed to program these devices. In this collaborative effort involving the University of California at Davis and Harvard University, the PIs will focus on the design and implementation of parallel hash tables, one of the most fundamental of data structures, on the new platforms. Real-time parallel hashing would enable a variety of graphics applications on dynamically changing data, including spatial hashing, surface and image matching, and hashed octrees which in turn enable a host of other applications including Boolean surface operations, point-cloud nearest neighbors, ray-tracing acceleration and photon mapping. In prior work, the PIs built a baseline implementation that shows effective parallel hashing can be done on the GPU; they can construct the table as quickly as the fastest available radix sort, and can execute parallel random access on the elements much more quickly than binary search. In the current research, the PIs plan to improve upon their baseline implementation significantly, while also focusing on related structures such as multi-maps and Bloom filters. New designs and construction algorithms will be developed, implemented, and analyzed with respect to performance, and then applied to a variety of computer graphics applications. The PIs expect this work to lead to interesting theoretical results; modern hash table constructions have never been considered in the parallel context, so finding the right model for analysis is one goal of the research.Broader Impacts: This project will contribute to the computing infrastructure, not only for computer graphics but also for general-purpose computation. The PIs will distribute their implementations freely, in part by extending and building upon their existing (and popular) library of general-purpose data structures (the CUDA Data Parallel Primitives). The PIs note that making the most of the emerging parallel GPU resources requires training the next generation of programmers to think in parallel; therefore, they plan to exploit this project as an opportunity to revive a long-untaught undergraduate parallel programming course, in addition to studying parallel algorithms with their graduate students.