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

AitF：协作研究：GPU 动态数据结构的理论与实现

• 批准号: 1637442
• 负责人: John Owens
• 金额: $ 43.89万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637442&HistoricalAwards=false
• 关键词: AitF; Collaborative; Research; Theory; Implementation

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.

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

项目成果

Engineering a high-performance GPU B-Tree

• DOI: 10.1145/3293883.3295706
• 发表时间: 2019-02
• 期刊: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
• 作者: Muhammad A. Awad;Saman Ashkiani;Rob Johnson;Martín Farach-Colton;John Douglas Owens

Quotient Filters: Approximate Membership Queries on the GPU

商过滤器：GPU 上的近似成员资格查询

• DOI: 10.1109/ipdps.2018.00055
• 发表时间: 2018
• 期刊: Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium
• 作者: Geil, Afton;Farach-Colton, Martin;Owens, John D.
• 通讯作者: Owens, John D.

Dynamic Graphs on the GPU

GPU 上的动态图

• DOI: 10.1109/ipdps47924.2020.00081
• 发表时间: 2020
• 期刊: Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium
• 作者: Awad, Muhammad A;Ashkiani, Saman;Porumbescu, Serban D.;Owens, John D.
• 通讯作者: Owens, John D.

GPU LSM: A Dynamic Dictionary Data Structure for the GPU

GPU LSM：GPU 的动态字典数据结构

• DOI: 10.1109/ipdps.2018.00053
• 发表时间: 2018
• 期刊: Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium
• 作者: Ashkiani, Saman;Li, Shengren;Farach-Colton, Martin;Amenta, Nina;Owens, John D.
• 通讯作者: Owens, John D.

A Dynamic Hash Table for the GPU

• DOI: 10.1109/ipdps.2018.00052
• 发表时间: 2017-10
• 期刊: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
• 作者: Saman Ashkiani;Martín Farach-Colton;John Douglas Owens