Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories

合作研究：AF：媒介：平地历险记：现代记忆算法

• 批准号: 2106999
• 负责人: Martin Farach-Colton
• 金额: $ 29.98万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2024-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106999&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Adventures

The computer industry is in the midst of a revolution in data-storage technology that is forcing a major reevaluation of the algorithms used for moving data through the computer. Every new generation of storage hardware has required a new theoretical understanding of these algorithmic building blocks. Such theoretical improvements have had a profound impact on other fields of computer science, including databases and file systems, and even networks, operating systems, and machine learning. This project aims to develop the algorithmic solutions needed to exploit this seismic shift in storage technology.The team considers three impacts on algorithm performance that arise from new hardware technology such as nonvolatile memories and increased parallelism: (1) there are smaller gaps between levels in latency and in bandwidth, (2) many-core technologies introduce sharing effects on caches, and (3) memory hierarchies do not adhere to a standard strictly nested model. The team is investigating: (a) algorithmic problems in parallel-cache allocation and high-bandwidth-memory scheduling and allocation; (b) data structural problems that arise from different I/O cost models, including those that factor in the computational cost and/or the cost of durability; (c) extensions to the streaming and semi-streaming models, where algorithms have some amount of sequentially accessible working memory in addition to the traditional small pool of randomly accessible memory; (d) new I/O-efficient algorithms for directed graphs. The team is continuing community-building efforts to span systems and algorithms, including founding, steering, and/or running two new conferences and organizing workshops on the theory of non-volatile memory and storage.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

计算机行业正处于一场数据存储技术革命之中，这场革命迫使人们对用于在计算机中传输数据的算法进行重大重新评估。每一代新的存储硬件都需要对这些算法构建块有新的理论理解。这样的理论改进对计算机科学的其他领域产生了深远的影响，包括数据库和文件系统，甚至网络、操作系统和机器学习。该项目旨在开发算法解决方案，以利用存储技术的这一巨变。团队考虑了非易失性存储器和增加的并行度等新硬件技术对算法性能的三个影响：(1)延迟和带宽级别之间的差距较小；(2)多核技术在缓存上引入共享效应；(3)内存层次结构不遵守标准的严格嵌套模型。该团队正在调查：(A)并行缓存分配和高带宽内存调度和分配中的算法问题；(B)由不同I/O成本模型引起的数据结构问题，包括那些考虑计算成本和/或耐用性成本的问题；(C)对流和半流模型的扩展，其中算法除了传统的小容量随机访问内存池外，还具有一定数量的顺序访问工作内存；(D)用于有向图的新的I/O高效算法。该团队正在继续社区建设工作，以跨越系统和算法，包括创建、指导和/或举办两个新的会议，并组织关于非易失性存储器和存储理论的研讨会。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

用弦将多边形切割成小块：基于激光的定位

• DOI: 10.4230/lipics.esa.2020.7
• 发表时间: 2020
• 期刊: Leibniz international proceedings in informatics
• 作者: Arkin, Esther;Das, Rathish;Gao, Jie;Goswami, Mayank;Mitchell, Joseph;Polishchuk, Valentin;Toth, Csaba.
• 通讯作者: Toth, Csaba.

Timely Reporting of Heavy Hitters using External Memory

使用外部存储器及时报告重要人物

• 发表时间: 2021
• 期刊: SIGMOD record
• 影响因子: 1.1
• 作者: Singh, S;Pandey, P;Bender, M.;Berry, J.;Farach-Colton, M;Johnson, R;Kroeger, T.;Phillips, C
• 通讯作者: Phillips, C

SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores

• 发表时间: 2020
• 作者: Alex Conway;Abhishek K. Gupta;Vijay Chidambaram;Martín Farach-Colton;Richard P. Spillane;Amy Tai;Rob Johnson

GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams

• DOI: 10.1145/3514221.3526146
• 发表时间: 2022-03
• 期刊: Proceedings of the 2022 International Conference on Management of Data
• 作者: D. Tench;Evan West;Victor Zhang;M. A. Bender;Abiyaz Chowdhury;J. Dellas;Martín Farach-Colton;Tyler Seip;Kenny Zhang;Abiyaz Chowd-hury

Batched Predecessor and Sorting with Size-Priced Information in External Memory

批处理前驱和外部存储器中按大小定价的信息排序

• DOI: 10.1007/978-3-030-61792-9_13
• 发表时间: 2021
• 期刊: Latin American Symposium on Theoretical Informatics
• 作者: Bender, Michael A;Goswami, Mayank;Medjedovic, Dzejla;Montes, Pablo;Tsichlas, Kostas
• 通讯作者: Tsichlas, Kostas