AF: Small: Collaborative Research: Maintaining order

AF：小：协作研究：维持秩序

• 批准号: 1617727
• 负责人: Jeremy Fineman
• 金额: $ 23.97万
• 依托单位: Georgetown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617727&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Maintaining

This project investigates "order structures," that is, data structures for maintaining total orders on dynamic data sets. Order structures are applicable in surprisingly diverse settings. The PIs aim to answer fundamental theoretical questions relating to order structures. The investigation takes place in the context of two high-impact application areas: (1) tools for debugging parallel programs and (2) data structures used in databases and file systems to organize data on disk or SSDs. As part of the project, the PIs will develop publicly available educational materials and reference implementations on order structures to be incorporated into courses at their institutions and shared openly on the web.The order structures addressed in this project are order-maintenance data structures, sparse tables, and data structures for incremental topological ordering. The investigation comprises (1) new algorithms with good worst-case guarantees, (2) algorithms with strong common-case guarantees, i.e., optimized for common input distributions, (3) provably good concurrent algorithms, (4) algorithms that leverage randomization in surprising ways (e.g., to achieve history independence), and (5) robust lower bounds that also apply to the randomized setting. In the context of the target applications, the PIs will design and use order structures to implement race detectors, which uncover determinacy races in parallel programs. The PIs will also use orders structures to build external-memory key-value stores to make databases and file systems run faster.

该项目研究“订单结构”，即用于维护动态数据集总订单的数据结构。 订单结构适用于令人惊讶的多样化环境。 PI 旨在回答与订单结构相关的基本理论问题。这项调查是在两个高影响力的应用领域进行的：(1) 用于调试并行程序的工具；(2) 数据库和文件系统中使用的数据结构，用于组织磁盘或 SSD 上的数据。 作为该项目的一部分，PI 将开发关于订单结构的公开教育材料和参考实现，将其纳入其机构的课程中并在网络上公开共享。该项目中解决的订单结构是订单维护数据结构，稀疏用于增量拓扑排序的表和数据结构。 研究包括（1）具有良好的最坏情况保证的新算法，（2）具有强大的常见情况保证的算法，即针对常见输入分布进行优化，（3）可证明良好的并发算法，（4）利用随机化的算法令人惊讶的方法（例如，实现历史独立性），以及（5）也适用于随机设置的稳健下限。在目标应用程序的背景下，PI 将设计并使用顺序结构来实现竞争检测器，从而揭示并行程序中的确定性竞争。 PI 还将使用订单结构来构建外部内存键值存储，以使数据库和文件系统运行得更快。

项目成果

Efficient race detection with futures

通过 future 进行高效种族检测

• DOI: 10.1145/3293883.3295732
• 发表时间: 2019
• 期刊: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
• 作者: Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy;Lee, I-Ting Angelina
• 通讯作者: Lee, I-Ting Angelina

Race detection and reachability in nearly series-parallel DAGs

近串联并行 DAG 中的竞争检测和可达性

• DOI: 10.1137/1.9781611975031.11
• 发表时间: 2018
• 期刊: Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Agrawal, Kunal;Devietti, Joseph;Fineman, Jeremy T.;Lee, I-Ting Angelina;Utterback, Robert;Xu, Changming
• 通讯作者: Xu, Changming

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

近乎高效的有向图可达性并行算法

• DOI: 10.1137/18m1197850
• 发表时间: 2020
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Fineman, Jeremy T.