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 可以处理的应用类别。 PI 将以免费开源软件的形式发布他们的成果，并将与工业合作伙伴 NVIDIA 合作，将该项目的研究和教育成果纳入 NVIDIA 广泛的教育工作中。在该项目中，PI 建议构建动态、高性能的用于众核 (GPU) 计算的数据结构。现在的GPU数据结构很少在GPU上构建，而是在CPU上构建并复制到GPU上，并且现在的GPU数据结构不能在GPU上动态更新，而是必须从头开始重建。该项目的目标是具有点和范围查询、列表以及近似隶属度和范围查询结构的动态字典数据结构。 PI 将把这些数据结构实现为高性能、灵活的开源软件，并使用这些数据结构开发针对 GPU 的理论模型，供多核计算中的理论家和实践者使用。该项目还将重点关注数据结构设计、实现、建模和评估方面的众多交叉问题，这些问题可能对众核计算产生重大的实际影响。

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
影响因子：
0
作者：
Muhammad A. Awad;Saman Ashkiani;Rob Johnson;Martín Farach-Colton;John Douglas Owens
通讯作者：
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
影响因子：
0
作者：
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
影响因子：
0
作者：
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
影响因子：
0
作者：
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)
影响因子：
0
作者：
Saman Ashkiani;Martín Farach-Colton;John Douglas Owens
通讯作者：
Saman Ashkiani;Martín Farach-Colton;John Douglas Owens