AF: Small: Algorithms for New Memory Models

AF：小：新内存模型的算法

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

Accessing memory and storage has a substantial impact on the performance of computer programs, particularly when operating on large data sets. As such, memory-efficient algorithms (or algorithms designed to optimize for memory accesses) have received significant attention both in theory and practice. With new developments in memory technology and usage, however, the classic models less accurately capture true system performance characteristics. The goal of this project is to develop a theory for new memory models that more closely capture important performance features arising from recent shifts in memory technology and usage. The project advances the state of the art in several directions, including new performance models, new memory-efficient algorithms in these models, new techniques for understanding the performance of algorithms, and new lower bounds to explain the limits of algorithm performance. The algorithms studied are themselves fundamental building blocks in larger systems, and importing any new efficient solutions into existing programming platforms could directly improve the performance of diverse software systems. As part of the project the PI will develop educational materials, and any reference implementations developed as part of the project will be made available to the public.This project studies algorithms in two classes of new memory models, namely the cache-adaptive model and the asymmetric-memory models. The cache-adaptive model is a way of modeling the fluctuations in effective memory size that occur when multiple processes compete for space in a shared cache. Efficient cache-adaptive algorithms should have more robust and predictable performance on parallel systems. This project considers the following areas relating to cache-adaptive algorithms: (1) new cache-adaptive algorithms, (2) new cache-adaptive data structures, (3) more general performance theorems, and (4) how sensitive the algorithms and their analyses are to worst-case adversaries. An asymmetric-memory model is a model where writes are significantly more expensive than reads; asymmetric models are relevant, e.g., to phase-change memories and other emerging memory technologies. This project studies (1) new algorithms for asymmetric memory models, including implicit representations of solution outputs that allow for a sublinear number of writes, and (2) lower bounds for algorithms in these models.

内存和存储对计算机程序的性能有很大的影响，特别是在对大型数据集进行操作时。因此，存储器高效算法（或被设计为优化存储器访问的算法）在理论和实践中都受到了极大的关注。然而，随着内存技术和使用的新发展，经典模型无法准确地捕捉真实的系统性能特征。这个项目的目标是为新的内存模型开发一个理论，更紧密地捕捉内存技术和使用的最新变化所产生的重要性能特征。该项目在几个方向上推进了最先进的技术，包括新的性能模型，这些模型中的新内存效率算法，用于理解算法性能的新技术，以及解释算法性能限制的新下限。所研究的算法本身就是大型系统的基本构建模块，将任何新的有效解决方案导入现有的编程平台可以直接提高各种软件系统的性能。作为项目的一部分，PI将开发教育材料，作为项目的一部分开发的任何参考实现将提供给公众。该项目研究两类新的内存模型中的算法，即缓存自适应模型和非对称内存模型。 缓存自适应模型是一种对多个进程竞争共享缓存中的空间时发生的有效内存大小波动进行建模的方法。高效的缓存自适应算法应该在并行系统上具有更健壮和可预测的性能。这个项目考虑了以下与缓存自适应算法相关的领域：（1）新的缓存自适应算法，（2）新的缓存自适应数据结构，（3）更一般的性能定理，以及（4）算法及其分析对最坏情况对手的敏感程度。非对称内存模型是一种写入比读取成本高得多的模型;非对称模型是相关的，例如，相变存储器和其他新兴的存储器技术。本项目研究（1）非对称内存模型的新算法，包括允许次线性写入数的解决方案输出的隐式表示，以及（2）这些模型中算法的下限。

项目成果

Optimal Parallel Algorithms in the Binary-Forking Model

二分叉模型中的最优并行算法

• DOI: 10.1145/3350755.3400227
• 发表时间: 2020
• 期刊: ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Blelloch, Guy E.;Fineman, Jeremy T.;Gu, Yan;Sun, Yihan
• 通讯作者: Sun, Yihan

Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm

简短公告：改进的分布式近似单源最短路径算法

• DOI: 10.1145/3465084.3467945
• 发表时间: 2021
• 期刊: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
• 作者: Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
• 通讯作者: Russell, Katina

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

I/O-Efficient Algorithms for Topological Sort and Related Problems

拓扑排序及相关问题的 I/O 高效算法

• DOI: 10.1137/1.9781611975482.124
• 发表时间: 2019
• 期刊: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algortihms
• 作者: Cao, Nairen;Fineman, Jeremy T;Russell, Katina;Yang, Eugene
• 通讯作者: Yang, Eugene

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

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

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