AF: Small: Algorithms for New Memory Models

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

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.