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的广泛教育工作中。在该项目中，PIS建议为许多CORE（GPU）计算建立动态，高表现数据结构。今天的GPU数据结构很少在GPU上构建，而是在CPU上构建并复制到GPU，而今天的GPU数据结构不能在GPU上动态更新，但必须从Scratch重建。该项目针对具有点和范围查询，列表以及近似成员资格和范围查询结构的动态词典数据结构。 PI将将这些数据结构作为高性能，灵活，开源软件实施，并使用这些数据结构来开发针对GPU的理论模型，用于理论家和从业者在Manuscore计算中使用。该项目还将集中在数据结构设计，实施，建模和评估中的许多跨切割问题上，这些问题可能对许多核计算产生重大实际影响。

项目成果

期刊论文数量（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