AF: Small: Algorithms for New Memory Models

Georgetown University, Washington DC

Investigators

Abstract

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.