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

由于GPU和其他大规模并行商用多核硬件以及编程这些设备所需的软件的快速发展，并行数据结构和算法正成为一个日益重要的研究领域。在这项涉及加州大学戴维斯分校和哈佛大学的合作努力中，私人投资机构将专注于在新平台上设计和实施并行哈希表，这是最基本的数据结构之一。实时并行散列将支持各种图形应用程序对动态变化的数据进行处理，包括空间散列、表面和图像匹配，以及散列八叉树，这反过来又支持许多其他应用程序，包括布尔曲面操作、点云最近邻、光线跟踪加速和光子映射。在以前的工作中，PI构建了一个基线实现，表明可以在GPU上进行有效的并行散列；他们可以像最快的可用基数排序一样快速地构建表，并且可以比二进制搜索更快地对元素执行并行随机访问。在目前的研究中，PI计划显著改进其基线实施，同时也将重点放在相关结构上，如多图和布隆过滤器。新的设计和构造算法将被开发、实施和性能方面的分析，然后应用于各种计算机图形应用程序。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.