Collaborative Research: PPoSS: Planning: Efficient Address Translation with Formal Guarantees for Data-Center-Scale Applications

协作研究：PPoSS：规划：有效的地址转换，为数据中心规模的应用程序提供正式保证

• 批准号: 2118830
• 负责人: Michael Bender
• 金额: $ 6.25万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2023-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2118830&HistoricalAwards=false
• 关键词: Collaborative; Research; PPoSS; Planning; Efficient

The investigators propose a bottom-up redesign of address translation, a critical bottleneck in the way computers organize where data is stored---whether the computer is a laptop or a massively parallel supercomputer. Address translation gives computer systems flexibility in placing and migrating data between RAM and disk, but it incurs an additional computational cost. The project’s novelty is to employ advanced techniques in data structures to accelerate address translation. The project’s impact will be to dramatically accelerate a component of all computational tasks, on all computers, from laptops to parallel supercomputers, and for computations ranging from weather simulations to machine learning.The investigators propose a redesign of TLBs, based on the investigators’ recent advances in stable, low-address-complexity hashing. This redesign includes improvements across the hardware/software stack, from the CPU, to hardware accelerators, to RDMA. The goal of this planning project is to establish the viability of the team’s approach in preparation for a full proposal to be submitted in the next phase. The investigators are empirically evaluating tacit assumptions behind address-translation design, providing a principled theoretical foundation for end-to-end analysis and design of naming, placement, load balancing, and translation in data-center-scale applications.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.

研究人员提出了地址翻译的自下而上的重新设计，这是计算机整理数据存储位置的关键瓶颈 - 无论计算机是笔记本电脑还是大量并行超级计算机。地址翻译使计算机系统在将RAM和磁盘之间放置和迁移数据时具有灵活性，但会产生额外的计算成本。该项目的新颖性是在数据结构中采用先进的技术来加速地址翻译。项目的影响将是在所有计算机，从笔记本电脑到平行超级计算机的所有计算机上的所有计算任务的组成部分，以及从天气模拟到机器学习的计算。重新设计包括从CPU到硬件加速器再到RDMA的硬件/软件堆栈的改进。该计划项目的目的是建立团队方法的可行性，以准备在下一阶段提交的完整建议。调查人员正在紧急评估地址翻译设计背后的默认假设，为数据中心规模应用程序中的端到端分析和设计提供了校长的理论基础。该奖项在数据中心规模的应用中。该奖项反映了NSF的法定任务，反映了通过评估范围的支持者的支持者，该奖项已被评估概念和众所周知的基础。

项目成果

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.

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