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

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

• 批准号: 1637458
• 负责人: Martin Farach-Colton
• 金额: $ 34.94万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637458&HistoricalAwards=false
• 关键词: AitF; Collaborative; Reserach; 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 的理论模型，供多核计算中的理论家和实践者使用。 该项目还将重点关注数据结构设计、实现、建模和评估中的众多交叉问题，这些问题可能对众核计算产生重大的实际影响。

项目成果

GPU LSM: A Dynamic Dictionary Data Structure for the GPU

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

• 发表时间: 2018-01
• 期刊: IPDPS .... [proceedings]
• 作者: Ashkiani, S.;Li, S.;Farach;Amenta, N.;Owens, J
• 通讯作者: Owens, J

Writes Wrought Right, and Other Adventures in File System Optimization

撰写 Wrought Right 以及文件系统优化中的其他冒险

• DOI: 10.1145/3032969
• 发表时间: 2017-03-16
• 期刊: ACM Transactions on Storage (TOS)
• 作者: Jun Yuan;Yang Zhan;William K. Jannen;P. P;ey;ey;Amogh Akshintala;Kanchan Ch;nani;nani;Pooja Deo;Zardosht Kasheff;L. Walsh;M. A. Bender;Martín Farach;Rob Johnson;Bradley C. Kuszmaul;Donald E. Porter
• 通讯作者: Donald E. Porter

Write-Optimized Skip Lists

写入优化的跳跃列表

• DOI: 10.1145/3034786.3056117
• 发表时间: 2017-05-09
• 期刊: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: M. A. Bender;Martín Farach;Rob Johnson;Simon Mauras;Tyler Mayer;C. Phillips;Helen Xu
• 通讯作者: Helen Xu

Optimal Hashing in External Memory

外部存储器中的最佳散列

• DOI: 10.4230/lipics.icalp.2018.39
• 发表时间: 2018-05-23
• 作者: Alex Conway;Martín Farach;Philip Shilane
• 通讯作者: Philip Shilane

A Dynamic Hash Table for the GPU

GPU 的动态哈希表

• 发表时间: 2018-01
• 期刊: IPDPS .... [proceedings]
• 作者: Ashkiani, S;Farach;Owens, J.
• 通讯作者: Owens, J.