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

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

• 批准号: 2106827
• 负责人: Michael Bender
• 金额: $ 30万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2106827&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.

计算机行业正处于数据存储技术的革命之中，该革命正在迫使用于通过计算机移动数据的算法进行重新评估。每个新一代的存储硬件都需要对这些算法的构建块有新的理论理解。这样的理论改进对计算机科学的其他领域（包括数据库和文件系统，甚至网络，操作系统和机器学习）产生了深远的影响。 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遵守标准的严格嵌套模型。 该团队正在研究：（a）并行缓存分配和高带宽记忆计划和分配中的算法问题； （b）由不同的I/O成本模型引起的数据结构问题，包括考虑到计算成本和/或耐用性成本的成本模型； （c）向流和半流模型的扩展，其中算法除了传统的小型随机访问记忆池外，还具有一定数量的依次可访问的工作记忆； （d）有向图的新的I/O效率算法。 该团队正在继续进行社区建设努力，以跨越系统和算法，包括成立，转向和/或开展两个新会议，并组织有关非挥发性记忆和存储理论的研讨会。这项奖项反映了NSF的法定任务，并通过使用该基金会的知识优点和广泛影响来评估NSF的法定任务，并被视为值得的支持。

项目成果

An Associativity Threshold Phenomenon in Set-Associative Caches

• DOI: 10.1145/3558481.3591084
• 发表时间: 2023-04
• 期刊: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: M. A. Bender;Rathish Das;Martín Farach-Colton;Guido Tagliavini

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

Mosaic Pages: Big TLB Reach with Small Pages

马赛克页面：小页面实现大 TLB 覆盖范围

• DOI: 10.1145/3582016.3582021
• 发表时间: 2023
• 期刊: Proc.\ 28th {ACM} International Conference on Architectural Support for Programming Languages and Operating Systems
• 作者: Gosakan, Krishnan;Han, Jaehyun;Kuszmaul, William;Mubarek, Ibrahim N.;Mukherjee, Nirjhar;Sriram, Karthik;Tagliavini, Guido;West, Evan;Bender, Michael A.;Bhattacharjee, Abhishek
• 通讯作者: Bhattacharjee, Abhishek

Online Parallel Paging with Optimal Makespan

• DOI: 10.1145/3490148.3538577
• 发表时间: 2022-07
• 期刊: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Kunal Agrawal;M. A. Bender;Rathish Das;William Kuszmaul;E. Peserico;Michele Scquizzato

When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

缓存无关算法何时具有缓存自适应性？

• 发表时间: 2022
• 期刊: ESA
• 作者: Bhattacharya, Arghya;Chowdhury, Abiyaz;Xu, Helen;Das, Rathish;Chowdhury, Rezaul Alam;Johnson, Rob;Nithyanand, Rishab;Bender, Michael A.
• 通讯作者: Bender, Michael A.