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

存储器管理是从小型低功耗和移动的设备到大型数据中心的计算机系统的重要组成部分。存储器对于需要执行的任何非平凡计算过程都是必需的，以便存储输入数据和计算状态。高效内存管理的目标是将可用内存分配给需要执行的不同进程，以使后续计算的速度最大化;系统使用的能量最小化;并且充分利用可用的内存硬件。该项目的重点是改进现有的内存管理方法，并可能导致在广泛的应用程序中使用的计算机基础设施的显着改善。本项目还将通过课程开发和直接参与研究，培养学生将算法设计应用于计算机系统领域的能力。在本项目中，我们专注于针对内存管理中出现的各种问题设计和分析新的随机算法。这些包括轻量级数据流或“基于草图”的算法，这些算法速度快，使用有限的内存，以及在线算法，这些算法需要致力于如何最好地使用少量可用内存，而不知道将来哪些数据或这些数据上的操作将是相关的。我们还将开发一种新的随机化技术，用于压缩内存，即使是对于使用显式内存管理的C和C++等语言，以及无法重新定位对象的语言。我们的方法应该减轻潜在的灾难性碎片的风险，从而提高内存利用率和性能。

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.