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.