AitF: Efficient Memory Management via Randomized, Streaming, and Online Algorithms

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

Memory management is an essential component of computer systems ranging from small low-power and mobile devices up to large data centers. Memory is necessary for any non-trivial computing process that needs to be performed in order to store the input data and the state of the computation. The goal of efficient memory management is to allocate the available memory to the different processes that need to be performed in such a way that the speed of the subsequent computation is maximized; the energy used by the system is minimized; and the available memory hardware is fully exploited. This project is focused on improving existing memory management approaches and could lead to significant improvements in the computer infrastructure used in a broad range of applications. The project will also train students, both through curriculum development and direct involvement in the research, in the application of algorithm design to the field of computer systems. In this project, we focus on designing and analyzing new randomized algorithms for various problems that arise in the context of memory management. These include both lightweight data stream or "sketch-based" algorithms that are fast and use limited memory, and online algorithms that need to commit to decisions about how to best to use a small amount of available memory without knowing what data or operations on this data will be relevant in the future. We will also develop a new randomized technique for compacting memory even for languages such as C and C++ that use explicit memory management and where objects cannot be relocated. Our approach should mitigate the risk of potentially catastrophic fragmentation and thereby improve memory utilization and performance.