AitF: Collaborative Reserach: Theory and Implementation of Dynamic Data Structures for the GPU

计算机以“数据结构”组织数据，这种结构的设计是为了允许对数据进行某些操作，例如查找符合特定标准集的所有项，或向现有数据集添加新项。计算机科学家努力构建能够快速有效地执行这些操作的数据结构。使数据结构操作更快的一种方法是使用不止一个，而是多个并行操作的处理器来执行给定的操作。然而，今天的许多并行数据结构只支持有限的一组操作，而且，值得注意的是，不允许修改这些数据结构的操作，而不是在只更新部分数据时从头开始重建整个结构。在这个项目中，pi汇集了数据结构和并行计算方面的专业知识，以设计、构建和评估允许更新操作的动态数据结构。这项工作的目标是高性能、高度并行的图形处理单元（GPU），并将显著拓宽GPU可以处理的应用类别。这些pi将以免费开源软件的形式发布他们的研究成果，并将与工业合作伙伴NVIDIA合作，将该项目的研究和教育成果纳入NVIDIA广泛的教育工作中。在这个项目中，pi建议为多核（GPU）计算构建动态、高性能的数据结构。今天的GPU数据结构很少在GPU上构建，而是在CPU上构建并复制到GPU上，并且今天的GPU数据结构不能在GPU上动态更新，而是必须从头开始重建。该项目针对具有点和范围查询、列表、近似成员关系和范围查询结构的动态字典数据结构。pi将把这些数据结构作为高性能、灵活的开源软件来实现，并使用这些数据结构来开发针对GPU的理论模型，供理论家和多核计算从业者使用。该项目还将关注数据结构设计、实现、建模和评估方面的许多交叉问题，这些问题可能对多核计算产生重大的实际影响。

Computers organize data in "data structures," which are designed to allow certain operations on data such as looking up all items that match a particular set of criteria, or adding new items to an existing data set. Computer scientists strive to build data structures that can perform these operations quickly and efficiently. One way to make data structure operations faster is to use not just one but many processors, operating in parallel, to perform a given operation. However, many of today's parallel data structures support only a limited set of operations and, notably, do not allow operations that modify these data structures instead of rebuilding an entire structure from scratch when only part of the data is updated. In this project the PIs bring together expertise in data structures and parallel computing to design, build, and evaluate dynamic data structures that allow update operations. This work targets the high-performance, highly-parallel graphics processing unit (GPU) and will significantly broaden the class of applications that the GPU can address. The PIs will release their results as freely-available open-source software and will work with industrial partner NVIDIA to incorporate the research and educational outcomes of this project into NVIDIA's broad educational efforts.In this project the PIs propose to build dynamic, high-performance data structures for manycore (GPU) computing. Today's GPU data structures are rarely constructed on the GPU but instead are built on the CPU and copied to the GPU, and today's GPU data structures cannot be updated dynamically on the GPU but instead must be rebuilt from scratch. This project targets dynamic dictionary data structures with point and range queries, lists, and approximate membership and range query structures. The PIs will implement these data structures as high-performance, flexible, open-source software and use these data structures to develop a theoretical model, targeted at the GPU, for use by theorists and practitioners in manycore computing. The project will also focus on numerous cross-cutting issues in data structure design, implementation, modeling, and evaluation that have the potential for significant practical impact on manycore computing.