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

HCC：媒介：协作研究：数据并行哈希表：理论、实践和应用

• 批准号: 0964357
• 负责人: Annamaria Amenta
• 金额: $ 53.21万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0964357&HistoricalAwards=false
• 关键词: HCC; Medium; Collaborative; Research; Data

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.

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