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

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

基本信息

批准号：
2118620
负责人：
Martin Farach-Colton
金额：
$ 12.5万
依托单位：
Rutgers University New Brunswick
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2118620&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 和磁盘之间，但它会产生额外的计算成本，该项目的新颖之处在于采用数据结构中的先进技术来加速地址转换，该项目的影响将极大地加速所有计算机上笔记本电脑的所有计算任务的组件。平行超级计算机，以及从天气模拟到机器学习的计算。研究人员根据研究人员在稳定、低地址复杂性哈希方面的最新进展，提出了 TLB 的重新设计。这种重新设计包括对硬件/软件堆栈的改进。该规划项目的目标是确定团队方法的可行性，为下一阶段提交的完整提案做好准备。研究人员正在根据经验评估默契。地址转换设计背后的假设，为数据中心规模应用程序中的命名、布局、负载平衡和转换的端到端分析和设计提供原则性的理论基础。该奖项反映了 NSF 的法定使命，并被认为是值得的通过使用基金会的智力优势和更广泛的影响审查标准进行评估来获得支持。

项目成果

期刊论文数量（15）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

External-Memory Dictionaries in the Affine and PDAM Models

Affine 和 PDAM 模型中的外部存储器字典

DOI：
10.1145/3323165.3323210
发表时间：
2021-01
期刊：
ACM transactions on parallel computing
影响因子：
0
作者：
Bender, Michael;Conway, Ale;Farach;Jannen, William;Jiao, Yizheng;Johnson, Rob;Knorr, Eric;McAllister, Sara;Mukherjee, Nirjhar;Pandey, Prashant;et al
通讯作者：
et al

Mitigating False Positives in Filters: to Adapt or to Cache?

减少过滤器中的误报：适应还是缓存？

DOI：
发表时间：
2021-01
期刊：
SIAM Symposium on Algorithmic Principles of Computer System
影响因子：
0
作者：
Bender, Michael;Das, Ratish;Farach;Mo, Tianchi;Tench, David;Wang, Yung Ping
通讯作者：
Wang, Yung Ping

Randomized Cup Game Algorithms Against Strong Adversaries

针对强大对手的随机杯赛算法

DOI：
10.1145/3313276.3316342
发表时间：
2021-01
期刊：
Proceedings of the annual ACMSIAM symposium on discrete algorithms
影响因子：
0
作者：
Bender, M;Kuszmaul, W.
通讯作者：
Kuszmaul, W.

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

重新审视线性探测：墓碑标志着主集群的消亡

DOI：
发表时间：
2021-01
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
0
作者：
Bender, M.;Kuszmaul, B.;Kuszmaul, W.
通讯作者：
Kuszmaul, W.

Tight Bounds for Parallel Paging and Green Paging

并行分页和绿色分页的严格界限

DOI：
发表时间：
2021-01
期刊：
Proceedings of the annual ACMSIAM symposium on discrete algorithms
影响因子：
0
作者：
Agrawal, Kunal;Bender, Michael;Das, Ratish;Kuszmaul, William;Peserico, Enoch;Scquizzato, Michele
通讯作者：
Scquizzato, Michele